Answer Happy

2. Binomial Trees are defined in Problem 5.29 of the text on page 184.. To construct the Fibonacci Tree fi you need the trees fi-1 and fi-2. Draw fi-1, and from the root of that tree draw a line to the root of fi-2. You now have fi. a. Note a leaf is a node without any children. Give a recurrence relation which satisfies the number of leaves in a binomial tree fr. b. Solve the recurrence relation from part a.

Problem 5.29. (Fibonacci trees) It is convenient to define the Fibonacci tree F-1 to consist of a single node. Then the i-th Fibonacci tree Fi, i 2 0, is defined recursively to consist of a root node with i children, where the j-th child, 1 sisi, is in turn the root of a Fibonacci tree Fj-2. Figure 5.23 shows Foto F5. Prove that the Fibonacci tree Fj, i 20, has fi-1 nodes, where fx is the k-th member of the Fibonacci sequence; see Section 1.6.4. F FoF F2 F3 Figure 5.23. Fibonacci trees Foto F