you are asked to assemble a proof by induction from the parts given. you pick one from each letter.

answer should be like this: (e.g., A5 B2 C3 D4 E1 F2 G3 H5 I3).

Question 1

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. Use the paragraphs below to assemble a proof by induction that in every full binary tree T, leaves(T) = intNodes(T) + 1.

A1: Induction Hypothesis P(h): for every full binary tree T with height h, leaves(T) = intNodes(T) + 1.

A2: Induction Hypothesis P(n): for every full binary tree T with n internal nodes, leaves(T) = intNodes(T) + 1.

A3: Induction Hypothesis P(n): for every full binary tree T with n nodes, leaves(T) = intNodes(T) + 1.

B1: Base case P(0): the only full binary tree with height 0 consists of a single node. There is one leaf and zero internal nodes. Hence, P(0) holds.

B2: Base case P(0): the only full binary tree with 0 internal nodes is the full binary tree that consists of a single leaf and zero internal nodes, hence P(0) holds.

B3: Base case P(1): the only full binary tree with 1 node has one internal node and zero leaves, hence P(1) holds.

B4: Base case P(1): the only full binary tree with height 1 has one internal node and two leaves, hence P(1) holds.

B5: Base case P(1): the only full binary tree with height 1 has one internal node and zero leaves, hence P(1) holds.

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.

C5: Suppose that we have a full binary tree with n internal nodes.

C6: Suppose that we have a full binary tree with n+1 internal 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 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: Since T ' has fewer nodes than T, by the induction hypothesis, leaves( T ' ) = intNodes( T ' ) + 1.

E2: Since T ' has fewer internal nodes than T, by the induction hypothesis, leaves( T ' ) = intNodes( T ' ) + 1.

E3: Since T ' has fewer leaves than T, by the induction hypothesis, leaves( T ' ) = intNodes( T ' ) + 1.

E4: Since T ' has more nodes than T, by the induction hypothesis, leaves( T ) = intNodes( T ) + 1.

E5: Since T_L and T_R have fewer nodes than T, by the induction hypothesis, we know that leaves(T_L) = intNodes(T_L) + 1 and leaves(T_R) = intNodes(T_R) + 1.

E6: Since T_L and T_R have smaller height than T, by the induction hypothesis, we know that leaves(T_L) = intNodes(T_L) + 1 and leaves(T_R) = intNodes(T_R) + 1.

E7: Since T_L and T_R have fewer internal nodes than T, by the induction hypothesis, we know that leaves(T_L) = intNodes(T_L) + 1 and leaves(T_R) = intNodes(T_R) + 1.

F1: By construction, we know that intNodes( T ' ) = intNodes( T ) + 1, because we added an internal node to T when we constructed T '.

F2: By construction, we know that intNodes( T ' ) = intNodes( T ) 1 because we removed an internal node to T when we constructed T '.

F3: By construction, we know that intNodes( T ' ) = intNodes( T ). because every internal nodes in T is also an internal node ofT ', and vice versa.

F4: By construction, we know that intNodes( T ) = 1 + intNodes( T_L ) + intNodes( T_R ).

F5: By construction, we know that intNodes( T ) = intNodes( T_L ) + intNodes( T_R ).

G1: Also, leaves( T ' ) = leaves( T ) + 1.

G2: Also, leaves( T ' ) = leaves( T ) + 2.

G3: Also, leaves( T ' ) = leaves( T ) 1.

G4: Also, leaves( T ) = 2 + leaves( T_L ) + leaves( T_R ).

G5: Also, leaves( T ) = leaves( T_L ) + leaves( T_R ).

G6: Also, leaves( T ) = leaves( T_L ) + leaves( T_R ) 1.

H1: Finally, by applying some algebra, we get leaves( T ' ) = intNodes( T ' ) + 1.

H2: Finally, by applying some algebra, we get leaves( T ) = intNodes( T ) + 1.

H3: Finally, by applying some algebra, we get leaves( T ) = intNodes( T ).

H4: Finally, by applying some algebra, we get leaves( T ) = intNodes( T ).

H5: Finally, by applying some algebra, we get intNodes( T ' ) = intNodes( T ).

H6: Finally, by applying some algebra, we get leaves( T ' ) = leaves( T ).

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.