IMO6 bijna triviaal?

Opgave - IMO 1977 dag 2 vraag 3

Bewijs dat als $f N \to N$ voldoet aan
$f(n + 1) > f(f(n))$
voor alle $\forall n \in N$, dat dan $f(n) = n $ geldt $\forall n \in N.$
**
Hierbij staat $N$ voor de internationale natuurlijke getallen ( vanaf $1$).

Oplossing

Stel dat het minimum wordt bereikt in $a>1$, dan is $f(f(a-1))< f(a)$, dus gaf $a$ toch niet het minimum. Dus $a=1$. Dus $f(n)> f(1)$ als $n>1$.

Met inductie bewijzen we nu dat de op-$b-1$-na-kleinste waarde wordt bereikt in $b$ alleen.
Stel dat het waar is tot en met $b$.

Veronderstel dat het niet klopt voor $b+1$ en dat er een $n> b+1$ is zodat $f(n)$ de op-$b$-na-kleinste waarde geeft.

Nu is $f(x)> f(b)$ voor $x> b$ wegens de inductiehypothese, dus $f(n-1)> f(b)\geq b$. Stellen we $x=f(n-1)$ hebben we dus $f(f(n-1))> f(b)$.

Omdat $f(f(n-1))< f(n)$ en $f(f(n-1))> f(b)$ gaf $n$ dan toch niet de op-$b$-na-kleinste waarde, contradictie.

Dit betekent dus dat $f(b+1)$ de unieke op-$b$-na-kleinste waarde is.

Hiermee is het bewezen via inductie.

Merk op dat de uitspraak "De op-$b-1$-na-kleinste waarde wordt bereikt in $b$ alleen." niets anders betekent dat de functie strikt stijgend is. Dus $f(n)\geq n$.

Veronderstel nu dat er een $n$ is zodat $f(n)> n$. Dan is wegens de stijgendheid $f(n+1)> f(f(n))\geq f(n+1)$, contradictie.

Dus $f(n)=n$.

Het is een triviale controle op te merken dat deze functie inderdaad voldoet aan de functievergelijking.