Finding formulas for a recursive function from $\Bbb{N} \times \Bbb{N}$ to $\Bbb{N}$

Question

Define $B: \Bbb{N} \times \Bbb{N} \to \Bbb{N}$ by the recursive formula:

$$B(0,x) = x+1$$ $$B(y+1,0) = B(y,1)$$ $$B(y +1,x +1) = B(y, B(y +1,x))$$

The assignment asks me to find simple formulas for $B(1,x), B(2,x) \text{ and } B(3,x)$. I think I could do this if I understood how this function actually works.

I've tried sticking in natural numbers but I don't quite follow. If $x=1$ and $y=2$,

$B(0,1) = 1+1 =2$

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

$B(y +1,x +1) = B(2 +1,1 +1) = B(3,2) = B(2, B(2 +1,1)) = B(2, B(3,1))$

What is $B(2,1)$ and $B(3,1)$? Do I even need to have values for those to understand the problem?

Answer 1

I think you're picturing it backwards, pluggin the values you care about into the $x$ and $y$ in the definition. That's not going to work: instead, you want to use the definition to "build up to" the values you care about.

For example, let's say we want to compute $B(2,0)$. We have: $$B(2,0)=B(1+1,0)\color{blue}{=}B(1,1)=B(0+1,0+1)\color{red}{=}B(0, B(1,0))$$ where again the red equality comes from the third clause of the definition (with $y=0,x=0$) and the blue equality comes from the second clause of the definition (with $y=1$).

So now we have a "sub-computation" to perform: we have to compute $B(1,0)$ before we can finish computing $B(2,0)$. As before we have $$B(1,0)=B(0+1,0)\color{blue}{=}B(0,1)\color{green}{=}2$$ where the blue equality comes from the second clause of the definition (with $y=0$) and the green equality comes from the first clause of the definition (with $x=1$). Note that this is new: we couldn't apply the first clause of the definition until now.

And now we're ready to finish our computation of $B(2,0)$. We already showed that $B(2,0)=B(0,B(1,0))$, so by our above sub-computation we get $$B(2,0)=B(0,2)\color{green}{=}3$$ where again the green equality comes from the first clause of the definition (with $x=2$).

---

Computing $B(2,1)$ takes longer, but the idea is the same. At each stage, apply one of the relevant clauses to break down your current $B$-expression into one with smaller entries. When one entry or the other is zero, you use either the first or second clause; if neither coordinate is zero, you use the third clause. The values of $x$ and $y$ you consider change with each step. It might help to rephrase the clauses in terms of subtraction, so that e.g. the third clause would be

"If $u,v>0$ then $B(u,v)=B(u-1, B(u, v-1))$,"

but this is somewhat messier in the long run.

Answer 2

Suppose we know all the $B(y, \dots)$ values for a given value of $y$. The third rule tells us that if we know $B(y+1,x)$ then we can find $B(y+1,x+1)$ by using $B(y+1,x)$ as an index into the $B(y,\dots)$ values.

If we knew $B(y+1,0)$ then we could use this to find $B(y+1,1)$, then use this to find $B(y+1,2)$ and so on. But the second rule tells us how to find $B(y+1,0)$. And the first rule tells us all the $B(0,\dots)$ values to get us started.

So $B(0,\dots)=1,2,3,4,\dots$. And $B(1,0)=B(0,1)=2$. So ...

$B(1,1) = B(0,2) =3\\B(1,2) = B(0,3) =4\\B(1,3) = B(0,4) =5$

and so on. We see a pattern emerging ... $B(1,x)=x+2$.

And now that we know $B(1,\dots)$ we can use the same method to find $B(2,\dots)$ ...

Answer 3

It is a good approach to see some values of the function $B(y,x)$ for some concrete $(y,x) \in \mathbb{N} \times \mathbb{N}$. But how to compute them in a smart way?

The recursive definition of $B$ suggests to fix $y$ and vary $x$. Indeed, $B(2,1) = B(1,B(2,0)) = B(1, B(1,1))$ and we can easily compute the value of $z = B(1,1)$, but we don't have an explicit definition of $B(1,z)$. And if $z= 103$? How many recursive steps are needed to compute the value of $B(2,1)$? It seems like that, in order to know the value of $B(2,1)$, it would be better to have an explicit definition of $B(1,x)$.

An analogous discourse holds for computing the value of $B(3,1)$: it would be better to have an explicit definition of $B(2,x)$.

---

We perfectly know the definition of $B$ for $y=0$.

$$ B(0,x) = x+ 1 \qquad \text{for every } x \in \mathbb{N}. $$

So, let's start by fixing $y =1$ and varying $x \in \mathbb{N}$.

\begin{align} B(1,0) &= B(0,1) = 1+1 = 2 \\ B(1,1) &= B(0,B(1,0)) = B(1,0) + 1 = 2+1 = 3 \\ B(1,2) &= B(0,B(1,1)) = B(1,1) + 1 = 3+1 = 4 \\ B(1,3) &= B(0,B(1,2)) = B(1,2) + 1 = 4+1 = 5 \end{align}

So, we "suspect" that $B(1,x) = x+2$. Let us verify it with a proof by induction on $x \in \mathbb{N}$.

Base case ($x = 0$). We have just shown that $B(1,0) = 2 = 0 + 2$.

Inductive step. We suppose that $B(1,x) = x + 2$ (inductive hypothesis). We have to show that $B(1,x+1) = (x+1) + 2 = x + 3$. According to the definition of $B$,

$$ B(1,x+1) = B(0,B(1,x)) = B(1,x) + 1 = (x+2) + 1 = x+3. $$

---

We have found an explicit definition of $B(1,x)$ for every $x \in \mathbb{N}$.

$$ B(1,x) = x + 2 $$

We can now compute some examples for $B(2,x)$.

\begin{align} B(2,0) &= B(1,1) = 1 + 2 = 3 \\ B(2,1) &= B(1,B(2,0)) = B(2,0) + 2 = 3 + 2 = 5 \\ B(2,2) &= B(1,B(2,1)) = B(2,1) + 2 = 5 + 2 = 7 \\ B(2,3) &= B(1,B(2,2)) = B(2,2) + 2 = 7 + 2 = 9 \end{align}

So, we "suspect" that $B(2,x) = 2x+3$. Let us verify it with a proof by induction on $x \in \mathbb{N}$.

Base case ($x = 0$). We have just shown that $B(2,0) = 3 = 2 \cdot 0 + 3$.

Inductive step. We suppose that $B(2,x) = 2x + 3$ (inductive hypothesis). We have to show that $B(2,x+1) = 2(x+1) + 3 = 2x + 5$. According to the definition of $B$,and since we have the explicit definition of $B(1,x)$,

$$ B(2,x+1) = B(1,B(2,x)) = B(2,x) + 2 = (2x+3) + 2 = 2x+5. $$

---

We have found an explicit definition of $B(2,x)$ for every $x \in \mathbb{N}$.

$$ B(2,x) = 2x + 3 $$

We can now compute some examples for $B(3,x)$.

\begin{align} B(3,0) &= B(2,1) = 2\cdot 1 + 3 = 5 \\ B(3,1) &= B(2,B(3,0)) = 2B(3,0) + 3 = 2 \cdot 5 + 3 = 13 \\ B(3,2) &= B(2,B(3,1)) = 2B(3,1) + 3 = 2 \cdot 13 + 3 = 29 \\ B(3,3) &= B(2,B(3,2)) = 2B(3,2) + 3 = 2 \cdot 29 + 3 = 61 \end{align}

Note that $5 = 2^3 -3$, $13 = 2^4 -3$, $29 = 2^5 - 3$, $61 = 2^6 -3$. So, we "suspect" that $B(3,x) = 2^{x+3} - 3$. Let us verify it with a proof by induction on $x \in \mathbb{N}$.

Base case ($x = 0$). We have just shown that $B(3,0) = 5 = 2^{0+3} - 3$.

Inductive step. We suppose that $B(3,x) = 2^{x+3} - 3$ (inductive hypothesis). We have to show that $B(3,x+1) = 2^{(x+1) + 3} - 3 = 2^{x+4} - 3$. According to the definition of $B$, and since we have the explicit definition of $B(2,x)$,

$$ B(3,x+1) = B(2,B(3,x)) = 2B(3,x) + 3 = 2(2^{x+3} - 3) + 3 = 2^{x+4} -3. $$

---

Thus, we have found an explicit definition of $B(3,x)$ for every $x \in \mathbb{N}$.

$$ B(3,x) = 2^{x+3} - 3 $$

Answer 4

I think recasting every equation in the definition to $B(y,x)$ instead of $B(y+1,x+1)$ for example may be more intuitive.

$$B(0,x)=x+1$$

$$B(y,0)=B(y-1,1)$$

$$B(y,x)=B(y-1,B(y,x-1))$$

or all together:

$$B(y,x)=\begin{cases}x+1,&y=0\\B(y-1,1),&y\ne0\text{ and }x=0\\B(y-1,B(y,x-1)),&y\ne0\text{ and }x\ne0\end{cases}$$

Now you can simply plug into the above. For example, with $B(2,1)$ we get:

\begin{align}B(2,1)&=B(1,B(2,0))\\B(2,0)&=B(1,1)\\B(1,1)&=B(0,B(1,0))\\B(1,0)&=B(0,1)\\B(0,1)&=2\end{align}

and you can plug that back in and work it out further.