Maths Olympiad Prep

Library / /31 of 214

Algebra Difficulty 5.2 AIME, harder Prove it Belarus

Does there exist a function f:N→Nf: \mathbb{N} \to \mathbb{N} such that
f(f(n+1))=f(f(n))+2n−1 f(f(n+1)) = f(f(n)) + 2^{n-1}
for any positive integer nn? (As usual, N\mathbb{N} stands for the set of all positive integers.)

Solution

Answer: yes.
Note that if function f(x)f(x) satisfy f(f(n))=2n−1f(f(n)) = 2^{n-1} for any positive integer nn, then it satisfy the problem condition f(f(n+1))=f(f(n))+2n−1f(f(n+1)) = f(f(n)) + 2^{n-1} as well.
It is well known that there exist infinitely many functions f:N→Nf: \mathbb{N} \to \mathbb{N} such that f(f(n))=2n−1f(f(n)) = 2^{n-1} for all positive integers nn.

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.