1

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!

Alex
  • 649

1 Answers1

1

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$

S.C.B.
  • 22,768