Ackermann Function: Prove that $A(m, n + 1) > A(m, n)$ whenever $m$ and $n$ are nonnegative integers.

Question

So I've been trying to solve the exercises out of Discrete Mathematics and Its Applications by Kenneth H. Rosen, and found myself to be stuck at this problem for quite a long time. The Ackermann function $A(m, n)$ is defined as $$\begin{cases} A(0, n) \overset{\text{def}}{=} 2n \\ A(m, 0) \overset{\text{def}}{=} 0 \\ A(m, 1) \overset{\text{def}}{=} 2 \\ A(m, n) \overset{\text{def}}{=} A(m - 1, A(m, n - 1))\end{cases} $$Prove that $A(m, n + 1) > A(m, n)$ whenever $m$ and $n$ are non-negative integers. Any help regarding how to approach this problem using induction would be really appreciated.

Answer 1

Hint:

Consider the slightly stronger statement:

$A(m,n+1)\ge A(m,n)+2$ for all $m,n\in\mathbb N$.

Note that this also implies $A(m,n)\ge2n$ by induction over $n$.

Prove it by induction over $m$.

Base case $m=0$ follows trivially.

Inductive case: Suppose it holds for some $m=j$. We prove it holds for $m=j+1$. We prove by induction over $n$.

Base case $n=0$ follows trivially.

Base case $n=1$ follows trivially. (Show that $A(m,2)=4$ for all $m$.)

Inductive case: Suppose it holds for some $n=k\ge1$. We prove it holds for $n=k+1$::

$A(j+1,k+2)\\=A(j,A(j+1,k+1))\\\ge2A(j+1,k+1)\\=A(j+1,k+1)+A(j+1,k+1)\\\ge A(j+1,k+1)+2(k+1)\\\ge A(j+1,k+1)+2.$