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.
[Math] Ackermann Function: Prove that $A(m, n + 1) > A(m, n)$ whenever $m$ and $n$ are nonnegative integers.
ackermann-functiondiscrete mathematicsinduction
Best Answer
Hint:
Consider the slightly stronger statement:
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$::