Tetration induction proof
$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}
auparrowuparrowuparrow2&=auparrowuparrow a\
auparrowuparrowuparrow3&=auparrowuparrow(auparrowuparrow a)\
auparrowuparrowuparrow4&=auparrowuparrow(auparrowuparrow(auparrowuparrow a))
end{align}$$
We can define the triple arrow-up rigorously by using recursion:
$$auparrowuparrowuparrow1=atext{ and }auparrowuparrowuparrow(k+1)=auparrowuparrow(auparrowuparrowuparrow 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 }mge1text{ and }n=0\2&text{if }mge1text{ and }n=1\Abig(m-1,A(m,n-1)big)&text{if }mge1text{ and }nge2.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.
discrete-mathematics induction recursion tetration ackermann-function
edited Jan 9 at 22:24
Simply Beautiful Art
50.6k579183
asked Oct 31 '18 at 3:09
Jonathan Jonathan
1
$endgroup$
add a comment |
$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}
auparrowuparrowuparrow2&=auparrowuparrow a\
auparrowuparrowuparrow3&=auparrowuparrow(auparrowuparrow a)\
auparrowuparrowuparrow4&=auparrowuparrow(auparrowuparrow(auparrowuparrow a))
end{align}$$
We can define the triple arrow-up rigorously by using recursion:
$$auparrowuparrowuparrow1=atext{ and }auparrowuparrowuparrow(k+1)=auparrowuparrow(auparrowuparrowuparrow 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 }mge1text{ and }n=0\2&text{if }mge1text{ and }n=1\Abig(m-1,A(m,n-1)big)&text{if }mge1text{ and }nge2.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.
discrete-mathematics induction recursion tetration ackermann-function
edited Jan 9 at 22:24
Simply Beautiful Art
50.6k579183
asked Oct 31 '18 at 3:09
Jonathan Jonathan
1
$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
add a comment |
$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}
auparrowuparrowuparrow2&=auparrowuparrow a\
auparrowuparrowuparrow3&=auparrowuparrow(auparrowuparrow a)\
auparrowuparrowuparrow4&=auparrowuparrow(auparrowuparrow(auparrowuparrow a))
end{align}$$
We can define the triple arrow-up rigorously by using recursion:
$$auparrowuparrowuparrow1=atext{ and }auparrowuparrowuparrow(k+1)=auparrowuparrow(auparrowuparrowuparrow 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 }mge1text{ and }n=0\2&text{if }mge1text{ and }n=1\Abig(m-1,A(m,n-1)big)&text{if }mge1text{ and }nge2.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.
discrete-mathematics induction recursion tetration ackermann-function
edited Jan 9 at 22:24
Simply Beautiful Art
50.6k579183
asked Oct 31 '18 at 3:09
Jonathan Jonathan
1
$endgroup$
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}
auparrowuparrowuparrow2&=auparrowuparrow a\
auparrowuparrowuparrow3&=auparrowuparrow(auparrowuparrow a)\
auparrowuparrowuparrow4&=auparrowuparrow(auparrowuparrow(auparrowuparrow a))
end{align}$$
We can define the triple arrow-up rigorously by using recursion:
$$auparrowuparrowuparrow1=atext{ and }auparrowuparrowuparrow(k+1)=auparrowuparrow(auparrowuparrowuparrow 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 }mge1text{ and }n=0\2&text{if }mge1text{ and }n=1\Abig(m-1,A(m,n-1)big)&text{if }mge1text{ and }nge2.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.
discrete-mathematics induction recursion tetration ackermann-function
discrete-mathematics induction recursion tetration ackermann-function
edited Jan 9 at 22:24
Simply Beautiful Art
50.6k579183
asked Oct 31 '18 at 3:09
Jonathan Jonathan
1
edited Jan 9 at 22:24
Simply Beautiful Art
50.6k579183
asked Oct 31 '18 at 3:09
Jonathan Jonathan
1
edited Jan 9 at 22:24
Simply Beautiful Art
50.6k579183
edited Jan 9 at 22:24
Simply Beautiful Art
50.6k579183
edited Jan 9 at 22:24
Simply Beautiful Art
50.6k579183
50.6k579183
asked Oct 31 '18 at 3:09
Jonathan Jonathan
1
asked Oct 31 '18 at 3:09
Jonathan Jonathan
1
asked Oct 31 '18 at 3:09
Jonathan Jonathan
1
1
$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
add a comment |
$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
$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
$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
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Hint:
If you know that $A(2,n)=2uparrowuparrow n$, then it amounts to seeing what $A(3,1)$ is and comparing it to $2uparrowuparrowuparrow n$ or something similar. Note that we already have:
$$auparrowuparrowuparrow(k+1)=auparrowuparrow(auparrowuparrowuparrow k)\A(3,n+1)=2uparrowuparrow A(3,n)$$
which should make this fairly obvious.
answered Jan 9 at 22:28
Simply Beautiful ArtSimply Beautiful Art
50.6k579183
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2978626%2ftetration-induction-proof%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hint:
If you know that $A(2,n)=2uparrowuparrow n$, then it amounts to seeing what $A(3,1)$ is and comparing it to $2uparrowuparrowuparrow n$ or something similar. Note that we already have:
$$auparrowuparrowuparrow(k+1)=auparrowuparrow(auparrowuparrowuparrow k)\A(3,n+1)=2uparrowuparrow A(3,n)$$
which should make this fairly obvious.
answered Jan 9 at 22:28
Simply Beautiful ArtSimply Beautiful Art
50.6k579183
$endgroup$
add a comment |
$begingroup$
Hint:
If you know that $A(2,n)=2uparrowuparrow n$, then it amounts to seeing what $A(3,1)$ is and comparing it to $2uparrowuparrowuparrow n$ or something similar. Note that we already have:
$$auparrowuparrowuparrow(k+1)=auparrowuparrow(auparrowuparrowuparrow k)\A(3,n+1)=2uparrowuparrow A(3,n)$$
which should make this fairly obvious.
answered Jan 9 at 22:28
Simply Beautiful ArtSimply Beautiful Art
50.6k579183
$endgroup$
add a comment |
$begingroup$
Hint:
If you know that $A(2,n)=2uparrowuparrow n$, then it amounts to seeing what $A(3,1)$ is and comparing it to $2uparrowuparrowuparrow n$ or something similar. Note that we already have:
$$auparrowuparrowuparrow(k+1)=auparrowuparrow(auparrowuparrowuparrow k)\A(3,n+1)=2uparrowuparrow A(3,n)$$
which should make this fairly obvious.
answered Jan 9 at 22:28
Simply Beautiful ArtSimply Beautiful Art
50.6k579183
$endgroup$
Hint:
If you know that $A(2,n)=2uparrowuparrow n$, then it amounts to seeing what $A(3,1)$ is and comparing it to $2uparrowuparrowuparrow n$ or something similar. Note that we already have:
$$auparrowuparrowuparrow(k+1)=auparrowuparrow(auparrowuparrowuparrow k)\A(3,n+1)=2uparrowuparrow A(3,n)$$
which should make this fairly obvious.
answered Jan 9 at 22:28
Simply Beautiful ArtSimply Beautiful Art
50.6k579183
answered Jan 9 at 22:28
Simply Beautiful ArtSimply Beautiful Art
50.6k579183
answered Jan 9 at 22:28
Simply Beautiful ArtSimply Beautiful Art
50.6k579183
answered Jan 9 at 22:28
Simply Beautiful ArtSimply Beautiful Art
50.6k579183
50.6k579183
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2978626%2ftetration-induction-proof%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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