Olympiad Maths Prep

Library / /10 of 22

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.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.