The Fibonacci number of Fibonacci trees and a related family of polynomial recurrence systems, Fibonacci Quart. 45

Fibonacci trees are special binary trees which are of natural interest in the study of data structures. A Fibonacci tree of order n has the Fibonacci trees of orders n − 1 and n − 2 as left and right subtrees. On the other hand, the Fibonacci number F (G) of a graph G, introduced in a paper of Prodinger and Tichy in 1982, is defined as the number of independent vertex subsets of G. In this paper, we study the Fibonacci number of Fibonacci trees and show that the underlying system of re-currence equations belongs to a class with a special property. It will be shown that the Fibonacci number of the n-th Fibonacci tree with Fn+2 − 1 vertices is asymptotically 0.682328 · (3.659873)Fn.