Compute f4 1981 given that f0 y y1 fx1 0 fx 1 fx1 y1 fx f

Compute f(4, 1981), given that f(0, y) = y+1 f(x+1, 0) = f(x, 1) f(x+1, y+1) = f(x, f(x+1), y) Show all calculations.

solution:

f(1,n) = f(0,f(1,n-1)) = 1 + f(1,n-1).

So f(1,n) = n + f(1,0) = n + f(0,1) = n + 2.

f(2,n) = f(1,f(2,n-1)) = f(2,n-1) + 2.

So f(2,n) = 2n + f(2,0) = 2n + f(1,1) = 2n + 3

f(3,n) = f(2,f(3,n-1)) = 2f(3,n-1) + 3.

Let u_n = f(3,n) + 3, then u_n = 2u_n-1. Also u₀ = f(3,0) + 3 = f(2,1) + 3 = 8.

So u_n = 2ⁿ⁺³, and f(3,n) = 2ⁿ⁺³ - 3

f(4,n) = f(3,f(4,n-1)) = 2^f(4,n-1)+3 - 3.

f(4,0) = f(3,1) = 2⁴ - 3 = 13.

We calculate two more terms to see the pattern: f(4,1) = 2^2⁴ - 3, f(4,2) = 2^{2^2⁴} - 3.

In fact it looks neater if we replace 4 by 2², so that f(4,n) is a tower of n+3 2s less 3.