2002 Pan African MO Problems/Problem 1

Problem

Find all functions $f: N_0 \to N_0$, (where $N_0$ is the set of all non-negative integers) such that $f(f(n))=f(n)+1$ for all $n \in N_0$ and the minimum of the set $\{ f(0), f(1), f(2) \cdots \}$ is $1$.

Solution

Let $n$ be the minimum of function $f$, so $f(n) = 1$. Substituting $f(n)$ means that $f(1) = 1+1 = 2$. Additionally, substituting $n = 1$ means that $f(2) = 2+1 = 3$, and substituting $n = 2$ means that $f(3) = 3+1 = 4$.


It seems as if $f(n) = n+1$ for $n \ge 1$. To prove this, we can use induction. The base case is covered because by substituting $f(n) = 1$, we get $f(1) = 1+1 = 2$. For the inductive step, assume that $f(n) = n+1$. Substituting $f(n)$ means that $f(n+1) = (n+1) + 1$, so the inductive step holds.


Therefore, $f(n) = n+1$ for $n \ge 1$, and since $f$ is increasing when $n \ge 1$ and $f(1) = 2$, $f(n)$ can not equal $1$ if $n \ge 1$. The only possible value of $n$ left for $f(n)$ to equal $1$ is $0$.


Since $f(0) = 0+1 = 1$, the only function $f$ that satisfies the requirements is $\boxed{f(n) = n+1}$.

See Also

2002 Pan African MO (Problems)
Preceded by
First Problem
1 2 3 4 5 6 Followed by
Problem 2
All Pan African MO Problems and Solutions