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$.
Problem
Source: Pan African 2002
Tags: function
nr1337
20.08.2005 15:42
Let x be the integer such that f(x) = 1. Then f(f(x)) = f(1) = f(x)+1 = 2.
Similarly, f(2) = 3
f(3)=4
etc.
f(n) = n+1 for n > 0.
However, this means for n>0, f(n)>1. However, we know that there is an integer x such that f(x)=1. Since it can't be greater than zero and it must be non-negative, x=0 and f(0) = 1.
So f(n)=n+1 for all non-negative integers n.
K81o7
20.08.2005 17:30
i think in order to get $f(f(f(n)))-f(f(n))=f(f(n))-f(n)$ it has to be linear. Thus, in order to have a minimum, it would have to be at 0 (because otherwise it wouldn't be linear) then it's $f(n)=n+1$. Basically we have $f^{x+1}(n)=f(n)+x$ so it has to be $f(n)=n+1$.