You are asked to assemble a proof by induction from the parts given. Your answer
ID: 3598747 • Letter: Y
Question
You are asked to assemble a proof by induction from the parts given. Your answer should include one paragraph from each letter prefix. The answer should only include the sequence of paragraph lablels (e.g., A1 B4 C1 D2 E5 F1 G4 H5 I3). There is more than one correct sequence. There are many incorrect sequences.
Question 1
Using the definition of full binary tree, we define a full binary tree to be a rooted tree such that every node in the tree either has two children or has no children. (I.e., a node in a full binary tree is not allowed to have exactly one child.) We call nodes with two children internal nodes and nodes without any children leaves, assemble a proof by induction that for all full binary trees, T,
nodes( T ) 2 · height( T ) + 1 .
where nodes( T ) and height( T ) are the number of nodes in T and the height of T, respectively. Here we define the height of a tree with a single node to be 0.
A1: Induction Hypothesis P(h): for every full binary tree T with height h, nodes( T ) 2 · height( T ) + 1 .
A2: Induction Hypothesis P(n): for every full binary tree T with n internal nodes, nodes( T ) 2 · height( T ) + 1 .
A3: Induction Hypothesis P(n): for every full binary tree T with n nodes, nodes( T ) 2 · height( T ) + 1 .
B1: Base case P(0): A full binary tree with height 0 has exactly 1 node. Since 1 2 · 0 + 1, the induction hypothesis holds for P(0).
B2: Base case P(1): A full binary tree with height 1 has exactly 3 nodes. Since 3 2 · 1 + 1, the induction hypothesis holds for P(1).
B2: Base case P(1): A full binary tree with a single node has height 0. Since 1 2 · 0 + 1, the induction hypothesis holds for P(0).
C1: Suppose that we have a full binary tree T with height h.
C2: Suppose that we have a full binary tree T with height h+1.
C3: Suppose that we have a full binary tree with n nodes.
C4: Suppose that we have a full binary tree with n+1 nodes.
D1: We construct a new full binary tree T ' by taking two copies of T and adding a new root node x. The first copy of T becomes the left subtree of x. The second copy of T becomes the right subtree of x. The T 'constructed this way is also a full binary tree.
D2: Consider the root of T. If we remove the root from T, we have two subtrees TL and TR. Both TL and TR. are also full binary trees.
D3: Let T be full binary tree with n nodes, where n 1. The tree T must have at least one leaf node x. We construct a new tree T ' by adding two children to x. The T ' constructed this way is also a full binary tree.
D4: Let T be a full binary tree with n+2 nodes. The tree T must have at least one leaf node x. Since T is a full binary tree, the parent of x must have another child y. We construct a new tree T ' by removing x and yfrom T. The new tree T ' must still be a full binary tree.
E1: By construction, T' must have height h.
E2: By construction, T' must have height h - 1.
E3: By construction, T' must have height h + 1.
E4: By construction, T' must have height at least h.
E5: By construction, T' must have height at least h - 1.
E6: By construction, T' must have height at least h + 1.
E7: By construction one of TL or TR must have height h and the other one has at least one node. Let T ' be the subtree that has height h.
E8: By construction one of TL or TR must have height h 1 and the other tree has at least one node. Let T ' be the subtree that has height h 1.
E9: By construction one of TL or TR must have height h + 1 and the other tree has at least one node. Let T ' be the subtree that has height h + 1.
E10: By construction both TL and TR must have height h.
E11: By construction both TL and TR must have height h-1.
E12: By construction both TL and TR must have height h+1.
F1: Then, by the induction hypothesis, nodes( T ' ) 2 h + 1.
F2: Then, by the induction hypothesis, nodes( T ' ) 2 (h 1) + 1 = 2 h 1.
F3: Then, by the induction hypothesis, nodes( T ' ) 2 (h + 1) + 1 = 2 h + 3.
F4: Then, by the induction hypothesis, nodes( TL ) 2 h + 1 and nodes( TR ) 2 h + 1.
Explanation / Answer
The correct sequence would be
B1 B2 A1 C1 D1 E10 E3 F3
B3 A3 C3 D3 E3 F4
please do upvote. If you have any doubts leave a comment.I will be happy to answer
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.