How can we prove by induction the relation $P(x,y)$?

Question

How can we prove by induction the relation $A(x,y)>y, \forall x,y$, where A(x,y) is the Ackermann function?

When we have to prove a relation $P(n), n\geq 0$, we do the following steps:

• we show that it stands for $n=0$

• we assume that it stands for n=k (Induction hypothesis)

• we want to shw that it stands for $n=k+1$ using the Induction hypothesis.

Which are the steps in this case where we have two variables??

Answer 1

For a general function (ignoring for the moment that you want Ackermann) it depends upon the way you want to traverse the pairs $(x, y)$.

Three ways occur to me:

For each $x$, do all the $y$'s.

For each $y$, do all the $x$'s.

For each $n$, do all the $(x, y)$ pairs with $x+y = n$. You can have $x$ go from $1$ to $n-1$ (so $y$ goes from $n-1$ to $1$), or $y$ go from $1$ to $n-1$ (so $x$ goes from $n-1$ to $1$).

Each of these requires a different proof strategy.

By looking how the function is defined recursively, you can decide which of these would work best. Essentially, choose the one that mimics how the function recurses.

Answer 2

marty's answer is correct regarding the general proof strategy. For the specific claim that Ackermann's function satisfies $A(x,y) \gt y$ for all nonnegative integers x and y, I believe this is a correct inductive proof:

Base case: $A(0,y) \gt 0$ for any nonnegative integer y. Proof: $A(0,y) = y+1 > y$.

Inductive hypothesis: $A(x-1, y) > y$ for any nonnegative integer $y$.

Because we're dealing with integers, $a > b$ implies that $a >= b+1$. So really we have:

Inductive hypothesis: $A(x-1, y) >= y + 1$ for any nonnegative integer $y$.

Now to prove $A(x, y) > y$ using that assumption:

$A(x, y) = A(x-1, A(x, y-1)) >= A(x, y-1) + 1$.

$A(x, y-1) + 1 = A(x-1, A(x, y-2)) + 1 >= A(x, y-2) + 2$.

$A(x, y-2) + 2 = A(x-1, A(x, y-3)) + 1 >= A(x, y-3) + 3$.

...

$A(x, 1) + (y-1) = A(x-1, A(x, 0)) + 1+(y-1) >= A(x, 0) + y$.

Therefore, $A(x, y) >= A(x, 0) + y$.

To conclude that $A(x, y) > y$, you also need to prove that $A(x, 0) > 0$. I'll leave that as an exercise since it's a much more straightforward induction proof.