$f(n)=0$ voldoet duidelijk, nu zoeken we nog andere functies.
$(0,0)$ invullen geeft $f(0)=0$.
$(0,n)$ geeft dan $f(f(n))=f(n)$.
Dus $f(m+f(n))=f(m)+f(n)$.
Met inductie is eenvoudig in te zien dat $f(m+kf(n))=f(m)+kf(n)$ voor $k\in\mathbb N$. (In het bijzonder voor $m=0$: $f(kf(n))=kf(n)$).
Stel dat $a$ en $b$ twee functiewaarden zijn, niet beide $0$ (die kunnen we vinden wegens de veronderstelling dat $f(n)$ niet steeds $0$ is want die oplossing hadden we al), en dat $p,q$ natuurlijke getallen zijn zodat $\text{ggd}(a,b)|p-q$.
Dan zijn er natuurlijke getallen $x,y>0$ zodat $p-q=yb-xa$ wegens Bézout.
Dan is $f(p)+xa=f(p+xa)=f(q+yb)=f(q)+yb$ dus $f(p)-p=f(q)-q=c$. Als we nu $g(n)=f(n)-n$ stellen, hebben we dus dat $g(n)$ periodiek is met als periode een deler van $\text{ggd}(a,b)$.
Stel nu $\text{ggd}(f(n))=d$, waarbij we de ggd nemen over alle functiewaarden.
$g(n)$ is dus periodiek met als periode een deler van $d$.
Dan kan $g(n)$ maximaal $d$ verschillende waarden $r_0,r_1,\cdots,r_{d-1}$ aannemen.
We stellen daarom $g(0)=r_0,g(1)=r_1,\cdots,g(d-1)=r_{d-1}$. Merk op dat $r_0=0$ omdat we $f(0)=0$ hadden.
En aangezien $d|f(n)$ is $d|g(n)+n$, dus $d|r_i+i$ zodat $r_i=k_id-i$ voor $i=0,1,\cdots,d-1$, en met $k_i\geq0$ (omdat $k_id=f(i)$).
Dit vormt dan meteen ook de andere oplossing:
Zij $d$ een natuurlijk getal groter dan $0$ en $r_0,r_1,\cdots r_{d-1}$ een rij natuurlijke getallen zodat $r_i=k_id-i$ voor $i=0,1,\cdots,d-1$, dan is dus voor een natuurlijk getal $x+yd$ met $0\leq x< d$ en $y\in\mathbb N$, $f(x+yd)=r_x+x+yd$.
Tenslotte controleren we deze oplossing.
Stel $m=x_1+y_1d$ en $n=x_2+y_2d$.
Dan is $f(m)=r_{x_1}+x_1+y_1d$ en $f(n)=r_{x_2}+x_2+y_2d$. Deze functiewaarden zijn deelbaar door $d$ wegens $d|r_i+i$.
Dus $f(m+f(n))=f(m+r_0+0+kd)=f(x_1+(y_1+k)d)=r_{x_1}+x_1+(y_1+k)d$ $=r_{x_1}+r_{x_2}+x_1+x_2+y_1d+y_2d$ met $kd=f(n)$.
Anderzijds is $f(f(m))+f(n)=f(ld)+f(n)=(r_0+0+ld)+f(n)$ $=r_{x_1}+r_{x_2}+x_1+x_2+y_1d+y_2d$ met $ld=f(m)$.
En we hebben dat beide leden gelijk zijn.
Hiermee hebben we alle functies gevonden die voldoen en bewezen dat ze inderdaad voldoen aan de functievergelijking.
Oplossing
$f(n)=0$ voldoet duidelijk, nu zoeken we nog andere functies.
$(0,0)$ invullen geeft $f(0)=0$.
$(0,n)$ geeft dan $f(f(n))=f(n)$.
Dus $f(m+f(n))=f(m)+f(n)$.
Met inductie is eenvoudig in te zien dat $f(m+kf(n))=f(m)+kf(n)$ voor $k\in\mathbb N$. (In het bijzonder voor $m=0$: $f(kf(n))=kf(n)$).
Stel dat $a$ en $b$ twee functiewaarden zijn, niet beide $0$ (die kunnen we vinden wegens de veronderstelling dat $f(n)$ niet steeds $0$ is want die oplossing hadden we al), en dat $p,q$ natuurlijke getallen zijn zodat $\text{ggd}(a,b)|p-q$.
Dan zijn er natuurlijke getallen $x,y>0$ zodat $p-q=yb-xa$ wegens Bézout.
Dan is $f(p)+xa=f(p+xa)=f(q+yb)=f(q)+yb$ dus $f(p)-p=f(q)-q=c$. Als we nu $g(n)=f(n)-n$ stellen, hebben we dus dat $g(n)$ periodiek is met als periode een deler van $\text{ggd}(a,b)$.
Stel nu $\text{ggd}(f(n))=d$, waarbij we de ggd nemen over alle functiewaarden.
$g(n)$ is dus periodiek met als periode een deler van $d$.
Dan kan $g(n)$ maximaal $d$ verschillende waarden $r_0,r_1,\cdots,r_{d-1}$ aannemen.
We stellen daarom $g(0)=r_0,g(1)=r_1,\cdots,g(d-1)=r_{d-1}$. Merk op dat $r_0=0$ omdat we $f(0)=0$ hadden.
En aangezien $d|f(n)$ is $d|g(n)+n$, dus $d|r_i+i$ zodat $r_i=k_id-i$ voor $i=0,1,\cdots,d-1$, en met $k_i\geq0$ (omdat $k_id=f(i)$).
Dit vormt dan meteen ook de andere oplossing:
Zij $d$ een natuurlijk getal groter dan $0$ en $r_0,r_1,\cdots r_{d-1}$ een rij natuurlijke getallen zodat $r_i=k_id-i$ voor $i=0,1,\cdots,d-1$, dan is dus voor een natuurlijk getal $x+yd$ met $0\leq x< d$ en $y\in\mathbb N$, $f(x+yd)=r_x+x+yd$.
Tenslotte controleren we deze oplossing.
Stel $m=x_1+y_1d$ en $n=x_2+y_2d$.
Dan is $f(m)=r_{x_1}+x_1+y_1d$ en $f(n)=r_{x_2}+x_2+y_2d$. Deze functiewaarden zijn deelbaar door $d$ wegens $d|r_i+i$.
Dus $f(m+f(n))=f(m+r_0+0+kd)=f(x_1+(y_1+k)d)=r_{x_1}+x_1+(y_1+k)d$ $=r_{x_1}+r_{x_2}+x_1+x_2+y_1d+y_2d$ met $kd=f(n)$.
Anderzijds is $f(f(m))+f(n)=f(ld)+f(n)=(r_0+0+ld)+f(n)$ $=r_{x_1}+r_{x_2}+x_1+x_2+y_1d+y_2d$ met $ld=f(m)$.
En we hebben dat beide leden gelijk zijn.
Hiermee hebben we alle functies gevonden die voldoen en bewezen dat ze inderdaad voldoen aan de functievergelijking.