Funksjonalligning

[jhoe06]

En funksjon $ f(x, y) $ tilfredsstiller følgende for alle heltall $ x, y \geq 0 $:

1. $f(0, y) = y + 1$
2. $f(x+1, 0) = f(x, 1)$
3. $f(x+1, y+1) = f(x, f(x+1, y))$

Finn $ f(4, 1981) $.

[Brahmagupta]

Tanken er at vi har gitt [tex]f(i,y)[/tex] og bruker denne sammenhengen sammen med den tredje ligningen til å
finne en rekursjonsligning for [tex]f(i+1,y)[/tex]. Vi finner deretter [tex]f(i+1,0)[/tex] ved ligning 2 og deretter finner
formelen for [tex]f(i+1,y)[/tex] som bevises ved induksjon (detaljene rundt dette har jeg utelatt). Dette gjøres fire
ganger slik at vi har funnet [tex]f(4,y)[/tex] og dermed også [tex]f(4,1981)[/tex].

Setter [tex]x=0[/tex] i 3)
[tex]f(1,y+1)=f(0,f(1,y))=f(1,y)+1[/tex]
[tex]f(1,0)=f(0,1)=2[/tex]
[tex]f(1,y)=y+2[/tex].

[tex]f(2,y+1)=f(1,f(2,y))=f(1,y)+2[/tex]
[tex]f(2,0)=f(1,1)=3[/tex]
[tex]f(2,y)=2y+3[/tex]

[tex]f(3,0)=f(2,1)=5[/tex]
[tex]f(3,y+1)=f(2,f(3,y))=2f(3,y)+3[/tex]
[tex]f(3,y)=2^{y+3}-3[/tex]

[tex]f(4,0)=f(3,1)=2^4-3=2^{2^2}-3[/tex]
[tex]f(4,y+1)=2^{f(4,y)+3}-3[/tex]

[tex]f(4,y)=2^{2^{2^{.^{.^{.^2}}}}}-3[/tex] hvor det er [tex]y+3[/tex] 2-tall i potenstårnet.

Dermed har vi at [tex]f(4,1981)=2^{2^{2^{.^{.^{.^2}}}}}-3[/tex] med 1984 2-tall i potenstårnet.

[jhoe06]

Ser bra ut, jeg løste den på nøyaktig samme måte. Oppgaven er fra IMO 1981.