Let $f\colon \mathbb N\times \mathbb Z \to \mathbb Z$ defined by
- $f(x,0)=x$ for all $x\in \mathbb N$
- $f(0,y)=2y$ for all $ y \in \mathbb Z$
- $x\gt0$ and $y\lt0$$\implies f(x,y)=2y$
- $x\gt0$ and $y\gt0$$\implies f(x,y)=f(x-1, f(x,y-1))$.
Compute $f(3,2)$.
I've restarted this problem several times and always seem to get an incredibly long series of steps that never seem to end. I start with
$f(3,2)=f(2,f(3,1))=f(2,f(2,f(3,0)))=f(2,f(2,3))=....$
and then it goes on for pages. There must be something I'm missing!
Let $f(1,x)=g(x)$.
Note that $$g(x)=f(1,x)=f(0, f(1, x-1))=2f(1,x-1)=2g(x-1)$$
Since $g(0)=1$ we conclude that for all non-negative integers $x$, $g(x)=2^{x}$.
Now let $f(2,x)=h(x)$.
Note that since $$g(x)=f(2,x)=f(1,f(2,x-1))=2^{f(2,x-1)}=2^{g(x-1)}$$
Since $h(0)=2$, we recursively see that $h(x)=2\uparrow \uparrow (x+1)$ and in particular $h(3)=65536$ where $\uparrow$ is Knuth's up-arrow notation.
Since $f(3,2)=f(2,h(3))=h(h(3))$, we have that $f(3,2)=2 \uparrow \uparrow 65537$