4. (12 points) The set of full binary trees is defined recursively in Definition 5 on page 353: Basis step: There is a full binary consisting only of a single vertex r. Recursive step: If Ti and T2 are disjoint full binary trees, there is a full binary tree, denoted by Ti T2, consisting of a (new) root r together with edges connecting this root to the roots of the left subtree Ti and the right subtree T2 The book includes these pictures of the full binary trees that can be built up by applying the recursive step one or two times FIGURE4 Beilding Up Fall Binary Tres. (a) Draw all the binary trees that could be built up by applying the recursive step three times. (b) Come up with a formula for the maximum number of nodes (vertices) in a full binary tree that is built up by applying the recursive step n times. Prove your formula using mathematical induction