I have a very elementary question: here
on the page 7, 4th line
why
$$ A_{k+1} (n+1) = A_k (A_{k+1} (n))$$
Is it trivial or do we need induction ?
Asked
Active
Viewed 157 times
0
-
It follows directly from line $1$ of page $7$: $A_{k+1}(n) = A_kA_k\cdots A_k$. – Dietrich Burde Oct 06 '21 at 16:47
-
@DietrichBurde But the r.h.s. on the 1st line of page 7 has $1$ as an argument; the displayed formula has $n$. Could you be more explicit ? – user122424 Oct 06 '21 at 20:41
-
@DietrichBurde I'm adding bounty for you, please reply. – user122424 Oct 09 '21 at 17:05
1 Answers
1
It depends on the way the definition is phrased.
A common way of defining the Ackermann function is this one:
(1) $A(0,n)=n+1$
(2) $A(k+1,0)=A(k,1)$
(3) $A(k+1,n+1)=A(k,A(k+1,n))$
If you rewrite $A(k,n)$ as $A_k(n)$, line (3) becomes
$A_{k+1}(n+1) = A_k(A_{k+1}(n))$
Your source uses an alternative style of definition, starting with $A_1$ and $A_{k+1}(n) = A_k\circ\cdots\circ A_k(1)=A_k^n(1)$. Starting from there, you can also obtain
$$ A_{k+1}(n+1) = A_k^{n+1}(1)= A_k(A_k^n(1)) = A_k(A_{k+1}(n)) $$
Marc Olschok
- 1,833
-
Still is something wrong there You write in the last but one line $$A_{k+1}(n)=A^n_k(1)$$ and on the last line $$A_{k+1}(n+1)=A^n_k(1).$$ So $$A_{k+1}(n)=A_{k+1}(n+1)$$ and this is strange. – user122424 Oct 11 '21 at 17:40
-
1yes, in the last line, the part after the first '=' should be shifted to match with the left side. I correted that now. – Marc Olschok Oct 12 '21 at 20:40