A Note on Closed-Form Representation of Fibonacci Numbers Using Fibonacci Trees

We give a new representation of the Fibonacci numbers. This is achieved using Fibonacci trees. With the help of this representation, the th Fibonacci number can be calculated without having any knowledge about the previous Fibonacci numbers. 1. Introduction A Fibonacci tree is a rooted binary tree in which for every nonleaf vertex , the heights of the subtrees, rooted at the left and right child of , differ by exactly one. A formal recursive definition of the Fibonacci tree (denoted by if its height is ) is given below. Definition 1. . For , is obtained by taking a copy of , a copy of , a new vertex , and joining to the roots of and . Figure 1 shows this construction and a few small Fibonacci trees. Figure 1: Recursive construction and examples of Fibonacci Trees. The above recursive definition implies that the number of vertices in is . On solving this recurrence relation, we get , where is the th number in the Fibonacci sequence, ; this justifies the terminology Fibonacci tree. The Fibonacci tree is the one with the minimum number of vertices among the class of AVL trees (see [1]). Several properties of Fibonacci trees have been investigated: for example, Fibonacci numbers of Fibonacci trees have been studied in [2], optimality of Fibonacci numbers is discussed in [3], asymptotic properties of Balaban’s index for Fibonacci trees have been explored in [4], and Zeckendorf representation of integers is given in [5]. In this short paper, we represent the number of vertices of in closed form (A closed form is one which gives the value of a sequence at index in terms of only one parameter, itself.) by observing the number of vertices at each level of . Such a calculation helps us to give a closed-form representation of th Fibonacci number for every . 2. Closed-Form Representation of Fibonacci Numbers There are several closed-form representations of the Fibonacci numbers. We state a few below.(i)Consider ？It was also derived by Binet (see [6]) in 1843, although the result was known to Euler, Daniel Bernoulli, and de Moivre more than a century earlier.(ii)Consider ？In the above generating function for the Fibonacci numbers the value of gives the th Fibonacci number. However, expanding the generating function involves tedious calculations.(iii)Consider It was also derived by Binet (see [6]) where the function rounds the simplified expression up or down to an integer. In this section, we give a simpler closed-form combinatorial representation of Fibonacci numbers. To do so, we first give a closed-form representation of the number of vertices of (the Fibonacci