Ackermann Function: Proof that n < A(m, n) for all m, n in N

Question

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

Answer 1

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$.

Answer 2

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$.