Fibonacci numbers and Leonardo numbers.
(The following formal derivations and computations are absolutely elementary and without
scientific interest. But I am interested in some numbers and need the formulae, and learned
that working on a scratch pad I make too many mistakes. Hence.)
The Fibonacci numbers are given by
F0 = 1 F1 = 1 Fn+2 = Fn+1 + Fn (or : Fn+2 - Fn+1 - Fn = 0).
The analytical solution of a homogeneous recurrence relation like this is found by solving first
the corresponding characteristic equation which one gets by "trying" an F of the form Fn = xⁿ :
(0) x² - x - 1 = 0
This equation has two different roots, which I shall denote by α and β
(1) α = ½ + ½√5 = 1.618034 10log α = 0.208988
β = ½ - ½√5 = - .618034
Obvious properties are
(2) α + β = 1 α . β = -1
α² = α + 1 , α³ = 2 . α + 1 , α⁴ = 3 . α + 2 , etc.
Because α ≠ β , αⁿ and βⁿ give rise to linearly independent sequences and each
solution of the homogeneous recurrence relation is of the form
(3) Fn = X . αⁿ + Y . βⁿ
where the constants X and Y are determined by solving the set of lineair equations
(4) X + Y = F0
α . X + β . Y = F1
Multiplying the second equation by α we get - see (2) -
(α + 1) . X - Y = α . F1 , and hence
(α + 2) . X = F0 + α . F1 , hence
F0 + (½ + ½ √5) . F1 2 . F0 + (1 + √5) . F1 (5 - √5)
X = ━━━━━━━━━━ = ━━━━━━━━━━ ∙ ━━━━
2 ½ + ½ √5 (5 + √5) (5 - √5)
= ⅟20 . (10 . F0 - 2 . F0 . √5 + 4 . F1 . √5) =
= ⅟10 . (5 . F0 + (2 . F1 - F0) . √5) (5)
and, for reasons of symmetry
Y = ⅟10 . (5 . F0 - (2 . F1 - F0) . √5) (5')
For the Fibonacci numbers we substitute F0 = F1 = 1 and find, according to (3)
(6) Fn = (½ + ⅟10√5) . αⁿ + (½ - ⅟10√5) . βⁿ
= .723607 . αⁿ + .276393 . βⁿ
* *
*
We now switch to the Leonardo numbers given by L0 = 1 L1 = 1 Ln+2 = Ln+1 + Ln + 1 .
This recurrence relation is not homogeneous but - because x = 1 is not a root of (0) - this is
only an apparent complication : (Ln+2 + 1) = (Ln+1) + (Ln + 1), and we immediately derive
(7) Ln = 2 . Fn - 1 .
The nth Leonardo tree has Ln vertices. The (n + 1)th and the nth Leonardo tree are the
two subtrees. A number that is perhaps of some interest is the distance from the root summed
over the vertices of the nth Leonardo tree.
Denoting this quantity by Kn we derive from the definition
(8) Kn+2 = (Kn+1 + Ln+1) + (Kn + Ln)
or
(Kn+2 - 2) = (Kn+1 - 2) + (Kn - 2) + (Ln+1 + 1) + (Ln + 1)
or with
(9) Kn = 2 . (Hn + 1) or Hn = (Kn - 2)/2
(10) Hn+2 = Hn+1 + Hn + Fn+2
Solving (10) for Fn+2 and taking the recurrence relation for the F's into account one
finds that the H's satisfy a homogeneous lineair recurrence relation with (x� - x - 1)� = 0
as characteristic equation. (This is a special case of a more general theorem of which I was
not aware.) Hence the general form of Hn is
(11) Hn = (a + n . A) . αⁿ + (b + n . B) . βⁿ
where the constants a, A, b, and B are determined by solving - see (2) -
(12) a + b = H0
α . a + α . A + β . b + β . B = H1
(α + 1) . a + (2 . α + 2) . A + (β + 1) . b + (2 . β + 2) . B = H2
(2 . α + 1) . a + (6 . α + 3) . A + (2 . β + 1) . b + (6 . β + 3) . B = H3
We eliminate a and b with
(13) y0 = H2 - H1 - H0 , y1 = H3 - H2 - H1
(α + 2) . A + (β + 2) . B = y0
(3 . α + 1) . A + (3 . β + 1) . B = y1 ,
which leads to
5 . A + 5 . B = z0
α . (5 . A) + β . (5 . B) = z1 with
(14) z0 = 3 . y0 - y2 , z1 = 2 . y2 - y0
This set of equations is of the same form as (4).
Hence we have
(15) A = ⅟50 . (5 . z0 + (2 . z1 - z0) . √5)
(15') B = ⅟50 . (5 . z0 - (2 . z1 - z0) . √5
We can eliminate A and B from (12) with
y3 = -2 . H3 + 3 . H2 + 6 . H1 - H0
5 . a + 5 . b = 5 . H0
α . (5 . a) + β . (5 . b) = y3
which is again of the form (4). Eliminating y3, we get
(16) a = ⅟50 . (25 . H0 + (-4 . H3 + 6 . H2 + 12 . H1 - 7 . H0) . √5)
(16') b = ⅟50 . (25 . H0 - (-4 . H3 + 6 . H2 + 12 . H1 - 7 . H0) . √5)
Let us apply these formulae with the numerical values of K0, K1, K2, K3 and then check
them against the numerical value of K4 . (It is a long time ago since I made my last check.)
n : Ln : Kn : Hn From (13) : y0 = 2 y1 = 3
0 1 0 -1 From (14) : z0 = 3 z1 = 4
1 1 0 -1 From (15) :
2 3 2 0 A = ⅟50 . (15 + 5 . √5) = ⅟10 . (3 + √5)
3 5 6 2 B = ⅟10 . (3 - √5)
4 9 16 7
From (16) a = ⅟50 . (-25 + (-8 - 12 + 7) . √5) = ⅟50 . (-25 -13 . √5)
b = ⅟50 . (-25 + 13 . √5) .
In order to check these values for n = 4 we compute
(a + 4 . A) . α⁴ = ⅟50 . (-25 -13 . √5 + 60 + 20 . √5) . (3 . α + 2)
= ⅟100 . (35 + 7 . √5) (7 + 3 . √5) = ⅟100 . (245 + 105 + 154 . √5)
= 3½ + 1.54 . √5 . This is OK and that is very encouraging.
We are now in a position to compute the asymptotic behaviour of the average distance
from the root
Kn 2 . Hn + 2 Hn ⅟10 . (3 + √5) 5 + √5
━━ = ━━━━━ ╺▷ ━━ ╺▷ ━━━━━━━━ . n = ━━━━ . n
Ln 2 . Fn - 1 Fn ⅟10 . (5 + √5) 10
With N the number of points, the average distance grows as
⅟10 . (5 + √5) . αlog N = .723607 . αlog N ,
a growth rate I would like to compare to the one of the completely balanced binary tree.
The numbers of nodes in the nth binary tree equals 2^(n+1) - 1 .
The sum over its nodes of their distances from the root is
(S i : 0 ≤ i ≤ n : i . 2^i) = (n - 1) . 2^(n+1) + 2 .
With N the number of points, the dominant term of the growth rate of the average distance
from the root is therefore 2log N . For the Leonardo trees it is
.723607 . αlog N = 1.042296 . 2log N .
The ratio is - as was to be expected - larger than 1, but only very little so. (I am not convinced
of the relevance of the notion "average distance from the root" ; it has the advantage that the
above estimations can be derived by elementary means.)
* *
*
We know that, with a given number, taking away the largest possible Leonardo number
and repeating this process on the remainder, we decompose the given number, x say, in the
minimum number f(x) of Leonardo numbers. What is the average value of f(x) when x ranges
over the first N natural numbers ?
Defining D i = (Sx : 0 ≤ x ≤ Li+1 : f(x)) , we have
D0 = 0 , D1 = 3 , Dn+2 = Dn+1 + Dn + Ln+1 + 2 ,
hence D2 = 6 , D3 = 14 , D4 = 27 , etc.
This is the moment I am going to reap the fruit of (13), (14), and (15).
With Hn = Dn + 1 we have Hn+2 = Hn+1 + Hn + 2 . Fn+1 , and (11) is applicable.
We have H0 = 1 , H1 = 4 , H2 = 7 , and H3 = 15.
From (13) y0 = 2 , y1 = 1 ; from (14) z0 = 2 , z1 = 6 ,
and from (15) A = ⅟50 . (10 + 10 . √5) = ⅟5 . (1 + √5) . Hence the dominant term of
Hn (and Dn) is ⅟5 . (1 + √5) . n . αⁿ .
The leading term of Ln+1 . (=2 . Fn+1 - 1) is ⅟5 . (5 + √5) . α^(n+1)
= ⅟10 . (1 + √5) (5 + √5) . αⁿ .
The growth rate of the average value of f(x) is that of Hn/Ln+1 , i.e.
2/(5 + √5) . n = ⅟10 . (5 - √5) = .276393 . αlog N .
Analogously to the perfectly balanced binary trees we can replace the Leonardo numbers
by Bn = 2^(n+1) - 1.
Let f'(x) be the minimum number of B's with sum x and let Cn = (S : 0 ≤ x ≤ Bn : f'(x)).
We find Cn = (n + 1) . 2ⁿ . In this case the growth rate of the average value of f'(x) is
- not surprisingly - Cn/Bn = ½ (n + 1) = ½ . 2log N = 4log N .
Comparing this with the case of the Leonardo numbers
.276393 αlog N = .796243 . 4log N
and this time the ratio is markedly smaller than 1.
Plataanstraat 5 12th July 1981
5671 AL NUENEN prof.dr. Edsger W.Dijkstra
The Netherlands Burroughs Research Fellow
|