| (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)
1
= ━━ (10∙F0 – 2∙F0∙√5 + 4∙F1∙√5) =
20
5∙F0 + (2∙F1 – F0)∙√5
= ━━━━━━━━━━━━ (5)
10
and, for reasons of symmetry
(5∙F0 – (2∙F1 – 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 = 2∙Fn – 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 + n∙A)∙αn + (b + n∙B)∙β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 | , |
| 5∙A + | 5∙B = z0 | |
| α∙(5∙A) + | β∙(5∙B) = z1 | with |
| 5∙a + | 5∙b | = 5∙H0 | |
| α∙(5∙a) + | β∙(5∙b) | = y3 |
| 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 |
|
|||||
| 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 |
. |
| Kn ━━ Ln |
= | 2∙Hn + 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 : i∙2i) = (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.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 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 + 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∙αn .
The leading term of Ln+1 (=2∙Fn+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. 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 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 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 5671 AL NUENEN The Netherlands |
12th July 1981 prof.dr. Edsger W.Dijkstra Burroughs Research Fellow |