Ackermann Function: Proof that n < A(m, n) for all m, n in N I've been stuck at this problem for a while now and can't get it solved. The prof wants me to proof n < A(m,n) for all m and n being positive Integers.
More details on the Ackermann Function:
$$(1) A(0,n) = n + 1$$
$$(2) A(m + 1, 0) = A(m, 1)$$
$$(3) A(m + 1, n + 1) = A(m, A(m + 1, n))$$
My approach was the following:
Inductionstart_m: $m=0 ;  A(0, n) = n+1$
A(0, n) = n+1 is defined and can be assumed to be true
Inductionassumption_m: $n < A(m, n)$ for one m and all n
Inductionproof_m (What we want to proof): $n < A(m+1, n)$ for all n
InductionEnd_m -->
Inductionstart_n: $n=0 ; A(m+1, 0) = A(m, 1)$ --> $1 < A(m, 1)$
Inductionassumption_n: $n < A(m+1, n)$ for one n and all m
Inductionproof_n: $n+1 < A(m+1, n+1)$ for all m
InductionEnd_n: $n+1 < A(m+1, n+1) = A(m, A(m+1, n))$
we already proofed: $n < A(m+1, n)$
Now Im stuck. I dont know how to proof $n+1 < A(m+1, n)$
If that can be proven, then the proof would be done since we know that:
$A(m+1,n) < A(m, A(m+1,n)) $
is true from the Inductionassumption_m because it has the form: $n < A(m, n)$ for one m and all n
 A: This is a case in which it seems to be easier to carry out the induction with a stronger induction hypothesis. I used a three-part hypothesis:
Induction hypothesis:
$$\begin{align*}
&(1_m)\;A(k,n)>n\text{ for }0\le k\le m\text{ and }n\ge 0\\
&(2_m)\;A(k,\ell+1)>A(k,\ell)\text{ for }0\le k\le m\text{ and }\ell\ge 0\\
&(3_m)\;A(k+1,\ell)\ge A(k,\ell+1)\text{ for }0\le k<m\text{ and }\ell\ge 0
\end{align*}$$
$(1_m)$ is what we want to prove for all $m\ge 0$; the other two clauses just make that easier. $(2)$ says that $A$ is strictly increasing in its second argument, and $(3)$ is a stronger form of the assertion that it is strictly increasing in its first argument as well.
For the induction step we want to prove $(1)_{m+1},(2)_{m+1}$, and $(3)_{m+1}$. Specifically, we want to prove that $A(m+1,n)>n$ for $n\ge 0$, that $$A(m+1,n+1)>A(m+1,n)$$ for $n\ge 0$, and that $$A(m+1,n)\ge A(m,n+1)$$ for $n\ge 0$. We do this by induction on $n$.
To get the induction on $n$ started, we have $A(m+1,0)=A(m,1)>1$, which establishes $(1)_{m+1}$ and $(3_{m+1})$ for $n=0$. Assume that $(1)_{m+1}$ and $(3_{m+1})$ hold for $n$. Then
$$\begin{align*}
A(m+1,n+1)&=A\big(m,A(m+1,n)\big)\\
&\overset{(1)}\ge A\big(m,A(m,n+1)\big)\\
&\overset{(2)}\ge A(m,n+2)\\
&\overset{(3)}>n+2\,.
\end{align*}$$
Here $(1)$ uses $(2)_m$ and the assumption that $(3)_{m+1}$ holds for $n$; $(2)$ uses $(1)_m$ to conclude that $A(m,n+1)\ge n+2$ and then $(2)_m$, and $(3)$ again uses $(1)_m$. This establishes $(1)_{m+1}$ and $(3_{m+1})$ for $n+1$. Finally,
$$\begin{align*}
A(m+1,n+1)&=A\big(m,A(m+1,n)\big)\\
&>A(m+1,n)
\end{align*}$$
by $(1)_m$, which establishes $(2)_{m+1}$. Thus, the main induction goes through to establish $(1)_m,(2)_m$, and $(3)_m$ for all $m\ge 0$.
A: Notice that the Ackermann function is discrete. This means we may use $a>b\iff a\ge b+1$, which may be used on the step you found troublesome:
$$A(m+1,n+1)=A(m,A(m+1,n))\ge A(m+1,n)+1\ge(n+1)+1>n+1\tag{$\star$}$$
and the whole proof would be as follows:

*

*Base case $m=0$: For all $n$, $A(0,n)=n+1\ge n$ follows.


*Induction hypothesis $m\implies m+1$: Assume for some $m$ that for all $n$, $A(m,n)\ge n$. Then:

*

*Base case $n=0$: $A(m+1,0)=A(m,1)>1>0$ follows.


*Induction hypothesis $n\implies n+1$: See $(\star)$.


*Therefore $A(m+1,n)>n$ for all $n$.




*Therefore ($A(m,n)>n$ for all $n$) for all $m$.
Notice the indented steps all use a fixed $m$ i.e. the same value of $m$. If you write (for all $m$) on those lines, then you are not proving ($A(m+1,n)>n$ for all $n$), which has a fixed value of $m$.
