1. The nth Fibonacci binary tree Fn is defined recursively as follows. A is a single root node with no children. For all n 2 2, Fn is obtained from -1 by adding a right child to every leaf and adding a left child to every node that has only one child. Figure 1. The first six Fibonacci binary trees. In each tree 9,' the subtree of gray nodes is 3,-1 (b) Prove that the number of leaves in n is precisely the nth Fibonacci number: F,-0, F1-1, and Fn F-1 +F-2 for all n 2 2. (c) How many nodes does F have? Given an exact closed-form answer in terms of Fibonacci numbers, and prove your answer is correct. (d) Prove that for all n 2, the right subtree of., is a copy of n_1