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<k$ 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)<k$ . 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$ .

Page

Toolbox

Search

1977 IMO Problems/Problem 6

Problem

Solution