Page 33 - MATINF Nr. 8

33


 (n) = F n−1 + F n−2 = F n
L F 1 = T F 1



L F 0 = T F 0 (n) = F n−3 + F n−4 = F n−2
P(n + 1) : ,
R F 1 (n − 1) = F n−2 + F n−3 = F n−1
= T F 1




R F 0 = T F 0 (n − 1) = F n−4 + F n−5 = F n−3
so our hypothesis is correct!
3 Properties of the leaves

Using the previous result, we have the following interesting properties (it is known that
F n
lim = φ).
n→+∞ F n−1

L F 1 F n−1
1. lim = lim = φ
n→+∞ R F 1 n→+∞ F n−2
F n−3
L F 0
2. lim = lim = φ
n→+∞ F n−4
n→+∞ R F 0
(n)
T F 1 F n 2
3. lim = lim = φ
(n)
n→+∞ T F 0 n→+∞ F n−2
(n) F n
4. lim T F 1 = lim = φ
(n − 1)
n→+∞ T F 1 n→+∞ F n−1
(n)
T F 0 F n−2
5. lim = lim = φ
(n − 1)
n→+∞ T F 0 n→+∞ F n−3
F n−1 + F n−3
6. lim L F 1 + L F 0 = lim F n−1 + F n−3 = lim F n−4 F n−4 =
n→+∞ F n−2 + F n−4 n→+∞ F n−2 + 1
n→+∞ R F 1 + R F 0
F n−4
3
2
φ + φ φ(φ + 1)
= = = φ.
2
2
φ + 1 φ + 1
Remark 1. These results are also true for any subtree with a bigger order than 4!
Remark 2. One can generalize in the following way: the Fibonacci tree is always amazing to
work with, but, the remarkable thing is that the previous stated properties are also valid on any
tree, where the sequence’s recurrence formula is the same (the n-order number is the sum of the
(n − 1)-order and (n − 2)-order.

Of course, one of the best examples of generalization is the Lucas tree, that will have the
same configuration as the Fibonacci tree. The only difference is that instead of leaves of value
F 0 and F 1 , it will have leaves of value L 0 and L 1 .

4 Applications

The formulas and properties from this article can be used to solve easier some problems in
Computer Science: