Find all injection functions f:N→N such that f(f(n))≤2n+f(n),∀n∈N.
Solution
Let f be the solution. Then f(f(n))≤max{n,f(n)},∀n∈N.(∗) Let fk(a)=kf(f(...f(a))). Now there is a such that a>f(a). Then f2(a)<a; by induction to k it's easy to prove that fk(a)<a,∀k>0.(1) Because the set {1,2,...,a−1} is finite, there is i,j such that 0<i<j and f′(a)=f′(a)=f′(fj−i(a)). The function f is injection so fj−i(a)=a, which is contradiction to (1). Then a≤f(a),∀a>0(2) and f(a)≤f(f(a)),∀a∈N. On another side, from (*) and (2) we have f(f(a))≤max{a,f(a)}=f(a) i.e. f(f(a))=f(a). Finally f(a)=a,∀a∈N. So f(n)=n,∀n∈N.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.