7. In many induction problems, our boolean variable A, is true if the claim we are proving is true for problems of size i. What follows is an exercise in strong induction, where Ai is true if the claim is true for problems of size i or smaller. When using induction to show that an algorithm is correct, we often use strong induction. A rooted tree is a full binary tree if every internal node has exactly two children. Note that this does not require all the leaves to be at the same level. The minimum number of leaves a rooted tree can have is 1. Claim: Every full binary tree has exactly one fewer internal nodes than leaves. For all i > 1, let A be the proposition that every full binary tree with i or fewer leaves has exactly one fewer internal nodes than leaves. (Note the use of strong induction.) For the induction step, we need to show that for all n > 1, An-1 An. If A is false, the implication is immediately true. The only way the implication could fail is if An-1 is true. Let's prove that the implication is true even if An-1 is true. Suppose from here on that it is. Let T be an arbitrary full binary tree with n leaves. If we can show that T has n - 1 internal nodes, then since T is an arbitrary full binary tree with n leaves, all full binary trees with n leaves will have n-1 internal nodes. Because An-1 is true and the claim will be true for all full binary trees with n leaves, it will follow that An is true. Here is a strategy for our induction step: Cut away the root of T. What is left is two smaller full binary trees, T1 and T2. Let k be the number of leaves in Ti; n-k is the number of leaves in T2. Except for the missing root, the set of internal nodes of Ti and T2 is the same as the set of internal nodes of T. (a) Under the assumption that An-1 is true, how many internal nodes are in Ti? (Look carefully at the definition of A.) (b) Under the assumption that An-1 is true, how many internal nodes are in T2? (c) What do these statements imply about the number of internal nodes in T? (d) Finish any remaining steps required to complete the proof of the the claim. (e) What would go wrong with the proof if we did not use strong induction