Fibonacci

Denis TRYSTRAM
Lecture notes Maths for Computer Science – MOSIG 1 – 2017

1 Fibonacci numbers

In the original problem introduced by Leonardo of Pisa (Fibonacci) in

the middle age, Fibonacci numbers are the number of pairs of rabbits that
can be produced at the successive generations. Starting by a single pair of
rabbits and assuming that each pair produces a new pair of rabbits at each
generation during only two generations.

Definition. Given the two numbers F0 = 1 and F1 = 1, the Fibonacci

numbers are obtained by the following expression: Fn+1 = Fn + Fn−1 .

Notice that it is a special case of un+1 = α.un + β.un−1 for α = β = 1.

There is a strong link between these numbers and the Pascal triangle:
As shown in Figure 2, Fibonacci numbers can be obtained by summing
up the successive numbers of the diagonals. The explanation is illustrated
in Figure 3: a diagonal is obtained by summing the two previous ones and
the two first start at 1.
 !" !" #" $" %"

Figure 1: Principle of the Fibonacci progression

F0 F1
1 F2
F3
1 1 F4
1 2 1 F5
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Figure 2: Obtaining Fibonacci numbers by the Pascal triangle.

2 Some recurrences on Fibonacci numbers

These numbers have nice
Pnproperties, like the following one.
Property 2. Fn+2 = k=0 Fk + 1

The proof is by induction.

The basis case (for n = 2) is true since F2 = F0 + 1.
Induction step: Let assume the property holds at rank n for Fn+2 and
compute Fn+3 : Pn
From the definition: FPn+3 = Fn+1 + FPn+2 where Fn+2 = k=0 Fk + 1
Thus, Fn+3 = Fn+1 + nk=0 Fk + 1 = n+1 F
k=0 k + 1

2.1 Computing the product of two consecutive Fibonacci

numbers
Pn−1
Fn .Fn−1 = k=0 Fk2 (for n ≥ 1)

2
 F3
+ F4
2 1 = F5
1 3 3
1 4
1

Figure 3: A diagonal is obtained by the sum of both previous ones.

• The relation can be proved by using a geometric argument (see figure

4).

Fn2
F22 …

F42
F32 Fn-1 F n

F5 Fn+12

Figure 4: Geometric interpretation of the relation F5 .F4 = F02 + F12 + F22 +

F32 + F42 and its generalization.

• Another proof is by induction.

The basis case is to check F0 .F1 = F02 , which is true.
Induction step: Let assume this property holds at rank n and com-
pute Fn+1 .Fn .
According to the definition of Fn+1 , we have
Fn+1 .Fn = (Fn + Fn−1 ).Fn = Fn2 + Fn .Fn−1
We apply now the induction hypothesis to this last term:
Fn+1 .Fn = Fn2 + n−1
P 2
Pn 2
k=0 Fk = k=0 Fk .

2.2 Another property dealing with squares

We will show the following property by two different methods

3
 2
Fn+2 2
= [Link] .Fn+1 + Fn−1 for n ≥ 2.

• The geometrical proof is obtained by using Fubini’s principle as de-

picted in Figure 5.

FnFn+1

Fn-12

2 .
Figure 5: Geometric interpretation for computing Fn+2

2
Let remark that this figure shows also another property: Fn+2 = Fn2 +
2
[Link] .Fn+1 + Fn−1

Fn2

Fn+12

Fn-12

2
Figure 6: Fn+2 and its various lower embedded ranks.

• Another proof uses directly the definition of the Fibonacci numbers:

2
Fn+2 = (Fn+1 + Fn )2
2
= Fn+1 + [Link]+1 .Fn + Fn2
2
= [Link]+1 .Fn − [Link]+1 .Fn + Fn+1 + Fn2
= [Link]+1 .Fn + (Fn+1 − Fn )2
Again, using the definition of Fn+1 into the square, we get the expected
result:
2
Fn+2 2
= [Link]+1 .Fn + Fn−1

4
2.3 Cassini’s identity
Show the following Cassini’s identity: Fn−1 .Fn+1 = Fn2 + (−1)n+1 for n ≥ 1.

• The proof by induction is as follows:

The basis case is straightforward since F0 .F2 = 2 and F12 + 1 = 2.
Below is the detail of the induction step, assuming the Cassini’s
identity holds at rank n.
Fn .Fn+2 = Fn (Fn+1 + Fn ) by definition of the Fibonacci progression
= Fn2 + Fn .Fn+1
we replace the last term using the recurrence hypothesis:
Fn2 = Fn−1 .Fn+1 − (−1)n+1 = Fn−1 .Fn+1 + (−1)n+2
Thus, Fn .Fn+2 = Fn .Fn+1 + Fn−1 .Fn+1 + (−1)n+2
= Fn+1 (Fn + Fn−1 ) + (−1)n+2
2
and again, since Fn + Fn−1 = Fn+1 , Fn .Fn+2 = Fn+1 + (−1)n+2

• The previous result (Cassini’s identity) is the basis of a geometrical

paradox (one of the favorite puzzle of Lewis Carroll). Consider a chess
board and cut it into 4 pieces as shown in figure 2.3, then reassemble
them into a rectangle.

The surface of the square is Fn2 while the rectangle is Fn+1 .Fn−1 . The
Cassini identity is applied for n = 5, F5 = 8. From one side, we obtain
a surface of 8 × 8 = 64 and 13 × 5 = 65 from the other side! The
paradox comes from the wrong representation of the diagonal of the
rectangle which does not coincide with the hypothenus of the rectangle
triangles of sides Fn+1 and Fn−1 . In other words, it always remains
(for any n) an empty space (corresponding to the unit size of the basic
case of the chess board). The greater n, the better the paradox because
the deformation of the surface of this basic case becomes more tiny.

5
3 Lucas numbers
A natural question is what happens if we change the first ranks, keeping the
same progression. It has been studied by the french mathematician Lucas:

Definition. Given the two numbers L0 = 2 and L1 = 1, the Lucas numbers

are obtained by the same progression as for Fibonacci: Ln+1 = Ln + Ln−1 .

There are several interesting links with Fibonacci numbers.

In particular,
P we established at the beginning of this chapter in Property 2
that Fn+2 = nk=0 Fk + 1 Pn
We have similarly: Ln+2 = k=0 Lk + 1 since the first steps are still
valid: L2 = L0 + 1 = 3. Actually, it will be true for all the progressions
where u1 = 1.

We can also easily show that the Lucas number of order n is the average
of the two previous and following Fibonacci numbers:
Ln = Fn+1 + Ln−1 .

4 Fibonacci system number

Let us study the way the Fibonacci numbers can be used for representing
integers.
Let us first introduce a notation: j  k iff j ≥ k + 2.
We will first prove the Zeckendorf ’s theorem which states that every
positive integer n has a unique representation of the form:
n = Fk1 + Fk2 + ... + Fkr where k1  k2  ...  kr and kr ≥ 2.
Here, we assume that the Fibonacci progression starts at index 1 and not
0, moreover, the decompositions will never consider F1 (since F1 = F2 ). For
instance, the representation of 12345 turns out to be:
12345 = 10946 + 987 + 377 + 34 + 1 = F21 + F16 + F14 + F9 + F2

Figure 7 shows the decomposition of the first integers written in this

system and its principle is depicted in Figure 8.

Proof of Zeckendorf ’s Theorem

The proof is done by induction on n.

• The basis is true for n = 2, n = 3 and n = 4. In this last case,

4 = 3 + 1 = F4 + F2 .

• Assume for the induction step that any integer k < n can be decom-
posed uniquely as the sum of non-consecutive Fibonacci numbers.
If n is a Fibonacci number, the proof is done.

6
 F2 F4 F6 F7 F8
F3 F5

Figure 7: The first integers (on the X-axis) broken down into the Zeckendorf
representation.

If it is not, write n = Fk1 + N where Fk1 is the largest Fibonacci

number lower than n and N > 0. There is only one such number. The
previous expression means in particular that n < Fk1+1 .
According to the induction hypothesis, N admits a unique decomposi-
tion in non-consecutive Fibonacci numbers:
N = Fk2 + ... + Fkr where k2  ...  kr ≥ 2.
Thus, n = Fk1 + Fk2 + ... + Fkr .
We should only check that Fk1  Fk2 , which is done by contradiction:
Assuming k1 and k2 are consecutive (k1 = k2 + 1 as k1 > k2) leads to
Fk1 + Fk2 = Fk1+1 which contradicts n < Fk1+1 .

Any unique system of representation is a numbering system.

The previous theorem ensures that any non-negative integer can be writ-
ten as a sequence of bits bi , in other words,
n = (bm bm−1 ...b2 )F iff n = Σm
k=2 bk Fk .
Let us compare this system to the binary representation. For instance,
the Fibonacci representation of 12345 is (100001010000100000010)F while
12345 = 213 + 212 + 25 + 24 + 23 + 20 = (1100000111001)2 .
The binary representation is more compact.

7
Figure 8: Principle of the construction of the Zeckendorf decomposition for
the successive numbers.

The decomposition in the Fibonacci basis of the first integers (starting

from 1 = (00001)F ) is as follows:
2 = (0010)2 = F3 = (00010)F
3 = (0011)2 = F4 = (00100)F
4 = (100)2 = 3 + 1 = (00101)F
5 = (101)2 = F5 = (01000)F
6 = (110)2 = 5 + 1 = (01001)F
7 = (111)2 = 5 + 2 = (01010)F
8 = (1000)2 = F6 = (10000)F
9 = (1001)2 = (10001)F
10 = (1010)2 = (10010)F
11 = (1011)2 = (10100)F
12 = (1100)2 = (10101)F
13 = (1101)2 = F7 = (100000)F
...
There is no consecutive digits equal to 1 in such representations. The
proof is by contradiction and comes directly from the  relation.

Let us now sketch how to perform basic arithmetic operations within this
system. We focus on the increment (addition of 1), that is obtaining n + 1
from n.
• This operation is simple if the last two digits are 00. Indeed, as there
are no consecutive 1s, we simply put a 01 at the rightmost positions.
• If the three last digits are 010, the operation gives 011, which is trans-
formed into 100. The process depends on the value of the fourth right
digit. The same transformation is propagated to the left if it is a 1.

8
• The last case to consider is when the two last digits are 01. Adding
1 leads to 10. Then, we proceed as for the previous case if the third
rightmost digit is a 1.