|
|
| Line 2: |
Line 2: |
| | | | |
| | ==Solution== | | ==Solution== |
| − |
| |
| − | This is very beautiful problem.
| |
| − |
| |
| − | I should start with some observation,
| |
| − |
| |
| − | <math>f(f(1))=f(1)+1=3=f(2)</math>.
| |
| − |
| |
| − | <math>f(f(2))=f(2)+2=5=f(3)</math>.
| |
| − |
| |
| − | [color=#f00][u]Claim(1):[/u][/color] <math>f(f_N)=f_{N+1}</math>.Here <math>f_n</math> is <math>n</math> th febonacchi number.
| |
| − |
| |
| − | [i]Proof.[/i] we have seen this is true for <math>N=1,2</math> assuming its true for <math>N=k</math> we can conclude,
| |
| − |
| |
| − | <cmath>f(f_{k+1})=f(f(f_k))=f(f_k)+f_k=f_{k+1}+f_k= f_{k+2}</cmath>.
| |
| − |
| |
| − | it is very well know that <math>\lim_{n\to\infty} \frac{f_{n+1}}{f_n} = \phi (\textcolor{blue}{\text{Golden ratio}})</math>.
| |
| − |
| |
| − | so we can see that for large <math>N</math> ,
| |
| − | <math>f(N)\sim [\phi .N]</math>.
| |
| − |
| |
| − | To see why the above observation is true we have to look the given condition we have <cmath>2=f(1)<f(2)<f(3)=5<f(4)<f(5)=8</cmath>
| |
| − | now clearly <math>f(4)</math> can be either <math>6</math> or <math>7</math>.here <math>[\phi .4]= 6</math> so difference is not large .
| |
| − |
| |
| − | From here we can guess <math>f(n)=[\phi.n+k]</math> can be a possible solution. where <math>0<k<1</math>.
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | \begin{tabular}{lllll}
| |
| − | \hline
| |
| − | \multicolumn{1}{|l|}{{\color{blue} n}} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{4} \\ \hline
| |
| − | \multicolumn{1}{|l|}{{\color{blue} <math>[\phi.n]</math>}} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{4} & \multicolumn{1}{l|}{6} \\ \hline
| |
| − | \multicolumn{1}{|l|}{{\color{blue} f(n)}} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{5} & \multicolumn{1}{l|}{6,7} \\ \hline
| |
| − | & & & &
| |
| − | \end{tabular}
| |
| − | If we put <math>k=0.4</math> on that we must get value of <math>[\phi.n+0.4]=2=f(1)</math> and it will same for <math>f(3)</math> as well.
| |
| − |
| |
| − | Now look into the following table,
| |
| − |
| |
| − | \begin{tabular}{lllll}
| |
| − | \hline
| |
| − | \multicolumn{1}{|l|}{{\color{blue} n}} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{4} \\ \hline
| |
| − | \multicolumn{1}{|l|}{{\color{blue} <math>[\phi.n+0.4]</math>}} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{5} & \multicolumn{1}{l|}{6} \\ \hline
| |
| − | \multicolumn{1}{|l|}{{\color{blue} f(n)}} & \multicolumn{1}{l|}{2} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{5} & \multicolumn{1}{l|}{6or7} \\ \hline
| |
| − | & & & &
| |
| − | \end{tabular}
| |
| − |
| |
| − | From here I should my final claim which finish this problem.
| |
| − |
| |
| − | [color=#960000][b][u]Claim(2):[/u][/b][/color] <math>f(n)=[\phi.n +0.4]</math> works.
| |
| − |
| |
| − | [color=#000][i][b]proof.[/b][/i][/color] At first of all notice that <math>[\phi.(n+1)+0.4]\ge [\phi.n+0.4]+[\phi]>[\phi.n +0.4]</math>.
| |
| − |
| |
| − | Now assume that <math>g:\mathbb{N}\to \mathbb{N}</math> such that <math>g(n)=[\phi.n +0.4]</math>. we hane <math>g(n+1)>g(n)</math>.
| |
| − | Now,
| |
| − | <cmath> g(g(n))=[\phi.g(n) +0.4] =[\phi.([\phi.n +0.4]) +0.4]</cmath>
| |
| − |
| |
| − | <cmath> <[\phi.[(\phi.n +0.4) +0.4] =\phi ^2 .n +0.4+0.4\times \phi</cmath>
| |
| − |
| |
| − | <cmath>= [\phi .n +n+0.4+0.4\times \phi] (\text{this is because of} \phi ^2 -\phi -1=0)</cmath>
| |
| − |
| |
| − | <cmath>\le [\phi .n +0.4]+[n+1+0.4\times \phi ] (\text{I used this fact} [x+y]\le [x]+[y+1])</cmath>
| |
| − |
| |
| − | <cmath> = g(n)+n+1 (\text{here } 0.4\times \phi \sim 0.64 ) </cmath>
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | Now it is time to find out lower bound.
| |
| − |
| |
| − | <cmath>g(g(n)) > [\phi.(\phi.n +0.4-1) +0.4]</cmath>
| |
| − |
| |
| − | <cmath>=[\phi^2.n +0.4 -0.6\times \phi]</cmath>
| |
| − |
| |
| − | <cmath> =[\phi .n +n+0.4-\phi \times 0.6]</cmath>
| |
| − |
| |
| − | <cmath>\ge [\phi .n +0.4]+[n-\phi \times 0.6]</cmath>
| |
| − |
| |
| − | <cmath>=g(n)+n-1</cmath>
| |
| − |
| |
| − | So only possibility is <math>g(g(n))=g(n)</math>.
| |
| − |
| |
| − | Again notice that <math>g(1)=2</math>.
| |
| − |
| |
| − | So ,<math>g(n)=f(n)</math> can be a solution to <math>f</math>.
| |
| − |
| |
| − | So, Yes there exists a function as defined in the question.
| |
