Problem

Source: American Mathematical Monthly

Tags: function, induction, strong induction, algebra proposed, algebra



Given a positive integer number $k$, define the function $f$ on the set of all positive integer numbers to itself by \[f(n)=\begin{cases}1, &\text{if }n\le k+1\\ f(f(n-1))+f(n-f(n-1)), &\text{if }n>k+1\end{cases}\] Show that the preimage of every positive integer number under $f$ is a finite non-empty set of consecutive positive integers.