## Task 3B - 271233B

Let $f$ be the function defined for all ordered pairs $(x ; y)$ of natural numbers $x, y$ that satisfies the following equations (1), (2), (3) for all natural numbers $x, y$:

$$
\begin{aligned}
f(0, y) & =y+1 \\
f(x+1,0) & =f(x, 1) \\
f(x+1, y+1) & =f(x, f(x+1, y))
\end{aligned}
$$

Determine a) the function value $f(3,3)$, b) the function value $f(4,2)$.

Hint: If necessary, the specification of a sought function value can be given by a computational expression with concretely specified operations, if the numerical evaluation of these operations without computational aids would require an excessively long computation time.

1. Claim: For all $y=0,1,2, \ldots$ it holds that
$$
f(1, y)=y+2
$$

Proof by complete induction:

I. According to (2) and (1), $f(1,0)=f(0,1)=2$.

II. According to (3), from the induction hypothesis, for some $y$ (4) holds, and from (1)

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

thus (4) with $y+1$ instead of $y$.

2. Claim: For all $y=0,1,2, \ldots$

$$
f(2, y)=2 y+3
$$

Proof:

I. According to (2) and (4), $f(2,0)=f(1,1)=3$.

II. According to (3), from the induction hypothesis, for some $y$ (5) holds, and from (4)

$$
f(2, y+1)=f(1, f(2, y))=f(1,2 y+3)=2 y+5=2(y+1)+3
$$

3. Claim: For all $y=0,1,2, \ldots$

$$
f(3, y)=2^{y+3}-3
$$

Proof:

I. According to (2) and (5), $f(3,0)=f(2,1)=5=2^{3}-3$.

II. According to (3), from the induction hypothesis, for some $y$ (6) holds, and from (5)

$$
f(3, y+1)=f(2, f(3, y))=f\left(2,2^{y+3}-3\right)=2\left(2^{y+3}-3\right)+3=2^{(y+1)+3}-3
$$

a) From (6), $f(3,3)=2^{6}-3=61$.

b) From (2), (3), and (6),

$$
\begin{aligned}
& f(4,0)=f(3,1)=2^{4}-3=13 \\
& f(4,1)=f(3, f(4,0))=f(3,13)=2^{16}-3=65533 \\
& f(4,2)=f(3, f(4,1))=f(3,65533)=2^{65533}-3
\end{aligned}
$$

## Adopted from $[5]$