HOME

Fibonacci numbers and Leonardo numbers

Show original manuscript
     (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 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 cor- responding characteristic equation which one gets by "trying" an F of the form Fn = xn : (0) x2 – 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 α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) Fn = Xαn + Yβn where the constants X and Y are determined by solving the set of linear 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         2F0 + (1 + √5)F1        (5 – √5)
X   =    ━━━━━━━━━━━━  =  ━━━━━━━━━━━━ ∙ ━━━━━
                    2 ½ + ½ √5                         (5 + √5)              (5 – √5)

           1 
     =  ━━ (10F0 – 2F0√5 + 4F1√5) =
          20

           5F0 + (2F1 – F0)√5
      =   ━━━━━━━━━━━━                                          (5)
                      10

        and, for reasons of symmetry

         (5F0 – (2F1 – F0)√5)
Y    =  ━━━━━━━━━━━━                                            (5')
                      10 

        For the Fibonacci numbers we substitute  F0 = F1 = 1
and find, according to (3)

(6)     Fn = (½ + ⅟10√5)αn + (½ – ⅟10√5)βn

        = .723607αn + .276393βn

                        *               *
                                *

        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+1) + (Ln + 1),
and we immediately derive

(7)             Ln = 2Fn – 1  .

        The nth Leonardo tree has Ln 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 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 linear recurrence relation
with (x2 – 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 Hn is

(11)    Hn = (a + nA)αn + (b + nB)βn

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
5A  + 5B  =  z0
α(5A)  + β(5B)  =  z1                 with
(14) z0 = 3y0 – y1 , z1 = 2y1 – y0 This set of equations is of the same form as (4). Hence we have 5z0 + (2z1 – z0)√5 (15) A = ━━━━━━━━━━━ 50 5z0 – (2z1 – z0)√5 (15') B = ━━━━━━━━━━━ 50 We can eliminate A and B from (12) with y3 = –2H3 + 3H2 + 6∙H1 – H0
          5a    + 5b  = 5H0
α(5a) + β(5b)  = y3
which is again of the form (4). Eliminating y3, we get  25H0 + (–4H3 + 6H2 + 12H1 – 7H0)√5 (16) a = ━━━━━━━━━━━━━━━━━━━━━━━ 50  25H0 – (–4H3 + 6H2 + 12H1 – 7H0)√5 (16') b = ━━━━━━━━━━━━━━━━━━━━━━━              50 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 =
15 + 5√5
━━━━━━ 
50
=
3 + √5
━━━━
10
3 5 6 2
4 9 16 7
B = 3 – √5
━━━━
10
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 + 4A)α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
Kn
━━
Ln
= 2Hn + 2
━━━━━
2
Fn – 1
Hn
━━
Fn
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  2n+1 – 1 . The sum over
its nodes of their distances from the root is
(S i : 0 ≤ i ≤ n : i2i) = (n–1)2n+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.0422962log 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        Di = (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 + 2Fn+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αn .
The leading term of  Ln+1 (=2Fn+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 Hn/Ln+1 , i.e. 2n/(5 + √5) = ⅟10(5 – √5)n =
.276393αlog N .

        Analogously to the perfectly balanced binary trees
we can replace the Leonardo numbers by Bn = 2n+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)2n  . In this case the growth rate of the
average value of f'(x) is not surprisinglyCn/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
5671 AL NUENEN
The Netherlands
12th July 1981
prof.dr. Edsger W.Dijkstra
Burroughs Research Fellow

transcribed by Sam Samshuijzen
revised Tue, 7 Jun 2005