0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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))$$. $\endgroup$ – Matt Groff Oct 31 '18 at 23:37
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.