Problem 6

The function

f(x,y)

satisfies

f(0,y) = y+1,

f(x+1,0) = f(x,1),

f(x+1,y+1) = f\big(x, f(x+1,y)\big)

for all non-negative integers

x,y

. Determine

f(4,1981)

Step 1 of 7: Solve the

x=1

level, base and step

Previous step Next step

In plain words

At $x=1$ the recursion just becomes 'add one repeatedly', starting from $2$ .

f(1,0)=f(0,1)=2,\quad f(1,y+1)=f(0,f(1,y))=f(1,y)+1

Detailed analysis

Using rule (2) with $x=0$ gives $f(1,0)=f(0,1)=1+1=2$ by rule (1). Using rule (3) with $x=0$ gives $f(1,y+1)=f(0,f(1,y))=f(1,y)+1$ by rule (1) again, so $f(1,\cdot)$ increases by exactly $1$ at each step.