You are asked to assemble a proof by induction from the parts given. Your answer

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, but only ONE from each ie (A1,A2 we should only choose either A1 or A2).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 yfromT. 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

F5: Then, by the induction hypothesis, nodes( TL ) 2 (h 1) + 1 = 2 h 1 and nodes( TR ) 2 (h 1) + 1 = 2 h 1.

F6: Then, by the induction hypothesis, nodes( TL ) 2 (h + 1) + 1 = 2 h + 3 and nodes( TR ) 2 (h + 1) + 1 = 2 h + 3.

G1: Finally, since nodes( T ) = nodes( T ' ) + 1,

G2: Finally, since nodes( T ) nodes( T ' ) + 1,

G3: Finally, since nodes( T ) = nodes( T ' ) - 1,

G4: Finally, since nodes( T ) nodes( T ' ) - 1,

G5: Finally, since nodes( T ) = nodes( T ' ) + 2,

G6: Finally, since nodes( T ) nodes( T ' ) + 2,

G7: Finally, since nodes( T ) = nodes( T ' ) - 2,

G8: Finally, since nodes( T ) nodes( T ' ) - 2,

G9: Finally, since nodes( T ) = nodes( TL ) + nodes( TR ) + 1,

G10: Finally, since nodes( T ) nodes( TL ) + nodes( TR ) + 1,

G11: Finally, since nodes( T ) = nodes( TL ) + nodes( TR ) + 2,

G12: Finally, since nodes( T ) nodes( TL ) + nodes( TR ) + 2,

G13: Finally, since nodes( T ) = nodes( TL ) + nodes( TR ),

G14: Finally, since nodes( T ) nodes( TL ) + nodes( TR ),

H1: by applying some algebra, we get nodes( T ) 2 · height( T ) + 1.

H2: by applying some algebra, we get nodes( T ' ) 2 · height( T ' ) + 1.

H3: by applying some algebra, we get nodes( T ) 2 · height( T ' ) + 1.

H4: by applying some algebra, we get nodes( T ' ) 2 · height( T ) + 1.

I1: Therefore, the induction hypothesis holds for all full binary trees with height h and we have completed the proof by induction.

I2: Therefore, the induction hypothesis holds for all full binary trees with height h+1 and we have completed the proof by induction.

I3: Therefore, the induction hypothesis holds for all full binary trees with height h-1 and we have completed the proof by induction.

I4: Therefore, the induction hypothesis holds for all full binary trees with n internal nodes and we have completed the proof by induction.

I5: Therefore, the induction hypothesis holds for all full binary trees with n+1 internal nodes and we have completed the proof by induction.

I6: Therefore, the induction hypothesis holds for all full binary trees with n nodes and we have completed the proof by induction.

I7: Therefore, the induction hypothesis holds for all full binary trees with n+1 nodes and we have completed the proof by induction.

.

Explanation / Answer

Here we will prove the hypothesis by induction on the number of nodes of the full binary tree.
There A3 is the correct induction hypothesis.

The base case is for a full binary tree with only one node. Therefore B2 is correct.

Now we assume that the hypothesis is true for all full binary trees with n nodes. Therefore C3 is correct.

Now we add 2 new nodes to an existing leaf node. Therefore D3 is correct.

Height of the new tree is at least the previous height. Hence E4 is correct.

Our induction hypothesis now applies on the new tree. Hence F1 is correct.

The new tree T' has 2 nodes more than the previous tree T. Hence G7 is correct.

We apply algebra and argue on the new tree T'. Hence H2 is correct.

Finally I6 is correct because the induction is on full binary tree on with n nodes.

We have,

A3 B2 C3 D3 E4 F1 G7 H2 I6

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.