amparvardi wrote: Let $f: \mathbb N \to \mathbb N$ be a function such that $f(1)=1$ and \[f(n)=n - f(f(n-1)) \qquad n \geq 2.\] Prove that $f(n+f(n))=n $ for each positive integer $n.$ Note. $\mathbb N$ denotes the set of positive integers. I'm sure it's not the requested solution, but there is a simple way : It's not very difficult to see that $f(x)$ is unique. let then $f(n)=\left\lfloor\frac{2n+2}{1+\sqrt 5}\right\rfloor$ It's rather easy (with some careful casework) to prove that this $f(x)$ matches the two equations. Hence the result.

pco wrote: amparvardi wrote: Let $f: \mathbb N \to \mathbb N$ be a function such that $f(1)=1$ and \[f(n)=n - f(f(n-1)) \qquad n \geq 2.\] Prove that $f(n+f(n))=n $ for each positive integer $n.$ Note. $\mathbb N$ denotes the set of positive integers. I'm sure it's not the requested solution, but there is a simple way : It's not very difficult to see that $f(x)$ is unique. let then $f(n)=\left\lfloor\frac{2n+2}{1+\sqrt 5}\right\rfloor$ It's rather easy (with some careful casework) to prove that this $f(x)$ matches the two equations. Hence the result. i see $f(2)=1$ so

bigbang195 wrote: i see $f(2)=1$ so So what ?

$f(2)=\left\lfloor\frac{2.2+2}{1+\sqrt 5}\right\rfloor=2 \not=1$

bigbang195 wrote: $f(2)=\left\lfloor\frac{2.2+2}{1+\sqrt 5}\right\rfloor=2 \not=1$ In my country, $\frac{2.2+2}{1+\sqrt 5}=1.854101966...$ and so $f(2)=\left\lfloor\frac{2.2+2}{1+\sqrt 5}\right\rfloor=1$

i'm sorry, it's stupid mistake :-s you can resolved this problem carefully i just understand

pco wrote: amparvardi wrote: Let $f: \mathbb N \to \mathbb N$ be a function such that $f(1)=1$ and \[f(n)=n - f(f(n-1)) \qquad n \geq 2.\] Prove that $f(n+f(n))=n $ for each positive integer $n.$ Note. $\mathbb N$ denotes the set of positive integers. I'm sure it's not the requested solution, but there is a simple way : It's not very difficult to see that $f(x)$ is unique. let then $f(n)=\left\lfloor\frac{2n+2}{1+\sqrt 5}\right\rfloor$ It's rather easy (with some careful casework) to prove that this $f(x)$ matches the two equations. Hence the result. I understand there can only be one solution (induction from 1, we see always only 1 f(n) if we know f(n-1), but how can we guess the only solution;$f(n)=\left\lfloor\frac{2n+2}{1+\sqrt 5}\right\rfloor$ ?

SCP wrote: pco wrote: amparvardi wrote: Let $f: \mathbb N \to \mathbb N$ be a function such that $f(1)=1$ and \[f(n)=n - f(f(n-1)) \qquad n \geq 2.\] Prove that $f(n+f(n))=n $ for each positive integer $n.$ Note. $\mathbb N$ denotes the set of positive integers. I'm sure it's not the requested solution, but there is a simple way : It's not very difficult to see that $f(x)$ is unique. let then $f(n)=\left\lfloor\frac{2n+2}{1+\sqrt 5}\right\rfloor$ It's rather easy (with some careful casework) to prove that this $f(x)$ matches the two equations. Hence the result. I understand there can only be one solution (induction from 1, we see always only 1 f(n) if we know f(n-1), but how can we guess the only solution;$f(n)=\left\lfloor\frac{2n+2}{1+\sqrt 5}\right\rfloor$ ? According to me, there is no way to guess. I remembered some old exercices about $f(n+f(n))=n$ whose solution was something similar to $\lfloor\frac n{\varphi}\rfloor$ and I made some trials in order to find the good value. Then , there is just some work to prove it. Since it's impoissible to guess, that's the reason why I wrote "I'm sure it's not the requested solution" : I think there is surely a simple direct way.

I think I got an idea. It is clear that we can determine all the values of the function, and therefore the function is unique. By checking the first values by hand we see that our function is increasing and it increases with at most $1$ at a time. It is clear that $f(n)\leq n,\ \forall n \in \Bbb{N}$. Now suppose that $f(n) \in \{f(n-1),f(n-1)+1\},\ (\star)$. This can be seen to be true for small $n$. Suppose now that $(\star)$ is true for all $n\leq N$. Then $f(N+1)-f(N)=1-(f(f(N))-f(f(N-1)))$. Let's analyze $h=f(f(N))-f(f(N-1))$. If $f(N)=f(N-1)$ then $h=0$. If $f(N)=f(N-1)+1$ then, because of the inductive hypothesis we need to have $h \in \{0,1\}$. Anyway, $h$ can only take the values $0,1$. This proves by induction that $(\star)$ is true for all positive integers. Now let's try to prove that $f(n+f(n))=n$ by induction. Small cases are true. Suppose that $f(n+f(n))=n,\ \forall n \leq N$. We know that $f(N+1)=N+1-f(f(N))$, and we calculate $f(N+1+f(N+1))=N+1+f(N+1)-f(f(N+f(N+1))\ (0)$. We have two cases: 1. $f(N+1)=f(N)$. Then $f(f(N+f(N+1)))=f(f(N+f(N)))=f(N)=f(N+1)$ which implies that $(0) = N+1$. 2. $f(N+1)=f(N)+1$. Then $f(f(N+f(N+1)))=f(f(N+1+f(N)))=$$f(N+1+f(N)-f(f(N+f(N))))=f(N+1+f(N)-f(N))=f(N+1)$ which implies that $(0)=N+1$. Thus in both cases we have $f(N+1+f(N+1))=N+1$, which proves by induction that the identity is true for all positive integers $n\geq 1$.

pco wrote: amparvardi wrote: Let $f: \mathbb N \to \mathbb N$ be a function such that $f(1)=1$ and \[f(n)=n - f(f(n-1)) \qquad n \geq 2.\] Prove that $f(n+f(n))=n $ for each positive integer $n.$ Note. $\mathbb N$ denotes the set of positive integers. I'm sure it's not the requested solution, but there is a simple way : It's not very difficult to see that $f(x)$ is unique. let then $f(n)=\left\lfloor\frac{2n+2}{1+\sqrt 5}\right\rfloor$ It's rather easy (with some careful casework) to prove that this $f(x)$ matches the two equations. Hence the result. Do you can prove f(x) is unique?

taylorcute56 wrote: Do you can prove f(x) is unique? $f(n)\le n$ $\forall n$ and so, if $f(x)$ is known over $[1,n]$, we also know $f(f(n))$, and so $f(n+1)=n+1-f(f(n))$ is uniquely known. And since $f(n)$ is unique over $[1,1]$, we get that $f(n)$ is unique over $\mathbb N$

benimath wrote: I think I got an idea. It is clear that we can determine all the values of the function, and therefore the function is unique. By checking the first values by hand we see that our function is increasing and it increases with at most $1$ at a time. It is clear that $f(n)\leq n,\ \forall n \in \Bbb{N}$. Now suppose that $f(n) \in \{f(n-1),f(n-1)+1\},\ (\star)$. This can be seen to be true for small $n$. Suppose now that $(\star)$ is true for all $n\leq N$. Then $f(N+1)-f(N)=1-(f(f(N))-f(f(N-1)))$. Let's analyze $h=f(f(N))-f(f(N-1))$. If $f(N)=f(N-1)$ then $h=0$. If $f(N)=f(N-1)+1$ then, because of the inductive hypothesis we need to have $h \in \{0,1\}$. Anyway, $h$ can only take the values $0,1$. This proves by induction that $(\star)$ is true for all positive integers. Now let's try to prove that $f(n+f(n))=n$ by induction. Small cases are true. Suppose that $f(n+f(n))=n,\ \forall n \leq N$. We know that $f(N+1)=N+1-f(f(N))$, and we calculate $f(N+1+f(N+1))=N+1+f(N+1)-f(f(N+f(N+1))\ (0)$. We have two cases: 1. $f(N+1)=f(N)$. Then $f(f(N+f(N+1)))=f(f(N+f(N)))=f(N)=f(N+1)$ which implies that $(0) = N+1$. 2. $f(N+1)=f(N)+1$. Then $f(f(N+f(N+1)))=f(f(N+1+f(N)))=$$f(N+1+f(N)-f(f(N+f(N))))=f(N+1+f(N)-f(N))=f(N+1)$ which implies that $(0)=N+1$. Thus in both cases we have $f(N+1+f(N+1))=N+1$, which proves by induction that the identity is true for all positive integers $n\geq 1$. I do agree. Quite nice direct solution which does not need to compute a closed form for $f(n)$. Congrats !

benimath wrote: I think I got an idea. It is clear that we can determine all the values of the function, and therefore the function is unique. By checking the first values by hand we see that our function is increasing and it increases with at most $1$ at a time. It is clear that $f(n)\leq n,\ \forall n \in \Bbb{N}$. Now suppose that $f(n) \in \{f(n-1),f(n-1)+1\},\ (\star)$. This can be seen to be true for small $n$. Suppose now that $(\star)$ is true for all $n\leq N$. Then $f(N+1)-f(N)=1-(f(f(N))-f(f(N-1)))$. Let's analyze $h=f(f(N))-f(f(N-1))$. If $f(N)=f(N-1)$ then $h=0$. If $f(N)=f(N-1)+1$ then, because of the inductive hypothesis we need to have $h \in \{0,1\}$. Anyway, $h$ can only take the values $0,1$. This proves by induction that $(\star)$ is true for all positive integers. Now let's try to prove that $f(n+f(n))=n$ by induction. Small cases are true. Suppose that $f(n+f(n))=n,\ \forall n \leq N$. We know that $f(N+1)=N+1-f(f(N))$, and we calculate $f(N+1+f(N+1))=N+1+f(N+1)-f(f(N+f(N+1))\ (0)$. We have two cases: 1. $f(N+1)=f(N)$. Then $f(f(N+f(N+1)))=f(f(N+f(N)))=f(N)=f(N+1)$ which implies that $(0) = N+1$. 2. $f(N+1)=f(N)+1$. Then $f(f(N+f(N+1)))=f(f(N+1+f(N)))=$$f(N+1+f(N)-f(f(N+f(N))))=f(N+1+f(N)-f(N))=f(N+1)$ which implies that $(0)=N+1$. Thus in both cases we have $f(N+1+f(N+1))=N+1$, which proves by induction that the identity is true for all positive integers $n\geq 1$. i had the same thing like your process but i used contradiction while induction by plugging in the number between f(n+f(n)) and f(n+1+f(n+1)) depending on whether f(n) or f(n)+1=f(n+1) the rest is the same. i really want to know how pco generated the function.well thanks though(the difference of 1 you see can be proved when you see that f(n+1)>=f(n)for all n.you can prove that if a>b f(a)-f(b)<=(a-b) )

taiiyama wrote: i really want to know how pco generated the function. As I previously said, I remembered an old problem rather similar whose solution was $\left\lfloor\frac x{\varphi}\right\rfloor$ and so I made some trials and found this value which is not very difficult to prove (when you know it )

pco wrote: amparvardi wrote: Let $f: \mathbb N \to \mathbb N$ be a function such that $f(1)=1$ and \[f(n)=n - f(f(n-1)) \qquad n \geq 2.\] Prove that $f(n+f(n))=n $ for each positive integer $n.$ Note. $\mathbb N$ denotes the set of positive integers. I'm sure it's not the requested solution, but there is a simple way : It's not very difficult to see that $f(x)$ is unique. let then $f(n)=\left\lfloor\frac{2n+2}{1+\sqrt 5}\right\rfloor$ It's rather easy (with some careful casework) to prove that this $f(x)$ matches the two equations. Hence the result. I think so... $f(n)=n-\left(\left\lfloor\frac{n+1}{21}\right\rfloor+\left\lfloor\frac{n+3}{21}\right\rfloor+\left\lfloor\frac{n+6}{21}\right\rfloor+\left\lfloor\frac{n+8}{21}\right\rfloor+\left\lfloor\frac{n+11}{21}\right\rfloor+\left\lfloor\frac{n+14}{21}\right\rfloor+\left\lfloor\frac{n+16}{21}\right\rfloor+\left\lfloor\frac{n+19}{21}\right\rfloor\right)$

hxthanh wrote: I think so... $f(n)=n-\left(\left\lfloor\frac{n+1}{21}\right\rfloor+\left\lfloor\frac{n+3}{21}\right\rfloor+\left\lfloor\frac{n+6}{21}\right\rfloor+\left\lfloor\frac{n+8}{21}\right\rfloor+\left\lfloor\frac{n+11}{21}\right\rfloor+\left\lfloor\frac{n+14}{21}\right\rfloor+\left\lfloor\frac{n+16}{21}\right\rfloor+\left\lfloor\frac{n+19}{21}\right\rfloor\right)$ I dont understand what you mean ? Do you mean your function is a solution ? If so, you are wrong ... . Choose for example $n=54$. With your function : $f(n)=f(54)=34$ $f(n-1)=f(53)=33$ $f(f(n-1))=f(33)=21$ $n-f(f(n-1))=54-21=33\ne f(n)$

Thanks for your checked! I'm wrong... ref!

Please correct me... to conjencture that value for the function you need to use the linear aproximation tehnique so you nead that $f(n)\sim{an}$ so $f(n)=n-f(f(n))$ $<=>$ $an\sim{n-a^2n}$ by dividing with n we get that $a^2+a-1=0$ so a =$\frac{1+\sqrt{5}}{2}$ instead of $\frac{2}{1+\sqrt{5}}$ where am i wrong?????

paul1703 wrote: Please correct me... to conjencture that value for the function you need to use the linear aproximation tehnique so you nead that $f(n)\sim{an}$ so $f(n)=n-f(f(n))$ $<=>$ $an\sim{n-a^2n}$ by dividing with n we get that $a^2+a-1=0$ so a =$\frac{1+\sqrt{5}}{2}$ instead of $\frac{2}{1+\sqrt{5}}$ where am i wrong????? In fact, $\frac{1+\sqrt{5}}{2}$ is not root of $a^2+a-1=0$. The two roots are $a_1=\frac{-1-\sqrt 5}2<0$ and $a_2=\frac{-1+\sqrt 5}2=\frac 2{\sqrt 5+1}$

sorry this is the way you conjenctured the solution right?

Amir Hossein wrote: Let $f: \mathbb N \to \mathbb N$ be a function such that $f(1)=1$ and \[f(n)=n - f(f(n-1)) \qquad n \geq 2.\] Prove that $f(n+f(n))=n $ for each positive integer $n.$ Note. $\mathbb N$ denotes the set of positive integers. We prove by induction $f\left( n \right) = k,f\left( {n + 21} \right) = k + 13$

thangtoancvp wrote: We prove by induction $f\left( n \right) = k,f\left( {n + 21} \right) = k + 13$ Dont hesitate to post the proof of your interesting [but unfortunately wrong] claim.

Click to reveal hidden text

benimath wrote: Iwe see that our function is increasing and it increases with at most $1$ at a time. As a matter of a fact, that's what we need to prove, as it's the most difficult part of the problem. If you can prove it, then write the proof please :-P

pco wrote: bigbang195 wrote: $f(2)=\left\lfloor\frac{2.2+2}{1+\sqrt 5}\right\rfloor=2 \not=1$ In my country, $\frac{2.2+2}{1+\sqrt 5}=1.854101966...$ and so $f(2)=\left\lfloor\frac{2.2+2}{1+\sqrt 5}\right\rfloor=1$ That is called real sarcasm! Oh After so many days!

Doesn't the much simpler $$f(n)=\left \lfloor \frac{3(n+1)}{5}\right \rfloor $$work nicely? Oh it doesn't

SPHS1234 wrote: Doesn't the much simpler $$f(n)=\left \lfloor \frac{3(n+1)}{5}\right \rfloor $$work nicely? No. Just try $n=12$ : $f(n)=f(12)=7$ $f(n-1)=f(11)=7$ $f(f(n-1))=f(7)=4$ $n-f(f(n-1))=12-4=8\ne 7=f(n)$

Cool problem. First observe that $f(n) \le n-1$. We will need the following crucial observation. Claim: $f(n) =f(n-1)+1$ or $f(n)=f(n-1)$ Proof: We proceed by induction with the base being trivial. Suppose the claim is true for all $i \le k-1$. We will prove $f(k)=f(k-1)$ or $f(k)=f(k-1)+1$. Note that we have the following identities: $$ f(k) =k-f(f(k-1)) \qquad \text{and} \qquad f(k-1)=k-1-f(f(k-2)) $$If $f(k-1) =f(k-2)$, then obviously $f(f(k-1)) =f(f(k-2))$ meaning that $f(k)=f(k-1)+1$. Otherwise we must have $f(k-1)=f(k-2)+1$. This means above identites can be rewritten as follows: $$ f(k)=k-f(r+1) \qquad \text{and} \qquad f(k-1)=k-1-f(r) $$where $f(k-2) = r$. Using the same idea as before either $f(r+1) =f(r)$ meaning that $f(k)=f(k-1)+1$ or $f(r+1)=f(r)-1$ meaning that $f(k)=f(k-1)$. This proves the claim. Now we return back to our problem. We will prove by induction that $f(n+f(n))=n$ using induction with bases cases being trivial. Suppose that for all $i \le k-1$ we have $f(i+f(i))=i$. Note that: $$ f(k+f(k-1)) =(k+f(k-1)) -f(f(k-1+f(k-1))) =k+f(k-1)-f(k-1) = k $$If $f(k-1)=f(k)$ we are already done, since this means that $f(k+f(k-1))=f(k+f(k)) =k$. Otherwise $f(k)=f(k-1)+1$ menaing that: $$ f(k+f(k-1)) =k = f(k+f(k)-1) $$Observe that in that case: $$ f(k+f(k)) = k+f(k) -f(f(k+f(k)-1)) = k+f(k)-f(k) = k $$as desired. This proves the problem.