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 4 of 7: Solve the

x=3

level

Previous step Next step

In plain words

Each level of the recursion is one operation 'up' from the last: addition becomes doubling, and doubling will become towering.

f(3,0)+3=8=2^{3},\quad f(3,y+1)+3=2\big(f(3,y)+3\big) \implies f(3,y)+3=2^{\,y+3}

Detailed analysis

By rule (2) and Step 3, $f(3,0)=f(2,1)=2(1)+3=5$ , so $f(3,0)+3=8=2^3$ . By rule (3) and Step 3, $f(3,y+1)=f(2,f(3,y))=2f(3,y)+3$ , so $f(3,y+1)+3=2(f(3,y)+3)$ ; this doubling recurrence starting at $8=2^3$ gives $f(3,y)+3=2^{y+3}$ .