Library / Belarusian Mathematical Olympiad /29 of 208

Belarusian Mathematical Olympiad

Algebra Difficulty 5.2 AIME, harder Prove it Belarus

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

Solution

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

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.