The rooted Fibonacci trees Tn, n ‰¥ 1, are defined recursively as follows:
(1) T1 is the rooted tree consisting of only the root;
(2) T2 is the same as T1 - it too is a rooted tree that consists of a single vertex; and
(3) For n ‰¥ 3, Tn is the rooted binary tree with Tn-2 as its left subtree and Tn-2 as its right subtree.
The first six rooted Fibonacci trees are shown in Fig. 12.47:

(a) For n ‰¥ 1, let in count the number of leaves in Tn. Find and solve a recurrence relation for in.
(b) Let in count the number of internal vertices for the tree Tn, where n ‰¥ 1. Find and solve a recurrence relation for in.
(c) Determine a formula for vn, the total number of vertices in Tn, where n ‰¥ 1.

Transcribed Image Text:

T6 T4 Ts