Where are are the errors in my inductive proof?
I was asked the following question on an exam and it was only marked wrong with no other marks on it. I went to see the TA who marked it and he could only tell me that it was wrong. I suspect that he did not have the time to explain it to me. This is worrying because I must not have as good of an understanding of induction as I thought I did. Any help would be greatly appreciated as this will not be the last time I will being seeing induction.
Question:
For a proper binary tree, prove e = i + 1, where e is the number of leaves (external nodes) in the tree, and i is the number of internal nodes in the tree.
My best attempt at a proof:
Base Case:
there is one node in the tree that is external.
i = 0
e = i + 1 = 1
Assume: e = i + 1
if we add a node, the node (parent) will become an internal node and the number of external nodes stays the same. Now we have e = i.
However, for the tree to be a proper binary tree, we must add one more child so e = i + 1.
tree binary-tree proof induction
asked Nov 13 '18 at 21:08
Caleb WhiteheadCaleb Whitehead
6
add a comment |
I was asked the following question on an exam and it was only marked wrong with no other marks on it. I went to see the TA who marked it and he could only tell me that it was wrong. I suspect that he did not have the time to explain it to me. This is worrying because I must not have as good of an understanding of induction as I thought I did. Any help would be greatly appreciated as this will not be the last time I will being seeing induction.
Question:
For a proper binary tree, prove e = i + 1, where e is the number of leaves (external nodes) in the tree, and i is the number of internal nodes in the tree.
My best attempt at a proof:
Base Case:
there is one node in the tree that is external.
i = 0
e = i + 1 = 1
Assume: e = i + 1
if we add a node, the node (parent) will become an internal node and the number of external nodes stays the same. Now we have e = i.
However, for the tree to be a proper binary tree, we must add one more child so e = i + 1.
tree binary-tree proof induction
asked Nov 13 '18 at 21:08
Caleb WhiteheadCaleb Whitehead
6
What are you doing the induction over? I suggest you do it over the structure of the root node (empty - the base case, one child, two children). You don't seem to be invoking the inductive hypothesis anywhere.
– Lee
Nov 13 '18 at 21:17
What is an internal vs an external node? If a node has one child, is it internal or external? Or neither?
– Patrick87
Nov 14 '18 at 21:32
add a comment |
I was asked the following question on an exam and it was only marked wrong with no other marks on it. I went to see the TA who marked it and he could only tell me that it was wrong. I suspect that he did not have the time to explain it to me. This is worrying because I must not have as good of an understanding of induction as I thought I did. Any help would be greatly appreciated as this will not be the last time I will being seeing induction.
Question:
For a proper binary tree, prove e = i + 1, where e is the number of leaves (external nodes) in the tree, and i is the number of internal nodes in the tree.
My best attempt at a proof:
Base Case:
there is one node in the tree that is external.
i = 0
e = i + 1 = 1
Assume: e = i + 1
if we add a node, the node (parent) will become an internal node and the number of external nodes stays the same. Now we have e = i.
However, for the tree to be a proper binary tree, we must add one more child so e = i + 1.
tree binary-tree proof induction
asked Nov 13 '18 at 21:08
Caleb WhiteheadCaleb Whitehead
6
I was asked the following question on an exam and it was only marked wrong with no other marks on it. I went to see the TA who marked it and he could only tell me that it was wrong. I suspect that he did not have the time to explain it to me. This is worrying because I must not have as good of an understanding of induction as I thought I did. Any help would be greatly appreciated as this will not be the last time I will being seeing induction.
Question:
For a proper binary tree, prove e = i + 1, where e is the number of leaves (external nodes) in the tree, and i is the number of internal nodes in the tree.
My best attempt at a proof:
Base Case:
there is one node in the tree that is external.
i = 0
e = i + 1 = 1
Assume: e = i + 1
if we add a node, the node (parent) will become an internal node and the number of external nodes stays the same. Now we have e = i.
However, for the tree to be a proper binary tree, we must add one more child so e = i + 1.
tree binary-tree proof induction
tree binary-tree proof induction
asked Nov 13 '18 at 21:08
Caleb WhiteheadCaleb Whitehead
6
asked Nov 13 '18 at 21:08
Caleb WhiteheadCaleb Whitehead
6
asked Nov 13 '18 at 21:08
Caleb WhiteheadCaleb Whitehead
6
asked Nov 13 '18 at 21:08
Caleb WhiteheadCaleb Whitehead
6
asked Nov 13 '18 at 21:08
Caleb WhiteheadCaleb Whitehead
6
6
What are you doing the induction over? I suggest you do it over the structure of the root node (empty - the base case, one child, two children). You don't seem to be invoking the inductive hypothesis anywhere.
– Lee
Nov 13 '18 at 21:17
What is an internal vs an external node? If a node has one child, is it internal or external? Or neither?
– Patrick87
Nov 14 '18 at 21:32
add a comment |
What are you doing the induction over? I suggest you do it over the structure of the root node (empty - the base case, one child, two children). You don't seem to be invoking the inductive hypothesis anywhere.
– Lee
Nov 13 '18 at 21:17
What is an internal vs an external node? If a node has one child, is it internal or external? Or neither?
– Patrick87
Nov 14 '18 at 21:32
What are you doing the induction over? I suggest you do it over the structure of the root node (empty - the base case, one child, two children). You don't seem to be invoking the inductive hypothesis anywhere.
– Lee
Nov 13 '18 at 21:17
What are you doing the induction over? I suggest you do it over the structure of the root node (empty - the base case, one child, two children). You don't seem to be invoking the inductive hypothesis anywhere.
– Lee
Nov 13 '18 at 21:17
What is an internal vs an external node? If a node has one child, is it internal or external? Or neither?
– Patrick87
Nov 14 '18 at 21:32
What is an internal vs an external node? If a node has one child, is it internal or external? Or neither?
– Patrick87
Nov 14 '18 at 21:32
add a comment |
1 Answer
1
active
oldest
votes
As described on Wikipedia page, induction proof consists of two steps base case and induction step. You started with good base case. It seems to me that you are not clear what n means in the proof, so it is not clear how to do induction step.
Here are two proofs by induction of the proposition, where base case is as you stated.
First to be clear, lets recall definition of proper binary tree, itis a binary tree where each inner node has exactly two children.
1. n is number of internal nodes
To create tree with n+1 internal nodes, we have to take a tree with n internal nodes and change some leave with internal node.
That new internal node has to have two children which are leaves. That means new tree has one more internal node and one more leave than tree it is created from. Since property (e=i+1) holds for initial tree it also holds (e+1=i+1+1) for new tree.
2. n is depth of a tree
Lets take a tree (T) of depth n+1. It consists of a root and it's two children trees. Each children tree is of depth <= n,
and for both of then property hold (e_1=i_1+1, e_2=i_2+1). So number of external nodes in T is e = e_1 + e_2.
Number of internal nodes in T is i = (i_1+1) + (i_2+1) + 1. It is easy to se that e = i + 1.
answered Nov 22 '18 at 9:31
AnteAnte
4,38451942
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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
},
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%2fstackoverflow.com%2fquestions%2f53289507%2fwhere-are-are-the-errors-in-my-inductive-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
As described on Wikipedia page, induction proof consists of two steps base case and induction step. You started with good base case. It seems to me that you are not clear what n means in the proof, so it is not clear how to do induction step.
Here are two proofs by induction of the proposition, where base case is as you stated.
First to be clear, lets recall definition of proper binary tree, itis a binary tree where each inner node has exactly two children.
1. n is number of internal nodes
To create tree with n+1 internal nodes, we have to take a tree with n internal nodes and change some leave with internal node.
That new internal node has to have two children which are leaves. That means new tree has one more internal node and one more leave than tree it is created from. Since property (e=i+1) holds for initial tree it also holds (e+1=i+1+1) for new tree.
2. n is depth of a tree
Lets take a tree (T) of depth n+1. It consists of a root and it's two children trees. Each children tree is of depth <= n,
and for both of then property hold (e_1=i_1+1, e_2=i_2+1). So number of external nodes in T is e = e_1 + e_2.
Number of internal nodes in T is i = (i_1+1) + (i_2+1) + 1. It is easy to se that e = i + 1.
answered Nov 22 '18 at 9:31
AnteAnte
4,38451942
add a comment |
As described on Wikipedia page, induction proof consists of two steps base case and induction step. You started with good base case. It seems to me that you are not clear what n means in the proof, so it is not clear how to do induction step.
Here are two proofs by induction of the proposition, where base case is as you stated.
First to be clear, lets recall definition of proper binary tree, itis a binary tree where each inner node has exactly two children.
1. n is number of internal nodes
To create tree with n+1 internal nodes, we have to take a tree with n internal nodes and change some leave with internal node.
That new internal node has to have two children which are leaves. That means new tree has one more internal node and one more leave than tree it is created from. Since property (e=i+1) holds for initial tree it also holds (e+1=i+1+1) for new tree.
2. n is depth of a tree
Lets take a tree (T) of depth n+1. It consists of a root and it's two children trees. Each children tree is of depth <= n,
and for both of then property hold (e_1=i_1+1, e_2=i_2+1). So number of external nodes in T is e = e_1 + e_2.
Number of internal nodes in T is i = (i_1+1) + (i_2+1) + 1. It is easy to se that e = i + 1.
answered Nov 22 '18 at 9:31
AnteAnte
4,38451942
add a comment |
As described on Wikipedia page, induction proof consists of two steps base case and induction step. You started with good base case. It seems to me that you are not clear what n means in the proof, so it is not clear how to do induction step.
Here are two proofs by induction of the proposition, where base case is as you stated.
First to be clear, lets recall definition of proper binary tree, itis a binary tree where each inner node has exactly two children.
1. n is number of internal nodes
To create tree with n+1 internal nodes, we have to take a tree with n internal nodes and change some leave with internal node.
That new internal node has to have two children which are leaves. That means new tree has one more internal node and one more leave than tree it is created from. Since property (e=i+1) holds for initial tree it also holds (e+1=i+1+1) for new tree.
2. n is depth of a tree
Lets take a tree (T) of depth n+1. It consists of a root and it's two children trees. Each children tree is of depth <= n,
and for both of then property hold (e_1=i_1+1, e_2=i_2+1). So number of external nodes in T is e = e_1 + e_2.
Number of internal nodes in T is i = (i_1+1) + (i_2+1) + 1. It is easy to se that e = i + 1.
answered Nov 22 '18 at 9:31
AnteAnte
4,38451942
As described on Wikipedia page, induction proof consists of two steps base case and induction step. You started with good base case. It seems to me that you are not clear what n means in the proof, so it is not clear how to do induction step.
Here are two proofs by induction of the proposition, where base case is as you stated.
First to be clear, lets recall definition of proper binary tree, itis a binary tree where each inner node has exactly two children.
1. n is number of internal nodes
To create tree with n+1 internal nodes, we have to take a tree with n internal nodes and change some leave with internal node.
That new internal node has to have two children which are leaves. That means new tree has one more internal node and one more leave than tree it is created from. Since property (e=i+1) holds for initial tree it also holds (e+1=i+1+1) for new tree.
2. n is depth of a tree
Lets take a tree (T) of depth n+1. It consists of a root and it's two children trees. Each children tree is of depth <= n,
and for both of then property hold (e_1=i_1+1, e_2=i_2+1). So number of external nodes in T is e = e_1 + e_2.
Number of internal nodes in T is i = (i_1+1) + (i_2+1) + 1. It is easy to se that e = i + 1.
answered Nov 22 '18 at 9:31
AnteAnte
4,38451942
answered Nov 22 '18 at 9:31
AnteAnte
4,38451942
answered Nov 22 '18 at 9:31
AnteAnte
4,38451942
answered Nov 22 '18 at 9:31
AnteAnte
4,38451942
4,38451942
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f53289507%2fwhere-are-are-the-errors-in-my-inductive-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
What are you doing the induction over? I suggest you do it over the structure of the root node (empty - the base case, one child, two children). You don't seem to be invoking the inductive hypothesis anywhere.
– Lee
Nov 13 '18 at 21:17
What is an internal vs an external node? If a node has one child, is it internal or external? Or neither?
– Patrick87
Nov 14 '18 at 21:32