In the following 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., A5 B2 C3 D4 E1 F2 G3 H5 I3). There is more than one correct sequence. There are many incorrect sequences.

Definition: 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.

Let intNodes(T) denote the number of internal nodes in a full binary tree T, and let leaves(T) denote the number of leaves in a full binary tree T, 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).

B3: 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 Tbecomes 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 T_L and T_R. Both T_L and T_R. 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 y from 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 T_L or T_R 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 T_L or T_R 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 T_L or T_R 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 T_L and T_R must have height h.

E11: By construction both T_L and T_R must have height h-1.

E12: By construction both T_L and T_R 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( T_L ) 2 h + 1 and nodes( T_R ) 2 h + 1.

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

F6: Then, by the induction hypothesis, nodes( T_L ) 2 (h + 1) + 1 = 2 h + 3 and nodes( T_R ) 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( T_L ) + nodes( T_R ) + 1,

G10: Finally, since nodes( T ) nodes( T_L ) + nodes( T_R ) + 1,

G11: Finally, since nodes( T ) = nodes( T_L ) + nodes( T_R ) + 2,

G12: Finally, since nodes( T ) nodes( T_L ) + nodes( T_R ) + 2,

G13: Finally, since nodes( T ) = nodes( T_L ) + nodes( T_R ),

G14: Finally, since nodes( T ) nodes( T_L ) + nodes( T_R ),

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.