So I have this Ackermann function:
$$
A(0,y) = y+ 1\\
A(x, 0) = A(x-1,1)\\
A(x,y) = A(x-1,A(x,y-1))
$$
And I have another function:
$$
d(n) = 2^{2^{.^{.^{.^{.^{2}}}}}}
$$
while the height of the power tower is $n+2$.
I need to show with induction (or any other way, but I think induction is the way to go here) that $A(n,n) > d(n)$ for every $n \geq 4$.
I can use the fact that $A(4,y) = 2^{2^{.^{.^{.^{.^{2}}}}}} – 3$ and the power tower is of height of $y+3$.
So my induction begin would be:
$A(4,4) = 2^{2^{2^{2^{2^{2^{2}}}}}} – 3 > 2^{2^{2^{2^{2^{2}}}}} = d(4)$
My induction assumption would be then $A(n,n) > d(n)$
And the induction itself would be to show $A(n+1,n+1) > d(n+1)$. But how?
If I start opening the Ackermann function all the way I'm just getting a huge term. Does anyone have any idea how I go from here with this proof?
Example:
$$
A(n+1,n+1) =A(n,A(n+1,n))=A(n,A(n, A(n+2, n-1)))….=A(n,A(n, … A(2n, 0)))
$$
If I was to describe it in words, it is clear to me that the Ackermann function is always bigger, because the power tower's height increases in an exponential way, while the power tower in $d(n)$ grows linearly in height. But that doesn't mean we can assume that $A(5,5)>d(5)$ is true, just because $A(5,5)>A(4,4)>d(4)$, right?
Best Answer
Note that:
$$A(3,n)=2^{n+3}-3\ge2^n,~n\ge0$$
and that
$$A(n+1,n+1)=A(n,A(n+1,n))\ge A(3,A(n,n))\ge2^{d(n)}=d(n+1)$$
which concludes the inductive step.