Fibonacci numbers and Leonardo numbers.
(The following formal derivations and computations
are absolutely elementary and without scientific in
terest. 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
F_{0} = 1 F_{1} = 1 F_{n+2} = F_{n+1} + F_{n} (or : F_{n+2} – F_{n+1} – F_{n} = 0).
The analytical solution of a homogeneous recurrence
relation like this is found by solving first the cor
responding characteristic equation which one gets
by "trying" an F of the form F_{n} = x^{n} :
(0) x^{2} – x – 1 = 0
This equation has two different roots, which I
shall denote by α and β
(1) α = ½ + ½√5 = 1.618034 ^{10}log α = 0.208988
β = ½ – ½√5 = – .618034
Obvious properties are
(2) α + β = 1 α∙β = –1
α^{2} = α + 1 , α^{3} = 2∙α + 1 , α^{4} = 3∙α + 2 , etc.
Because α ≠ β , α^{n} and β^{n} give rise to linearly
independent sequences and each solution of the
homogeneous recurrence relation is of the form
(3) F_{n} = X∙α^{n} + Y∙β^{n}
where the constants X and Y are determined by
solving the set of linear equations
(4) 
X + Y = F_{0} 

α∙X + β∙Y = F_{1} 
Multiplying the second equation by α we get —see (2)—
(α + 1)∙X – Y = α∙F1 , and hence
(α + 2)∙X = F_{0} + α∙F_{1} , hence
F_{0} + (½ + ½ √5)∙F_{1} 2∙F_{0} + (1 + √5)∙F_{1} (5 – √5)
X = ━━━━━━━━━━━━ = ━━━━━━━━━━━━ ∙ ━━━━━
2 ½ + ½ √5 (5 + √5) (5 – √5)
_{1}
= ━━ (10∙F_{0} – 2∙F_{0}∙√5 + 4∙F_{1}∙√5) =
^{20}
5∙F_{0} + (2∙F_{1} – F_{0})∙√5
= ━━━━━━━━━━━━ (5)
10
and, for reasons of symmetry
(5∙F_{0} – (2∙F_{1} – F_{0})∙√5)
Y = ━━━━━━━━━━━━ (5')
10
For the Fibonacci numbers we substitute F_{0} = F_{1} = 1
and find, according to (3)
(6) F_{n} = (½ + ⅟10√5)∙α^{n} + (½ – ⅟10√5)∙β^{n}
= .723607∙α^{n} + .276393∙β^{n}
* *
*
We now switch to the Leonardo numbers given
by L_{0} = 1 L_{1} = 1 L_{n+2} = L_{n+1} + L_{n} + 1 . This
recurrence relation is not homogeneous but
—because x = 1 is not a root of (0)— this is only
an apparent complication: (L_{n+2} + 1) = (L_{n+1}+1) + (L_{n} + 1),
and we immediately derive
(7) L_{n} = 2∙F_{n} – 1 .
The nth Leonardo tree has L_{n} vertices. The
(n+2)th Leonardo tree is a binary tree, of which
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 K_{n} we derive from
the definition
(8) K_{n+2} = (K_{n+1} + L_{n+1}) + (K_{n} + L_{n})
or
(K_{n+2}–2) = (K_{n+1}–2) + (K_{n}–2) + (L_{n+1}+1) + (L_{n}+1)
or with
(9) K_{n} = 2∙(H_{n} + 1) or H_{n} = (K_{n}–2)/2
(10) H_{n+2} = H_{n+1} + H_{n} + F_{n+2}
Solving (10) for F_{n+2} and taking the recurrence
relation for the F's into account one finds that the
H's satisfy a homogeneous linear recurrence relation
with (x^{2} – x – 1)^{2} = 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 H_{n} is
(11) H_{n} = (a + n∙A)∙α^{n} + (b + n∙B)∙β^{n}
where the constants a, A, b, and B are determined
by solving —see (2)—
(12) 
a + 

b 
= H_{0} 

α∙a + 
α∙A + 
β∙b + 
β∙B = H_{1} 

(α + 1)∙a + 
(2∙α + 2)∙A + 
(β + 1)∙b + 
(2∙β + 2)∙B = H_{2} 

(2∙α + 1)∙a + 
(6∙α + 3)∙A + 
(2∙β + 1)∙b + 
(6∙β + 3)∙B = H_{3} 
We eliminate a and b with
(13) y_{0} = H_{2} – H_{1} – H_{0}, y_{1} = H_{3} – H_{2} – H_{1}
(α + 2)∙A + 
(β + 2)∙B = y_{0} 

(3∙α + 1)∙A + 
(3∙β + 1)∙B = y_{1} 
, 
which leads to
5∙A + 
5∙B = z_{0} 

α∙(5∙A) + 
β∙(5∙B) = z_{1} 
with 
(14) z_{0} = 3∙y_{0} – y_{1} , z_{1} = 2∙y_{1} – y_{0}
This set of equations is of the same form as (4).
Hence we have
5∙z_{0} + (2∙z_{1} – z_{0})∙√5
(15) A = ━━━━━━━━━━━
50
5∙z_{0} – (2∙z_{1} – z_{0})∙√5
(15') B = ━━━━━━━━━━━
50
We can eliminate A and B from (12) with
y_{3} = –2∙H_{3} + 3∙H_{2} + 6∙H_{1} – H_{0
}

5∙a + 
5∙b 
= 5∙H_{0} 

α∙(5∙a) + 
β∙(5∙b) 
= y_{3}

which is again of the form (4). Eliminating y_{3}, we get
25∙H_{0} + (–4∙H_{3} + 6∙H_{2} + 12∙H_{1} – 7∙H_{0})∙√5
(16) a = ━━━━━━━━━━━━━━━━━━━━━━━
50
25∙H_{0} – (–4∙H_{3} + 6∙H_{2} + 12∙H_{1} – 7∙H_{0})∙√5
(16') b = ━━━━━━━━━━━━━━━━━━━━━━━
50
Let us apply these formulae with the numerical
values of K_{0}, K_{1}, K_{2}, K_{3} and then check them against
the numerical value of K_{4} . (It is a long time ago
since I made my last check.)
n: 
L_{n}: 
K_{n}: 
H_{n} 

From (13) : y_{0} = 2 y_{1} = 3 
0 
1 
0 
–1 

From (14) : z_{0} = 3 z_{1} = 4 
1 
1 
0 
–1 

From (15) : 
2 
3 
2 
0 

A = 
15 + 5∙√5
━━━━━━
^{50}

= 
3 + √5
━━━━
^{10}


3 
5 
6 
2 


4 
9 
16 
7 


From (16) 
a = 
–25 + (–8 – 12 + 7)∙√5
━━━━━━━━━━━━━━
^{50} 
= 
–25 –13∙√5
━━━━━━━━
^{50} 






b = 
–25 + 13∙√5
━━━━━━━━
^{50} 
. 

In order to check these values for n = 4 we compute
(a + 4∙A)∙α^{4} = ⅟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 asymp
totic behaviour of the average distance from the root
K_{n}
━━
L_{n} 
= 
2∙H_{n} + 2
━━━━━
2∙F_{n} – 1 
→ 
H_{n
}━━
F_{n} 
→ 
⅟10∙(3 + √5)
━━━━━━━━
⅟10∙(5 + √5) 
= 
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 number 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 ^{2}log N . For the Leonardo
trees it is .723607∙^{α}log N = 1.042296∙^{2}log 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 ≤ L_{i+1} : f(x)) , we have
D_{0} = 0 , D_{1} = 3 , D_{n+2} = D_{n+1} + D_{n} + L_{n+1} + 2 ,
hence D_{2} = 6 , D_{3} = 14 , D_{4} = 27 , etc.
This is the moment I am going to reap the fruit
of (13), (14), and (15). With H_{n} = D_{n} + 1 we have
H_{n+2} = H_{n+1} + H_{n} + 2∙F_{n+1} , and (11) is applicable.
We have H_{0} = 1 , H_{1} = 4 , H_{2} = 7 , and H_{3} = 15. From
(13) y_{0} = 2 , y_{1} = 1 ; from (14) z_{0} = 2 , z_{1} = 6 , and
from (15) A = ⅟50∙(10 + 10∙√5) = ⅟5∙(1 + √5) . Hence the
dominant term of H_{n} (and D_{n}) is ⅟5∙(1 + √5)∙n∙α^{n} .
The leading term of L_{n+1} (=2∙F_{n+1} – 1) is ⅟5∙(5 + √5)∙α^{n+1} =
⅟_{10}∙(1 + √5) (5 + √5)∙α^{n} .
The growth rate of the average value of f(x) is
that of H_{n}/L_{n+1} , i.e. 2∙n/(5 + √5) = ⅟10∙(5 – √5)∙n =
.276393∙^{α}log N .
Analogously to the perfectly balanced binary trees
we can replace the Leonardo numbers by B_{n} = 2^{n+1} – 1.
Let f'(x) be the minimum number of B's with sum x
and let C_{n} = (S : 0 ≤ x ≤ B_{n} : f'(x)). We find
C_{n} = (n + 1)∙2^{n} . In this case the growth rate of the
average value of f'(x) is —not surprisingly—
C_{n}/B_{n} = ½ (n + 1) = ½∙^{2}log N = ^{4}log N . Comparing
this with the case of the Leonardo numbers
.276393 ^{α}log N = .796243 ∙ ^{4}log N
and this time the ratio is markedly smaller than 1.
Plataanstraat 5
5671 AL NUENEN
The Netherlands 
12th July 1981
prof.dr. Edsger W.Dijkstra
Burroughs Research Fellow 
