functievergelijking

Opgave - APMC 2004 dag 3 vraag 1

Bepaal alle functies $f\{1,2,\ldots\}\rightarrow\mathbb Z$ die voldoen aan $f(x+y)=f(x+1)+f(y+1)$ voor alle onderling ondeelbare $x,y\in\{1,2,\ldots\}$.

Oplossing

Bepaal alle functies $f\mathbb N\rightarrow\mathbb Z$ die voldoet aan $f(x+y)=f(x+1)+f(y+1)$ voor elk koppel van coprieme natuurlijke getallen $(x,y)$.

Waarschijnlijk is $\mathbb{N} = \mathbb{N}\setminus\{0\}$, dus het is duidelijk dat $f(1)$ willekeurig is. (Want dan is $x+1,y+1,x+y \geq 2$, $\forall x,y\in\mathbb{N}$.)

Dus we zoeken $f(n)$ voor $n\geq 2$. Schrijf $f(3) = a$ en $f(4) = b$. In alle volgende substituties is $n$ een natuurlijk getal.

Vul $(x,y) = (2n-1,2)$ in: $f(2n+1) = f(2n)+f(3) = f(2n)+a$.

Vul $(x,y) = (2n-3,3)$ in, waarbij $n$ niet deelbaar is door 3: $f(2n) = f(2n-2)+f(4) = f(2n-2)+b$. (Dit impliceert dat $f(6n+2) = f(6n)+b$, zie later.)

Merk op dat $f(6)+f(9) = f(5+8) = f(13) = f(4)+f(11) = b+f(4)+f(9) = 2b+f(9)$, dus $f(6) = 2b$. Vul $(x,y) = (6n-1,6n+1)$ in: $f(12n) = f(6n)+f(6n+2) = f(6n)+f(6n)+b = 2f(6n)+b$. Vul $(x,y) = (6n+1,6n+5)$ in: $f(12n+6) = f(6n+2)+f(6n+6) = f(6n)+f(6n+6)+b$. Uit deze drie observaties valt het eenvoudig te induceren dat $f(6n) = (3n-1)b$.

Hieruit volgt natuurlijk dat $f(6n+2) = f(6n)+b = 3nb$ en $f(6n+4) = f(6n+2)+b = (3n+1)b$. Bijgevolg is $f(2n) = (n-1)b$. En $(x,y) = (2n-1,2)$ invullen, levert dan op dat $f(2n+1) = f(2n)+f(3) = (n-1)b+a$.

Bijgevolg voldoen alle functies van de vorm$$f(n) = \left\{\begin{array}{ll} \left(\frac{n}{2}-1\right)b & \textrm{als } n\textrm{ even is;} \\ \left(\frac{n-1}{2}-1\right)b+a & \textrm{als } n\textrm{ oneven is.}\end{array}\right.$$waarbij $a = f(3)$, $b = f(4)$ en $f(1)$ willekeurig zijn. (Dat deze functies voldoen aan de opgave, is niet moeilijk na te gaan.)