Mixing
Prove $F(n+2) - 1 = 1 + n(h-1) + n(h-2)$ by mathematical induction
$begingroup$
$F(0)= 0$ and $F(1) = 1$ are predefined; $F(n)$ references the $n^{th}$ Fibonacci number. $n(h)$ is the minimal number of nodes needed to construct a AVL binary tree of height $h$. The theory shouldn't matter too much here I only have to prove the equation by complete induction. I am already through the induction hypothesis and tried two different values $> 2$ which worked fine as expected.
This is what I did:
After swapping $h$ with $k+1$ I got:
$1 + n(h) + n(h-1) = F(h+3) - 1$
I then splitted $F(h+3) - 1$ into it's components $F(h+2) + F(h+1) - 1$.
Then $F(h+2) - 1$ could be replaced by $1 + n(h-1) + n(h-2)$ following the hypothesis.
This gets:
$1 + n(h) + n(h-1) = 1 + n(h-1) + n(h-2) + F(h+1)$ and this is where I am stuck as I could split the Fibonacci numbers as long as I want without getting any further. I would really appreciate some advice from you guys :/
graph-theory computer-science recursion fibonacci-numbers trees
edited Jan 11 at 2:20
Lee
328111
asked Jan 11 at 2:02
XoreXore
61
$endgroup$
|
show 1 more comment
$begingroup$
$F(0)= 0$ and $F(1) = 1$ are predefined; $F(n)$ references the $n^{th}$ Fibonacci number. $n(h)$ is the minimal number of nodes needed to construct a AVL binary tree of height $h$. The theory shouldn't matter too much here I only have to prove the equation by complete induction. I am already through the induction hypothesis and tried two different values $> 2$ which worked fine as expected.
This is what I did:
After swapping $h$ with $k+1$ I got:
$1 + n(h) + n(h-1) = F(h+3) - 1$
I then splitted $F(h+3) - 1$ into it's components $F(h+2) + F(h+1) - 1$.
Then $F(h+2) - 1$ could be replaced by $1 + n(h-1) + n(h-2)$ following the hypothesis.
This gets:
$1 + n(h) + n(h-1) = 1 + n(h-1) + n(h-2) + F(h+1)$ and this is where I am stuck as I could split the Fibonacci numbers as long as I want without getting any further. I would really appreciate some advice from you guys :/
graph-theory computer-science recursion fibonacci-numbers trees
edited Jan 11 at 2:20
Lee
328111
asked Jan 11 at 2:02
XoreXore
61
$endgroup$
2
$begingroup$
What is $AVL$, and why would you (with reputation $6$) assume everyone knows this?
$endgroup$
– David G. Stork
Jan 11 at 2:06
$begingroup$
@DavidG.Stork: An AVL tree is a binary search tree that satisfies a particular balancing condition; there are insert/delete algorithms that maintain the balancing invariant together with the search tree property as the tree evolves. en.wikipedia.org/wiki/AVL_tree
$endgroup$
– Henning Makholm
Jan 11 at 2:47
1
$begingroup$
But no, this should not be something a reader on this site is expected to know. @Xore, your proof probably ought to start by stating a recursion equation that holds for your $n(cdot)$ function. It looks like you're trying to complete a proof without referring to any property of this function that you already know. That is pretty much a doomed approach.
$endgroup$
– Henning Makholm
Jan 11 at 2:52
$begingroup$
@HenningMakholm If I were to define it further I would have to get further into the explanation what a AVL tree is. I can explain how I came up with 1 + n(h-1) + n(h-2): I will just state the facts without explaining further but if I look at a root node of a binary tree. One subtree must be 1 "deeper" than the other one. With deeper I mean that the height has to be higher by 1. Now n(h) describes how many nodes there are with given height h. So the total number in such a tree has to be n(h-1)+n(h-2) + 1. Because we start calculating after the root we have to add the "+1" afterwards
$endgroup$
– Xore
Jan 12 at 14:35
$begingroup$
@HenningMakholm The original question was that I had to prove following by complete induction: F(h+2) - 1 describes the minimal number of nodes required at given height h in an AVL Tree. The formula after the equation was given at some point in University so I assume it must be correct.
$endgroup$
– Xore
Jan 12 at 14:39
|
show 1 more comment
$begingroup$
$F(0)= 0$ and $F(1) = 1$ are predefined; $F(n)$ references the $n^{th}$ Fibonacci number. $n(h)$ is the minimal number of nodes needed to construct a AVL binary tree of height $h$. The theory shouldn't matter too much here I only have to prove the equation by complete induction. I am already through the induction hypothesis and tried two different values $> 2$ which worked fine as expected.
This is what I did:
After swapping $h$ with $k+1$ I got:
$1 + n(h) + n(h-1) = F(h+3) - 1$
I then splitted $F(h+3) - 1$ into it's components $F(h+2) + F(h+1) - 1$.
Then $F(h+2) - 1$ could be replaced by $1 + n(h-1) + n(h-2)$ following the hypothesis.
This gets:
$1 + n(h) + n(h-1) = 1 + n(h-1) + n(h-2) + F(h+1)$ and this is where I am stuck as I could split the Fibonacci numbers as long as I want without getting any further. I would really appreciate some advice from you guys :/
graph-theory computer-science recursion fibonacci-numbers trees
edited Jan 11 at 2:20
Lee
328111
asked Jan 11 at 2:02
XoreXore
61
$endgroup$
$F(0)= 0$ and $F(1) = 1$ are predefined; $F(n)$ references the $n^{th}$ Fibonacci number. $n(h)$ is the minimal number of nodes needed to construct a AVL binary tree of height $h$. The theory shouldn't matter too much here I only have to prove the equation by complete induction. I am already through the induction hypothesis and tried two different values $> 2$ which worked fine as expected.
This is what I did:
After swapping $h$ with $k+1$ I got:
$1 + n(h) + n(h-1) = F(h+3) - 1$
I then splitted $F(h+3) - 1$ into it's components $F(h+2) + F(h+1) - 1$.
Then $F(h+2) - 1$ could be replaced by $1 + n(h-1) + n(h-2)$ following the hypothesis.
This gets:
$1 + n(h) + n(h-1) = 1 + n(h-1) + n(h-2) + F(h+1)$ and this is where I am stuck as I could split the Fibonacci numbers as long as I want without getting any further. I would really appreciate some advice from you guys :/
graph-theory computer-science recursion fibonacci-numbers trees
graph-theory computer-science recursion fibonacci-numbers trees
edited Jan 11 at 2:20
Lee
328111
asked Jan 11 at 2:02
XoreXore
61
edited Jan 11 at 2:20
Lee
328111
asked Jan 11 at 2:02
XoreXore
61
edited Jan 11 at 2:20
Lee
328111
edited Jan 11 at 2:20
Lee
328111
edited Jan 11 at 2:20
Lee
328111
328111
asked Jan 11 at 2:02
XoreXore
61
asked Jan 11 at 2:02
XoreXore
61
asked Jan 11 at 2:02
XoreXore
61
61
2
$begingroup$
What is $AVL$, and why would you (with reputation $6$) assume everyone knows this?
$endgroup$
– David G. Stork
Jan 11 at 2:06
$begingroup$
@DavidG.Stork: An AVL tree is a binary search tree that satisfies a particular balancing condition; there are insert/delete algorithms that maintain the balancing invariant together with the search tree property as the tree evolves. en.wikipedia.org/wiki/AVL_tree
$endgroup$
– Henning Makholm
Jan 11 at 2:47
1
$begingroup$
But no, this should not be something a reader on this site is expected to know. @Xore, your proof probably ought to start by stating a recursion equation that holds for your $n(cdot)$ function. It looks like you're trying to complete a proof without referring to any property of this function that you already know. That is pretty much a doomed approach.
$endgroup$
– Henning Makholm
Jan 11 at 2:52
$begingroup$
@HenningMakholm If I were to define it further I would have to get further into the explanation what a AVL tree is. I can explain how I came up with 1 + n(h-1) + n(h-2): I will just state the facts without explaining further but if I look at a root node of a binary tree. One subtree must be 1 "deeper" than the other one. With deeper I mean that the height has to be higher by 1. Now n(h) describes how many nodes there are with given height h. So the total number in such a tree has to be n(h-1)+n(h-2) + 1. Because we start calculating after the root we have to add the "+1" afterwards
$endgroup$
– Xore
Jan 12 at 14:35
$begingroup$
@HenningMakholm The original question was that I had to prove following by complete induction: F(h+2) - 1 describes the minimal number of nodes required at given height h in an AVL Tree. The formula after the equation was given at some point in University so I assume it must be correct.
$endgroup$
– Xore
Jan 12 at 14:39
|
show 1 more comment
2
$begingroup$
What is $AVL$, and why would you (with reputation $6$) assume everyone knows this?
$endgroup$
– David G. Stork
Jan 11 at 2:06
$begingroup$
@DavidG.Stork: An AVL tree is a binary search tree that satisfies a particular balancing condition; there are insert/delete algorithms that maintain the balancing invariant together with the search tree property as the tree evolves. en.wikipedia.org/wiki/AVL_tree
$endgroup$
– Henning Makholm
Jan 11 at 2:47
1
$begingroup$
But no, this should not be something a reader on this site is expected to know. @Xore, your proof probably ought to start by stating a recursion equation that holds for your $n(cdot)$ function. It looks like you're trying to complete a proof without referring to any property of this function that you already know. That is pretty much a doomed approach.
$endgroup$
– Henning Makholm
Jan 11 at 2:52
$begingroup$
@HenningMakholm If I were to define it further I would have to get further into the explanation what a AVL tree is. I can explain how I came up with 1 + n(h-1) + n(h-2): I will just state the facts without explaining further but if I look at a root node of a binary tree. One subtree must be 1 "deeper" than the other one. With deeper I mean that the height has to be higher by 1. Now n(h) describes how many nodes there are with given height h. So the total number in such a tree has to be n(h-1)+n(h-2) + 1. Because we start calculating after the root we have to add the "+1" afterwards
$endgroup$
– Xore
Jan 12 at 14:35
$begingroup$
@HenningMakholm The original question was that I had to prove following by complete induction: F(h+2) - 1 describes the minimal number of nodes required at given height h in an AVL Tree. The formula after the equation was given at some point in University so I assume it must be correct.
$endgroup$
– Xore
Jan 12 at 14:39
2
2
$begingroup$
What is $AVL$, and why would you (with reputation $6$) assume everyone knows this?
$endgroup$
– David G. Stork
Jan 11 at 2:06
$begingroup$
What is $AVL$, and why would you (with reputation $6$) assume everyone knows this?
$endgroup$
– David G. Stork
Jan 11 at 2:06
$begingroup$
@DavidG.Stork: An AVL tree is a binary search tree that satisfies a particular balancing condition; there are insert/delete algorithms that maintain the balancing invariant together with the search tree property as the tree evolves. en.wikipedia.org/wiki/AVL_tree
$endgroup$
– Henning Makholm
Jan 11 at 2:47
$begingroup$
@DavidG.Stork: An AVL tree is a binary search tree that satisfies a particular balancing condition; there are insert/delete algorithms that maintain the balancing invariant together with the search tree property as the tree evolves. en.wikipedia.org/wiki/AVL_tree
$endgroup$
– Henning Makholm
Jan 11 at 2:47
1
1
$begingroup$
But no, this should not be something a reader on this site is expected to know. @Xore, your proof probably ought to start by stating a recursion equation that holds for your $n(cdot)$ function. It looks like you're trying to complete a proof without referring to any property of this function that you already know. That is pretty much a doomed approach.
$endgroup$
– Henning Makholm
Jan 11 at 2:52
$begingroup$
But no, this should not be something a reader on this site is expected to know. @Xore, your proof probably ought to start by stating a recursion equation that holds for your $n(cdot)$ function. It looks like you're trying to complete a proof without referring to any property of this function that you already know. That is pretty much a doomed approach.
$endgroup$
– Henning Makholm
Jan 11 at 2:52
$begingroup$
@HenningMakholm If I were to define it further I would have to get further into the explanation what a AVL tree is. I can explain how I came up with 1 + n(h-1) + n(h-2): I will just state the facts without explaining further but if I look at a root node of a binary tree. One subtree must be 1 "deeper" than the other one. With deeper I mean that the height has to be higher by 1. Now n(h) describes how many nodes there are with given height h. So the total number in such a tree has to be n(h-1)+n(h-2) + 1. Because we start calculating after the root we have to add the "+1" afterwards
$endgroup$
– Xore
Jan 12 at 14:35
$begingroup$
@HenningMakholm If I were to define it further I would have to get further into the explanation what a AVL tree is. I can explain how I came up with 1 + n(h-1) + n(h-2): I will just state the facts without explaining further but if I look at a root node of a binary tree. One subtree must be 1 "deeper" than the other one. With deeper I mean that the height has to be higher by 1. Now n(h) describes how many nodes there are with given height h. So the total number in such a tree has to be n(h-1)+n(h-2) + 1. Because we start calculating after the root we have to add the "+1" afterwards
$endgroup$
– Xore
Jan 12 at 14:35
$begingroup$
@HenningMakholm The original question was that I had to prove following by complete induction: F(h+2) - 1 describes the minimal number of nodes required at given height h in an AVL Tree. The formula after the equation was given at some point in University so I assume it must be correct.
$endgroup$
– Xore
Jan 12 at 14:39
$begingroup$
@HenningMakholm The original question was that I had to prove following by complete induction: F(h+2) - 1 describes the minimal number of nodes required at given height h in an AVL Tree. The formula after the equation was given at some point in University so I assume it must be correct.
$endgroup$
– Xore
Jan 12 at 14:39
|
show 1 more comment
0
active
oldest
votes
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%2f3069413%2fprove-fn2-1-1-nh-1-nh-2-by-mathematical-induction%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3069413%2fprove-fn2-1-1-nh-1-nh-2-by-mathematical-induction%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
2
$begingroup$
What is $AVL$, and why would you (with reputation $6$) assume everyone knows this?
$endgroup$
– David G. Stork
Jan 11 at 2:06
$begingroup$
@DavidG.Stork: An AVL tree is a binary search tree that satisfies a particular balancing condition; there are insert/delete algorithms that maintain the balancing invariant together with the search tree property as the tree evolves. en.wikipedia.org/wiki/AVL_tree
$endgroup$
– Henning Makholm
Jan 11 at 2:47
1
$begingroup$
But no, this should not be something a reader on this site is expected to know. @Xore, your proof probably ought to start by stating a recursion equation that holds for your $n(cdot)$ function. It looks like you're trying to complete a proof without referring to any property of this function that you already know. That is pretty much a doomed approach.
$endgroup$
– Henning Makholm
Jan 11 at 2:52
$begingroup$
@HenningMakholm If I were to define it further I would have to get further into the explanation what a AVL tree is. I can explain how I came up with 1 + n(h-1) + n(h-2): I will just state the facts without explaining further but if I look at a root node of a binary tree. One subtree must be 1 "deeper" than the other one. With deeper I mean that the height has to be higher by 1. Now n(h) describes how many nodes there are with given height h. So the total number in such a tree has to be n(h-1)+n(h-2) + 1. Because we start calculating after the root we have to add the "+1" afterwards
$endgroup$
– Xore
Jan 12 at 14:35
$begingroup$
@HenningMakholm The original question was that I had to prove following by complete induction: F(h+2) - 1 describes the minimal number of nodes required at given height h in an AVL Tree. The formula after the equation was given at some point in University so I assume it must be correct.
$endgroup$
– Xore
Jan 12 at 14:39