MathLabs

Problem 5

Let N={1,2,3,…}\mathbb{N}=\{1,2,3,\ldots\}. Determine whether there exists a strictly increasing function f:N↦Nf:\mathbb{N}\mapsto\mathbb{N} such that (i) f(1)=2f(1)=2; (ii) f(f(n))=f(n)+nf(f(n))=f(n)+n, (n∈N)(n\in\mathbb{N}).
Step 1 of 5: Define the candidate
Previous stepNext step
In plain words

The golden ratio is the slope whose self-composition reproduces addition.

φ=1+52,f(n)=⌊φn+φ−1⌋\varphi=\frac{1+\sqrt5}{2},\qquad f(n)=\lfloor\varphi n+\varphi-1\rfloor
Detailed analysis

Let phi be the golden ratio and define f by the displayed floor formula. Since phi is greater than 1, increasing n by 1 increases the inside by more than 1, so f is strictly increasing.