# Tetration induction proof

The triple arrow-up denotes power towers in which the number of levels themselves is a power tower with a number of levels that is a power tower, and so on. For example,

\begin{align} a\uparrow\uparrow\uparrow2&=a\uparrow\uparrow a\\ a\uparrow\uparrow\uparrow3&=a\uparrow\uparrow(a\uparrow\uparrow a)\\ a\uparrow\uparrow\uparrow4&=a\uparrow\uparrow(a\uparrow\uparrow(a\uparrow\uparrow a)) \end{align}

We can define the triple arrow-up rigorously by using recursion:

$$a\uparrow\uparrow\uparrow1=a\text{ and }a\uparrow\uparrow\uparrow(k+1)=a\uparrow\uparrow(a\uparrow\uparrow\uparrow k).$$

Let $$A$$ be the variation of the Ackermann function defined by $$A(m,n)=\begin{cases}2n&\text{if }m=0\\0&\text{if }m\ge1\text{ and }n=0\\2&\text{if }m\ge1\text{ and }n=1\\A\big(m-1,A(m,n-1)\big)&\text{if }m\ge1\text{ and }n\ge2.\end{cases}$$

Conjecture a formula for $$A(3,n)$$ in terms of the triple arrow-up and prove it using induction for all positive integers $$n$$.

So far, I have $$A(3,n) = A(2,A(3,n-1))$$ and then using $$A(2,n) = 2 \uparrow \uparrow n$$ I arrive at. $$A(3,n) = 2 \uparrow \uparrow A(3,n-1)$$ I'm not clear how to proceed from this point to rewrite it as a triple arrow function.

• It looks like you're almost there... Look at the form of your function, and at the form of the triple arrow $$a \uparrow \uparrow \uparrow k = a \uparrow \uparrow (a \uparrow \uparrow \uparrow (k-1))$$. – Matt Groff Oct 31 '18 at 23:37

## 1 Answer

Hint:

If you know that $$A(2,n)=2\uparrow\uparrow n$$, then it amounts to seeing what $$A(3,1)$$ is and comparing it to $$2\uparrow\uparrow\uparrow n$$ or something similar. Note that we already have:

$$a\uparrow\uparrow\uparrow(k+1)=a\uparrow\uparrow(a\uparrow\uparrow\uparrow k)\\A(3,n+1)=2\uparrow\uparrow A(3,n)$$

which should make this fairly obvious.