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}$ .

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

Page

Toolbox

Search

2002 Pan African MO Problems/Problem 1

Problem

Solution

See Also