Page 32 - MATINF Nr. 8

32 2 NUMBER OF LEAVES IN A FIBONACCI TREE

2 Number of leaves in a Fibonacci tree

In this section, we will prove, by using mathematical induction, the following

Theorem 1. For any n > 4, the following relations hold:


 = F n−1
L F 1



L F 0 = F n−3
P(n) : .
R F 1 = F n−2




= F n−4
R F 0
We will use the order 2 and order 3 trees (Images 1 and 2) to start the proof.

Image 1 Image 2

The order 4 tree will have the order 3 tree as the left subtree and the order 2 tree as the
right subtree.
It follows that the order 4 tree will have:


= 2

L F 1


= 1

L F 0
.
= 1
R F 1



 = 1
R F 0
As previously stated, the order 5 tree will have the order 4 tree as the left subtree and the
order 3 tree as the right subtree, which means that:

 = 3 = F 4
L F 1



L F 0 = 1 = F 2
P(5) : ,
R F 1 = 2 = F 3




R F 0 = 1 = F 1
which verifies our hypothesis.
If P(k) is true (where k ∈ {5, 6, 7, ..., n − 1, n}), then the (n + 1)-order tree will have the the
n-order tree as the left subtree and the order (n − 1)-tree as the right subtree, which means
that: