Lecture Notes The Fibonacci Sequence page 1

Part 1 - The De nition and Basic Properties

.
De nition: The Fibonacci sequence starts with 1 and 1 and for all other terms in the sequence, we must
add the last two terms.
F1 = 1 F2 = 2 and for all n 1, Fn + Fn+1 = Fn+2

So the rst few terms of the Fibonacci sequence are

1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; : : :

If we need to compute the 100th term of the sequence, we would be forced to rst compute the rst 99 terms in the sequence.
Such a de nition is called a recursive one. We are naturally interested in nding a formula that enables us to compute the
100th element directly. Such a formula is callled explicit. Like so many things about this sequence, the explicit formula for
its nth term is fascinating and surprising. We will derive this formula later. The Fibonacci sequence is named after Leonardo
Fibonacci and has many strange and interesting properties.
In case of each of the given statements, verify that it is true for the rst seven terms. of the Fibonacci sequence.
1. For all natural numbers n, n 2. F1 + F2 + F3 + ::: + Fn = Fn+2 1

2. For all natural numbers n, n 2, F12 + F22 + F32 + ::: + Fn2 = Fn Fn+1

3. For all natural numbers n, n 2, F1 + F3 + ::: + F2n 1 = F2n

4. For all natural numbers n, n 2, F2 + F4 + ::: + F2n = F2n+1 1

5. For all natural numbers n, n 2, Fn2 = Fn 1 Fn+1 + ( 1)n 1

Enrichment
1. Use induction to prove the properties stated above.
2. Prove that for all natural numbers n, Fn and Fn+1 are relatively prime. (Two integers are relatively
prime if their greatest common divisor is 1.)

Discussion: How are the solutons for these problems involve the Fibonacci Sequence?

1. We can get to the top of a mountain using steep roads (such as

between C and E) less steep roads (such as between A and B).
At each letter, we can switch from one type to the other. If
a climber wants to get from point A to point I, how many
different ways is that possible (assuming the climber always moves
upward)?
2. How many different ways are there to climb up 6 steps of stairs of
we always step upward one step or two steps at the time?
3. Number of partitioning. Given a number n; how many ways can we express the number as the
sum of 1 and 2? Order matters. For example, 1 + 2 + 2 and 2 + 1 + 2 are two different partitions of 5.

c Hidegkuti, 2019 Last revised: September 29, 2019

Lecture Notes The Fibonacci Sequence page 2

Part 2 - The Fibonacci Sequence and the Golden Mean

The Fibonacci
p sequece has strange and beautiful properties. A lot of these properties are connected to the golden mean,
1+ 5
ϕ= 1: 618 033 988 75.
2

Consider now another sequence, fqn g that is formed by taking the quotients of consecutive term in the Fibonacci sequence.
1 2 3 5 8 13
That is, ; ; ; ; ; ;.....
1 1 2 3 5 8
Fn+1
qn = for all natural number n.
F1
The decimal presentations of the rst few terms in this sequence show an interesting pattern.

F2 1 F6 8
= =1 = = 1:6
F1 1 F5 5
F3 2 F7 13
= =2 = = 1:625
F2 1 F6 8
F4 3 F8 21
= = 1:5 = 1:615 384 6
F3 2 F7 13
F5 5 F9 34
= 1:66667 = 1: 619 047 62
F4 3 F8 21

The quotients oscillate back and forth and seem to be closer and closer to each other. Amazingly, there is only one number
that is inside all of the "swirls" shown on the picture above. These ratios approach a single number. We call this number the
limit of this sequence and we compute its exact value in the sample problems.

.
De nition: A Fibonacci-type of a sequence starts with any two real numbers and the rest of the sequence
is generated the same way the Fibonacci sequence is.

f1 ; f2 2 R and for all n 1, fn + fn+1 = fn+2

Suppose we start with f1 = 3 and f2 = 4. The rst few terms of this Fibonacci-type sequence are

3; 4; 7; 11; 15; 26; 41; 67; 108; 175; : : :

We can de ne operations on Fibonacci-type sequences. Consider fan g and fbn g de ned as follows:

fan g : 3; 4; 7; 11; 18; 29; 47; 76; 123; 199; : : :

fbn g : 2; 7; 9; 16; 25; 41; 66; 107; 173; 280; : : :

We can multiply a sequence by a number by multiplying each term by that number:

2 fan g : 6; 8; 14; 22; 30; 52; 82; 134; 216; 350; : : :

and the resulting sequence is still Fibonacci-type.

c Hidegkuti, 2019 Last revised: September 29, 2019

Lecture Notes The Fibonacci Sequence page 3

We can also add two sequences by adding them term by term:

cn = an + bn

cn = fan + bn g : 5; 11; 16; 27; 43; 70; 113; 183; : : :

and the sum is again Fibonacci-type. Also, it is very easy to see that every Fibonacci-type sequence is uniquely determined
by its rst two terms.

These properties are used when we derive the explicit formula for the nth term of the Fibonacci sequence. The following
problems lead us through the steps.

Sample Problems

1. Solve the equation x2 = x + 1.

p p
1+ 5 1 5
2. De ne ϕ = and ψ = . Prove each of the following.
2 2
a) ϕ + ψ = 1 b) ϕψ = 1

3. Find the limit of of the sequence formed from consecutive terms in the Fibonacci sequence. In short,
Fn+1
compute lim .
n!∞ Fn

4. Consider a Fibonacci-type of a sequence with rst term 1 and second term x. Is there a value of x for which all terms of
the sequence fall between 100 and 100?

5. De nition: A geometric sequence is de ned as a; ar; ar2 ; ar3 ; ar4 ; ::::::. The number r is called the common ratio of the
an+1
sequence because if r 6= 0, then r = for all n 2 N. It is clear that a geometric sequence is determined by its rst
an
element and common ratio. One great advantage of a geometric sequence over a Fibonacci-type of a sequence is that
there is a very easy explicit formula for the nth term of the sequence: an = arn 1 :
Is there a Fibonacci-type sequence that is also a geometric series?
p
1+ 5
6. Consider the geometric sequence de ned by rst element 1 and common ratio r = . Compute the exact value of
2
the 9th term in the sequence.

7. Use results form the previous problems to nd the explicit formula for the nth term of the Fibonacci sequence.

c Hidegkuti, 2019 Last revised: September 29, 2019

Lecture Notes The Fibonacci Sequence page 4

Solutions - Enrichment Problems

2. Prove that any two consecutive terms of the Fibonacci sequence are relatively prime.
Solution: this is an interesting application of proofs by contradiction.
Suppose for a contradiction that there exist two consecutive terms Fk and Fk+1 (for some natural number k) that are not
relatively prime. Then there exists a positive integer d > 1 such that d is a divisor of both Fk and Fk+1 . So Fk = αd
and Fk+1 = β d. for some positive integers α and β We claim that then d is also a divisor of Fk 1 .

Fk + Fk 1 = Fk+1
Fk 1 = Fk+1 Fk = β d αd = d (β α)

Thus d also divides Fk 1 . Next we similarly prove that d is then also a divisor of Fk 2 and Fk 3 ; and so on, all the way
till F1 . Thus d is a divisor of F1 = 1. This is impossible because d > 1 This is a contradiction completing our proof.

Solutions - Sample Problems

1. Solve the equation x2 = x + 1
Solution 1. Using the quadratic formula x2 x 1 = 0
p p
1 1 ( 4) 1 5
x1;2 = =
2 2
Solution 2. Completing the square
2
1 1
x2 x 1 = 0 x = x2 x+
2 4
1 1
x2 x + 1 = 0
| {z 4} 4
2
1 5
x = 0
2 4
2 p !2
1 5
x = 0
2 2
p ! p !
1 5 1 5
x + x = 0
2 2 2 2
p p p p
1 5 1 5 1 5 1+ 5
x1 = = x2 = + =
2 2 2 2 2 2

p p
1+ 5 1 5
2. De ne ϕ = and ψ = . Prove each of the following.
2 2
a) ϕ + ψ = 1
p p p p
Solution: 1+ 5 1 5 1+ 5+1 5 2
ϕ +ψ = + = = =1
2 2 2 2

b) ϕψ = 1
p p p p
Solution: 1+ 5 1 5 1+ 5 1 5 1 5
ϕψ = = = = 1
2 2 4 4

c Hidegkuti, 2019 Last revised: September 29, 2019

Lecture Notes The Fibonacci Sequence page 5

3. Find the limit of of the sequence formed from consecutive terms in the Fibonacci sequence. In short,
Fn+1
compute lim .
n!∞ Fn
Solution 1: Let us assume rst that the consecutive terms
1 2 3 5 8 13 21 34 55 89 144
; ; ; ; ; ; ; ; ; ; ; :::
1 1 2 3 5 8 13 21 34 55 89
do approach a single number x. Imagine we are much further into the sequence, after millions and millions of terms.
Then these numbers are very close to x and thus also very close to each other. Sort of like

89 144
x we are in the Fibonacci sequence: 144 = 89 + 55
55 89
89 89 + 55
55 89
89 89 55
+
55 89 89
89 55
1+
55 89
1
x 1+
x
Using more general notation, we arrive to the same conclusion. For very large values of n,

Fn+1 Fn+2
x we are in the Fibonacci sequence: Fn+2 = Fn + Fn+1
Fn Fn+1
Fn+1 Fn + Fn+1
Fn Fn+1
Fn+1 Fn Fn+1
+
Fn Fn+1 Fn+1
Fn+1 Fn
+1
Fn Fn+1
1
x +1
x
1
We solve the equation x = 1 +
x
1
x = +1 multiply by x
x
x2 = 1+x
x2 x 1 = 0
p
1 5
x1;2 =
2
p
1 5
We rule out because it is negative, and the sequence clearly approaches a number above 0:6. The other solution,
p 2
1+ 5
, the golden mean is the limit.
2

c Hidegkuti, 2019 Last revised: September 29, 2019

Lecture Notes The Fibonacci Sequence page 6

Solution 2: This is the same computation but this time it is presented using limit notation from calculus.
Fn+1
Let us denote lim by x.
n!∞ Fn

Fn+1 Fn+2 Fn+1 Fn

lim = lim lim = lim +1
n!∞ Fn n!∞ Fn+1 n!∞ Fn n!∞ Fn+1
Fn+1 Fn + Fn+1 1
lim = lim x = +1
n!∞ Fn n!∞ Fn+1 x
Fn+1 Fn Fn+1 x2 = 1 + x
lim = lim +
n!∞ Fn n!∞ Fn+1 Fn+1 x2 x 1 = 0
p
Fn+1 Fn 1 5
lim = lim +1 x1;2 =
n!∞ Fn n!∞ Fn+1 2
p
1 5
We rule out because it is negative, and the sequence clearly approaches a number above 0:6. The other solution,
2 p
Fn+1 1 + 5
the golden mean is the limit. lim = .
n!∞ Fn 2

4. Consider a Fibonacci-type of a sequence with rst term 1 and second term x. Is there a value of x for which all terms of
the sequence fall between 100 and 100?
Solution: The Fibonacci sequence vey quickly becomes very large. The question is: how can we ensure that the terms
of the sequence do not become large? Consider a Fibonacci-type sequence with rst term 1 and second term x.

1; x; x + 1; 2x + 1; 3x + 2; 5x + 3; 8x + 5; 13x + 8; 21x + 13; : : : :

eventually the terms are Fn + Fn 1 x. If x is positive, even if tiny, the other part alone, Fn will ensure that the nth term is
very large. Thus, if we want the terms to stay small, we need x to be negative.
This idea can be generalized. We want every second term positive and every other term negative, because two
consecutive terms with the same sign guarantee that the terms after that get very large. Suppose that a and b are
two consecutive terms with the same sign. Then from then on, we have that

a; b; a + b; a + 2b; 2a + 3b; 3a + 5b; 5a + 8b; : : : ; Fn a + Fn+1 b ; : : : :

So we want alternating sings in the sequence

1; x; x + 1; 2x + 1; 3x + 2; 5x + 3; 8x + 5; 13x + 8; 21x + 13; : : : :

That is: 1 positive, 2x + 1 negative, 8x + 5 positive,

x negative, 3x + 2 positive, 13x + 8 negative,
x + 1 positive, 5x + 3 negative, 21x + 13 positive, and so on.
We solve all these inequalities:

x<0 x+1 > 0 2x + 1 < 0 3x + 2 > 0 5x + 3 < 0

x> 1 2x < 1 3x > 2 5x < 3
1 2 3
x< x> x<
2 3 5
8x + 5 > 0 13x + 8 < 0 21x + 13 > 0
8x > 5 13x < 8 21x > 13
5 8 13
x> x< x>
8 13 21

c Hidegkuti, 2019 Last revised: September 29, 2019

Lecture Notes The Fibonacci Sequence page 7

It appears that x must be between the values we previously obtained by taking the quotient of consecutive terms of the
Fibonacci sequence. These ratios display a strange behavior, they spiral around over a smaller and smaller interval
Fn Fn+1
(see problem 3). The only difference here is that we are looking at instead of . The ratios in this problem
Fn+1 Fn p
2 1 5
approach the negative reciprocal of the golden mean. We rationalize p and obtain . This is the only
5+1 2
number that will work for x. This sequence will have terms with alternating signs and thus each term will have a smaller
absolute value than the previous term. It is an amazing thought that for any other values of x, the sequence will reach
huge numbers and outgrow any bound.
We can present a bit more formal computation: denote the sequence by an :

fan g : 1; x; x + 1; 2x + 1; 3x + 2; 5x + 3; 8x + 5; 13x + 8; 21x + 13; : : : :

Notice that for all n 3

an = Fn 1 x + Fn 2

where fFn g is the Fibonacci sequence.

fFn g : 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144

We want a1 , a3 , a5 ,... positive and a2 ; a4 ; a6 ;... negative. For all n, we need a2n+1 > 0 and a2n < 0.

a2n = F2n 1 x + F2n 2 and a2n+1 = F2n x + F2n 1

F2n 1 x + F2n 2 > 0 and F2n x + F2n 1 < 0

F2n 2 F2n 1
x > and x < for all n
F2n 1 F2n
F2n 2 F2n 1
< x< for all n
F2n 1 F2n

Since these quotiens oscillate around and enclose only a single number, x must be that number. Thus
p
F2n 1 1 1 1 5
x = lim = = p =
n!∞ F2n F m+1 1+ 5 2
lim
m!∞ Fm 2

5. De nition: A geometric sequence is de ned as a; ar; ar2 ; ar3 ; ar4 ; ::::::. The number r is called the common ratio of the
an+1
sequence because if r 6= 0, then r = for all n 2 N. It is clear that a geometric sequence is determined by its rst
an
element and common ratio. One great advantage of a geometric sequence over a Fibonacci-type of a sequence is that
there is a very easy explicit formula for the nth term of the sequence: an = arn 1 :
Is there a Fibonacci-type sequence that is also a geometric series?
Solution: Let fan g be a Fibonacci-type geometric sequence with rst element a and comon ratio r. Then the rst three
elements (since geometric) are
a; ar; ar2
Let us assume that a 6= 0. (The constant zero sequence is both Fibonacci-type and geometric, but not very interesting.)

c Hidegkuti, 2019 Last revised: September 29, 2019

Lecture Notes The Fibonacci Sequence page 8

The sequence is also Fibonacci-type and so

a + ar = ar2
0 = ar2 ar a factor out a
0 = a r2 r 1 divide by a
2
0 = r r 1
p p
1 12 ( 4) 1 5
r1;2 = =
2 2
At this point, we are not surprised thatp we again ran into
p the golden mean. Both solutions work, which will be very
1+ 5 1 5
useful later on. Recall that ϕ = and ψ = .
2 2
Suppose that a = 1. Then one sequence is 1; ϕ; ϕ 2 ; ϕ 3 ; : : : is an increasing sequence that grows unbounded. The
other sequence is 1; ψ; ψ 2 , ψ 3 is a sequence with alternating sings and thus small terms, and the two sequences appear
to be conjugates of each other, term by term.
p
1 5
The computation above shows that only the geometric sequence with r = will result in a non-zero Fibonacci-type
2
sequence. On the other hand, all other such sequences are just constant muliples of these two. All Fibonacci-type
sequences that are also geometric sequences are of the form

a; aϕ; aϕ 2 ; aϕ 3 ; :::: and a; aψ; aψ 2 ; aψ 3 ; ::::

What makes these sequences special is that their nth term can be determined by an explicit formula because they are
also geometric sequences.
p
1+ 5
6. Consider the geometric sequence de ned by rst element 1 and common ratio r = . Compute the exact value of
2
the 9th term in the sequence.
p !8 p !8
Solution: 8 1+ 5 1+ 5
a9 = ar = 1 =
2 2

p !2 p !2 p 2
p p
1+ 5 1+ 5 1+ 5 6+2 5 3+ 5
We start with : = = =
2 2 22 4 2
We square this number:

p !4 2 p !2 32 p !2 p
3+ 5
2
p p
1+ 5 1 + 5 5 3+ 5 14 + 6 5 7 + 3 5
=4 = = = =
2 2 2 22 4 2

p !8 2 p !4 32 p !2 p 2
7+3 5 p
1+ 5 4 1 + 5 5 7 + 3 5 49 + 45 + 42 5
We square again: = = = =
2 2 2 22 4
p p p p
49 + 45 + 42 5 94 + 42 5 47 + 21 5 47 + 21 5
= = = and so a9 = .
4 4 2 2
This might seem laborous but if n is large, it is still much better than having to compute all previous terms.

c Hidegkuti, 2019 Last revised: September 29, 2019

Lecture Notes The Fibonacci Sequence page 9

7. Use results form the previous problems to nd the explicit formula for the nth term of the Fibonacci sequence.
Solution: We will express the Fibonacci sequence as the sum of two Fibonacci-type geometric sequences.
First, we need to verify that the constant mutplies and sums of Fibonacci-type sequences are still Fibonacci-type.
Second, we will use the fact that the rst two elements uniquely determine any Fibonaccy-type of sequence.
p p
1+ 5 1 5
De ne fan g and fbn g geometric sequences as follows. a1 = 1 and ra = ϕ = and b1 = 1 and rb = ψ = .
2 2
Thus
p !n 1 p !n 1
n 1 1+ 5 n 1 1 5
an = ϕ = and bn = ϕ =
2 2
These sequences are also Fibonacci-type (see problem 5). Thus, any constant multiples and sums formed from these
sequences will still be Fibonacci-type. Could we use fan g and fbn g to "concoct" the Fibonacci sequence?
Let x and y be real numbers such that for all n

cn = xan + ybn and c1 = 1 and c2 = 1

If we could nd such x and y, we would be done because a Fibonacci-type sequence that begins with 1 and 1 is THE
bonacci-sequence.
1 = c1 = xa1 + yb1 and 1 = c2 = xa2 + yb2
(
xa1 + yb1 = 1
We solve for x and y in terms of an and bn in the system
xa2 + yb2 = 1
(
x+y = 1
Since a1 = b1 = 1, and a2 = ϕ and b2 = ψ; the system above is the same as
xϕ + yψ = 1

x + y = 1 =) y = 1 x substitute this into other equation

xϕ + yψ = 1
xϕ + (1 x) ψ = 1
xϕ + ψ ψx = 1
xϕ ψx = 1 ψ
1 ψ
x (ϕ ψ) = 1 ψ =) x=
ϕ ψ

p p p
1 51+ 5 2 1+ 5 p p
1 ψ 1 1+ 5 1 1+ 5
x = = p 2 p = 2 2
= p = p = p
p p 2
ϕ ψ 1+ 5 1 5 1+ 5 1 5 2 5 5 2 5
2 2 2
2
p p p
5 1+ 5 5+ 5
= =
2 5 10
p
5+ 5
Thus x = . Then
10 p
p p
5 + 5 10 5+ 5 5 5
y=1 x=1 = =
10 10 10

So We found x and y so that Fn = xan + ybn .

c Hidegkuti, 2019 Last revised: September 29, 2019

Lecture Notes The Fibonacci Sequence page 10

p p !n 1 p p !n 1
5+ 5 1+ 5 5 5 1 5
Fn = xan + ybn = +
10 2 10 2
p p p p p
5 5 5 5 1 5 5 1
We can further simplify this result. Notice that = =
10 5 2 5 2
p p p !n 1 p p p !n 1
5 5+1 1+ 5 5 5 1 1 5 p p
Fn = + 5 1= 1 5
5 2 2 5 2 2
p 2p p !n 1 p p !n 1 3 p " p !n p !n #
5 4 5+1 1+ 5 1 5 1 5 5= 5 1 + 5 1 5
=
5 2 2 2 2 5 2 2

" p !n p !n #
1 1+ 5 1 5
So, Fn = p
5 2 2

This formula seems very unlikely to produce integers. Let us see the rst few elements generated by the formula.
p ! p !! p p p
1 1+ 5 1 5 1 1+ 5 1+ 5 1 2 5
F1 = p =p =p =1
5 2 2 5 2 5 2

0 p !2 p !2 1 p p ! p p
1 @ 1+ 5 1 5 A 1 3+ 5 3 5 1 3+ 5 3+ 5
F2 = p =p =p
5 2 2 5 2 2 5 2
p
1 2 5
= p =1
5 2
This is already proof that the formula determines the Fibonacci sequece. But, just for fun, let us compute F3 . We rst
p !3
1+ 5
compute .
2

p !3 p ! p !2 p ! p ! p p p
1+ 5 1+ 5 1+ 5 1+ 5 3+ 5 1 + 5 3 + 5 8+4 5 p
= = = = = 2+ 5
2 2 2 2 2 4 4

p !3
1 5
We similarly obtain the exact value of and then we are ready to compute F3 .
2
0 p !3 p !3 1
1 @ 1+ 5 1 5 A 1 p p 1 p
F3 = p =p 2+ 5 2 5 = p 2 5=2
5 2 2 5 5

So, our formula produces 1, 1, and then 2:

For more documents like this, visit our page at http://www.teaching.martahidegkuti.com and click on Lecture Notes. E-mail
questions or comments to mhidegkuti@ccc.edu.

c Hidegkuti, 2019 Last revised: September 29, 2019