MathDB
Preimage is finite non-empty set of consecutive naturals

Source: American Mathematical Monthly

April 9, 2012
functioninductionstrong inductionalgebra proposedalgebra

Problem Statement

Given a positive integer number kk, define the function ff on the set of all positive integer numbers to itself by f(n)={1,if n≤k+1f(f(n−1))+f(n−f(n−1)),if n>k+1f(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 ff is a finite non-empty set of consecutive positive integers.
Back to ProblemsView on AoPS