1993 IMO Problems/Problem 5

Problem

Solution

This is very beautiful problem.

I should start with some observation,

$f(f(1))=f(1)+1=3=f(2)$ .

$f(f(2))=f(2)+2=5=f(3)$ .

[color=#f00][u]Claim(1):[/u][/color] $f(f_N)=f_{N+1}$ .Here $f_n$ is $n$ th febonacchi number.

[i]Proof.[/i] we have seen this is true for $N=1,2$ assuming its true for $N=k$ we can conclude,

$f(f_{k+1})=f(f(f_k))=f(f_k)+f_k=f_{k+1}+f_k= f_{k+2}$ .

it is very well know that $\lim_{n\to\infty} \frac{f_{n+1}}{f_n} = \phi (\textcolor{blue}{\text{Golden ratio}})$ .

so we can see that for large $N$ , $f(N)\sim [\phi .N]$ .

To see why the above observation is true we have to look the given condition we have $2=f(1)<f(2)<f(3)=5<f(4)<f(5)=8$

now clearly  can be either  or .here  so difference is not large .

From here we can guess $f(n)=[\phi.n+k]$ can be a possible solution. where $0<k<1$ .

\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} $[\phi.n]$ }} & \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 $k=0.4$ on that we must get value of $[\phi.n+0.4]=2=f(1)$ and it will same for $f(3)$ 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} $[\phi.n+0.4]$ }} & \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] $f(n)=[\phi.n +0.4]$ works.

[color=#000][i][b]proof.[/b][/i][/color] At first of all notice that $[\phi.(n+1)+0.4]\ge [\phi.n+0.4]+[\phi]>[\phi.n +0.4]$ .

Now assume that $g:\mathbb{N}\to \mathbb{N}$ such that $g(n)=[\phi.n +0.4]$ . we hane $g(n+1)>g(n)$ . Now, $g(g(n))=[\phi.g(n) +0.4] =[\phi.([\phi.n +0.4]) +0.4]$