1977 IMO Problems/Problem 6

Problem

Let $f(n)$ be a function $f: \mathbb{N}^{+}\to\mathbb{N}^{+}$. Prove that if $$f(n+1) > f(f(n))$$ for each positive integer $n$, then $f(n)=n$.

Solution

We will prove this via induction. First we will prove there is a $t$ such that $f(t)=1$ and then that $t=1$ is the only such solution.

Define the sequence $a_n$ with $a_0>1$ for $a_0\in \mathbb{N}$ and $a_k=f(a_{k-1}-1)$. By the given inequality we have that $f(a_n)>f(a_{n+1})$, this can be used to form a inequality chain of decreasing positive integers: $$f(a_0)>f(a_1)>f(a_2)>...$$ By Infinite Descent, this sequence must terminate, and the only way it can terminate is if we input something into $f$ that is outside of its range. This can only happen if $a_n=1$ since the range and domain of $f$ are the positive integers. Since $a_0\neq 1$, there is a integer $t$ ($a_{n-1}-1$) such that $f(t)=1$.

Now if $t\neq 1$, then $f(t)=1>f(f(t-1))$, which is impossible since $f(f(t-1))\ge 1$ by the range of $f$, so we have $t=1$ is the only time when $f(t)=1$.

Now for the inductive step.

Assume that $f(n)=n$ for all $n and these are the only times these values occur. We will prove that $f(k)=k$ and that this is the only time this value occurs. Define the sequence $a_n$ similarly, except that $a_0>k$, by the reasoning above, there is a $a_m$ such that $f(a_m)=1$, by the inductive assumption, this means that $a_m=f(a_{m-1}-1)=1$, we can repeat the inductive assumption to get that $a_{m-k+1}=k$. This implies that $f(a_{m-k}-1)=k$. Thus, there is a $t$ such that $f(t)=k$.

Now for that $t$, we have $k>f(f(t-1))$, which means that $k+1>t$ by the inductive assumption which implies $t=k$ since we must have $t>k-1$, otherwise $f(t). So $t=k$ is the only time when $f(t)=k$

So the inductive step is complete. Therefore, by induction $f(n)=n$ for all positive integers $n$.