Fibonacci Numbers and the

Golden Ratio

Lecture Notes for

Jeffrey R. Chasnov
 The Hong Kong University of Science and Technology
Department of Mathematics
Clear Water Bay, Kowloon
Hong Kong

Copyright ○
c 2016-2022 by Jeffrey Robert Chasnov

This work is licensed under the Creative Commons Attribution 3.0 Hong Kong License. To view
a copy of this license, visit http://creativecommons.org/licenses/by/3.0/hk/ or send a letter to
Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA.
Preface
View the promotional video on YouTube

These are my lecture notes for my online Coursera course, Fibonacci Numbers and the
Golden Ratio. These lecture notes are divided into chapters called Lectures, and each
Lecture corresponds to a video on Coursera. I have also uploaded the Coursera videos to
YouTube, and links are placed at the top of each Lecture.
Most of the Lectures also contain problems for students to solve. Less experienced
students may find some of these problems difficult. Do not despair! The Lectures can be
read and watched, and the material understood and enjoyed without actually solving any
problems. But mathematicians do like to solve problems and I have selected those that I
found to be interesting. Try some of them, but if you get stuck, full solutions can be read
in the Appendix.
My aim in writing these lecture notes was to place the mathematics at the level of an
advanced high school student. Proof by mathematical induction and matrices, however,
may be unfamiliar to a typical high school student and I have provided a short and
hopefully readable discussion of these topics in the Appendix. Although all the material
presented here can be considered elementary, I suspect that some, if not most, of the
material may be unfamiliar to even professional mathematicians since Fibonacci numbers
and the golden ratio are topics not usually covered in a University course. So I welcome
both young and old, novice and experienced mathematicians to peruse these lecture notes,
watch my lecture videos, and solve some problems. I hope you enjoy the wonders of the
Fibonacci sequence and the golden ratio!
Contents

I Fibonacci: It’s as Easy as 1, 1, 2, 3 1

1 The Fibonacci sequence 2

2 The Fibonacci sequence redux 4

Practice quiz: The Fibonacci numbers 6

3 The golden ratio 7

4 Fibonacci numbers and the golden ratio 9

5 Binet’s formula 11

Practice quiz: The golden ratio 14

II Identities, Sums and Rectangles 15

6 The Fibonacci Q-matrix 16

7 Cassini’s identity 19

8 The Fibonacci bamboozlement 21

Practice quiz: The Fibonacci bamboozlement 24

9 Sum of Fibonacci numbers 25

10 Sum of Fibonacci numbers squared 27

Practice quiz: Fibonacci sums 29

11 The golden rectangle 30

12 Spiraling squares 32

III The Most Irrational Number 35

13 The golden spiral 36

14 An inner golden rectangle 39

15 The Fibonacci spiral 42

Practice quiz: Spirals 44

iv
 CONTENTS v

16 Fibonacci numbers in nature 45

17 Continued fractions 46

18 The golden angle 49

19 The growth of a sunflower 51

Practice quiz: Fibonacci numbers in nature 53

Appendices 54

A Mathematical induction 55

B Matrix algebra 56
B.1 Addition and Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
B.2 Determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

C Problem and practice quiz solutions 59

 Week I

Fibonacci: It’s as Easy as 1, 1, 2, 3

In this week’s lectures, we learn about the Fibonacci numbers, the golden ratio, and their relation-
ship. We conclude the week by deriving the celebrated Binet’s formula, an explicit formula for the
Fibonacci numbers in terms of powers of the golden ratio and its reciprocal.

1
Lecture 1 | The Fibonacci sequence
View this lecture on YouTube

Fibonacci published in the year 1202 his now famous rabbit puzzle:

A man put a male-female pair of newly born rabbits in a field. Rabbits take a
month to mature before mating. One month after mating, females give birth to
one male-female pair and then mate again. No rabbits die. How many rabbit
pairs are there after one year?

To solve, we construct Table 1.1. At the start of each month, the number of juvenile
pairs, adult pairs, and total number of pairs are shown. At the start of January, one pair
of juvenile rabbits is introduced into the population. At the start of February, this pair
of rabbits has matured. At the start of March, this pair has given birth to a new pair of
juvenile rabbits. And so on.

month J F M A M J J A S O N D J
juvenile 1 0 1 1 2 3 5 8 13 21 34 55 89
adult 0 1 1 2 3 5 8 13 21 34 55 89 144
total 1 1 2 3 5 8 13 21 34 55 89 144 233

Table 1.1: Fibonacci’s rabbit population.

We define the Fibonacci numbers Fn to be the total number of rabbit pairs at the start
of the nth month. The number of rabbits pairs at the start of the 13th month, F13 = 233,
can be taken as the solution to Fibonacci’s puzzle.
Further examination of the Fibonacci numbers listed in Table 1.1, reveals that these
numbers satisfy the recursion relation

Fn+1 = Fn + Fn−1 . (1.1)

This recursion relation gives the next Fibonacci number as the sum of the preceeding
two numbers. To start the recursion, we need to specify F1 and F2 . In Fibonacci’s rabbit
problem, the initial month starts with only one rabbit pair so that F1 = 1. And this initial
rabbit pair is newborn and takes one month to mature before mating so F2 = 1.
The first few Fibonacci numbers, read from the table, are given by

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, . . .

and has become one of the most famous sequences in mathematics.

2
 WEEK I. FIBONACCI: IT’S AS EASY AS 1, 1, 2, 3 3

Problems for Lecture 1

1. The Fibonacci numbers can be extended to zero and negative indices using the relation
Fn = Fn+2 − Fn+1 . Determine F0 and find a general formula for F−n in terms of Fn . Prove
your result using mathematical induction.

2. The Lucas numbers are closely related to the Fibonacci numbers and satisfy the same
recursion relation Ln+1 = Ln + Ln−1 , but with starting values L1 = 1 and L2 = 3. Deter-
mine the first 12 Lucas numbers.

3. The generalized Fibonacci sequence satisfies f n+1 = f n + f n−1 with starting values
f 1 = p and f 2 = q. Using mathematical induction, prove that

f n+2 = Fn p + Fn+1 q. (1.2)

4. Prove that
Ln = Fn−1 + Fn+1 . (1.3)

5. Prove that
1
Fn = (L + L n +1 ) .
5 n −1
6. The generating function for the Fibonacci sequence is given by the power series

∞
f (x) = ∑ Fn xn .
n =1

Assuming the power series converges, prove that

x
f (x) = .
1 − x − x2

Solutions to the Problems

Lecture 2 | The Fibonacci sequence redux
View this lecture on YouTube

We can solve another puzzle that also leads to the Fibonacci sequence:

How many ways can one climb a staircase with n steps, taking one or two
steps at a time?

Any single climb can be represented by a string of ones and twos which sum to n. We
define an as the number of different strings that sum to n. In Table 1, we list the possible
strings for the first five values of n. It appears that the an ’s form the beginning of the
Fibonacci sequence.
To derive a relationship between an and the Fibonacci numbers, consider the set of
strings that sum to n. This set may be divided into two nonoverlapping subsets: those
strings that start with one and those strings that start with two. For the subset of strings
that start with one, the remaining part of the string must sum to n − 1; for the subset of
strings that start with two, the remaining part of the string must sum to n − 2. Therefore,
the number of strings that sum to n is equal to the number of strings that sum to n − 1
plus the number of strings that sum to n − 2. The number of strings that sum to n − 1 is
given by an−1 and the number of strings that sum to n − 2 is given by an−2 , so that

a n = a n −1 + a n −2 .

And from the table we have a1 = 1 = F2 and a2 = 2 = F3 , so that an = Fn+1 for all positive
integers n.

n strings an
1 1 1
2 11, 2 2
3 111, 12, 21 3
4 1111, 112, 121, 211, 22 5
5 11111, 1112, 1121, 1211, 2111, 122, 212, 221 8

Table 2.1: Strings of ones and twos that add up to n.

4
 WEEK I. FIBONACCI: IT’S AS EASY AS 1, 1, 2, 3 5

Problems for Lecture 2

1. Consider a string consisting of the first n natural numbers, 123 . . . n. For each number
in the string, allow it to either stay fixed or change places with one of its neighbors. Define
an to be the number of different strings that can be formed. Examples for the first four
values of n are shown in Table 2.2. Prove that an = Fn+1 .

n strings an
1 1 1
2 12, 21 2
3 123, 132, 213 3
4 1234, 1243, 1324, 2134, 2143 5

Table 2.2: Strings of natural numbers obtained by allowing a number to stay fixed or
change places with its neighbor.

2. Consider a problem similar to that above, but now allow the first 1 to change places
with the last n, as if the string lies on a circle. Suppose n ≥ 3, and define bn as the number
of different strings that can be formed. Show that bn = Ln , where Ln is the nth Lucas
number.

Solutions to the Problems

Practice Quiz | The Fibonacci numbers
1. In Fibonacci’s rabbit problem, the number of adult rabbit pairs in the fifth month is

a) 1

b) 2

c) 3

d) 5

2. The Fibonacci number denoted as F−5 is

a) -8

b) -5

c) 5

d) 8

3. Which of the following statements are true:

A. Ln = Fn−2 + 3Fn−1
B. Ln = Fn−1 + Fn+1

a) A only

b) B only

c) Both A and B

d) Neither A nor B

Solutions to the Practice quiz

6
Lecture 3 | The golden ratio
View this lecture on YouTube

x y

Figure 3.1: The golden ratio satisfies x/y = ( x + y)/x.

We now present the classical definition of the golden ratio. Referring to Fig. 3.1, two
positive numbers x and y, with x > y are said to be in the golden ratio if the ratio
between the larger number and the smaller number is the same as the ratio between their
sum and the larger number, that is,

x x+y
= . (3.1)
y x

Denoting Φ = x/y to be the golden ratio, (Φ is the capital Greek letter Phi), the relation
(3.1) becomes
1
Φ = 1+ , (3.2)
Φ
or equivalently Φ is the positive root of the quadratic equation

Φ2 − Φ − 1 = 0. (3.3)

Straightforward application of the quadratic formula results in

√
5+1
Φ= ≈ 1.618.
2

The negative of the negative root of the quadratic equation (3.3) is what we will call the
golden ratio conjugate φ, (the small Greek letter phi), and is equal to
√
5−1
φ= ≈ 0.618.
2

The relationship between the golden ratio conjugate φ and the golden ratio Φ, is given by

φ = Φ − 1,

or using (3.2),
1
φ= .
Φ

7
 WEEK I. FIBONACCI: IT’S AS EASY AS 1, 1, 2, 3 8

Problems for Lecture 3

1. The golden ratio Φ and the golden ratio conjugate φ can be defined as
√ √
5+1 5−1
Φ= , φ= .
2 2

From these definitions, prove the following identities by direct calculation:

(a) φ = Φ − 1,

(b) φ = 1/Φ,

(c) Φ2 = Φ + 1,

(d) φ2 = −φ + 1,

2. Prove that the golden ratio satisfies the Fibonacci-like relationship

Φ n +1 = Φ n + Φ n −1 .

3. Prove that the golden ratio conjugate satisfies

φ n −1 = φ n + φ n +1 .

Solutions to the Problems

Lecture 4 | Fibonacci numbers and the
golden ratio
View this lecture on YouTube

The recursion relation for the Fibonacci numbers is given by

Fn+1 = Fn + Fn−1 .

Dividing by Fn yields
Fn+1 F
= 1 + n −1 . (4.1)
Fn Fn
We assume that the ratio of two consecutive Fibonacci numbers approaches a limit as
n → ∞. Define limn→∞ Fn+1 /Fn = α so that limn→∞ Fn−1 /Fn = 1/α. Taking the limit,
(4.1) becomes α = 1 + 1/α, the same identity satisfied by the golden ratio. Therefore, if
the limit exists, the ratio of two consecutive Fibonacci numbers must approach the golden
ratio for large n, that is,
Fn+1
lim = Φ.
n→∞ Fn
The ratio of consecutive Fibonacci numbers and this ratio minus the golden ratio is shown
in Table 4.1. The last column appears to be approaching zero.

n Fn+1 /Fn value Fn+1 /Fn − Φ

1 1/1 1.0000 −0.6180
2 2/1 2.0000 0.3820
3 3/2 1.5000 −0.1180
4 5/3 1.6667 0.0486
5 8/5 1.6000 −0.0180
6 13/8 1.6250 0.0070
7 21/13 1.6154 −0.0026
8 34/21 1.6190 0.0010
9 55/34 1.6176 −0.0004
10 89/55 1.6182 0.0001

Table 4.1: Ratio of consecutive Fibonacci numbers approaches Φ.

9
 WEEK I. FIBONACCI: IT’S AS EASY AS 1, 1, 2, 3 10

Problems for Lecture 4

1. Assuming limn→∞ Fn+1 /Fn = Φ, prove that

Fk+n
lim = Φn .
k→∞ Fk

2. Using Φ2 = Φ + 1, prove by mathematical induction the following linearization of

powers of the golden ratio:
Φn = Fn Φ + Fn−1 , (4.2)

where n is a positive integer and F0 = 0.

3. Using φ2 = −φ + 1, prove by mathematical induction the following linearization of

powers of the golden ratio conjugate:

(−φ)n = − Fn φ + Fn−1 , (4.3)

where n is a positive integer and F0 = 0.

Solutions to the Problems

Lecture 5 | Binet’s formula
View this lecture on YouTube

The Fibonacci numbers are uniquely determined from their recursion relation,

Fn+1 = Fn + Fn−1 , (5.1)

and the initial values, F1 = F2 = 1. An explicit formula for the Fibonacci numbers can be
found, and is called Binet’s Formula.
To solve (5.1) for the Fibonacci numbers, we first look at the equation

x n +1 = x n + x n −1 . (5.2)

This equation is called a second-order, linear, homogeneous difference equation with con-
stant coefficients, and its method of solution closely follows that of the analogous differen-
tial equation. The idea is to guess the general form of a solution, find two such solutions,
and then multiply these solutions by unknown constants and add them. This results in
a general solution to (5.2), and one can then solve (5.1) by satisfying the specified initial
values.
To begin, we guess the form of the solution to (5.2) as

xn = λn , (5.3)

where λ is an unknown constant. Substitution of this guess into (5.2) results in

λ n +1 = λ n + λ n −1 ,

or upon division by λn−1 and rearrangement of terms,

λ2 − λ − 1 = 0.

Use of the quadratic formula yields two roots, both of which are already familiar. We
have √ √
1+ 5 1− 5
λ1 = = Φ, λ2 = = −φ,
2 2
where Φ is the golden ratio and φ is the golden ratio conjugate.
We have thus found two independent solutions to (5.2) of the form (5.3), and we can
now use these two solutions to find a solution to (5.1). Multiplying the solutions by
constants and adding them, we obtain

Fn = c1 Φn + c2 (−φ)n , (5.4)

which must satisfy the initial values F1 = 1 and F2 = 1. The algebra for finding the
unknown constants can be made simpler, however, if instead of F2 , we use the value
F0 = F2 − F1 = 0.

11
 WEEK I. FIBONACCI: IT’S AS EASY AS 1, 1, 2, 3 12

Application of the values for F0 and F1 results in the system of equations given by

c1 + c2 = 0,
c1 Φ − c2 φ = 1.

We use the first equation to write c2 = −c1 , and substitute into the second equation to get

c1 (Φ + φ) = 1.
√
Since Φ + φ = 5, we can solve for c1 and c2 to obtain
√ √
c1 = 1/ 5, c2 = −1/ 5. (5.5)

Using (5.5) in (5.4) then derives the surprising formula

Φn − (−φ)n
Fn = √ , (5.6)
5

known as Binet’s formula.

 WEEK I. FIBONACCI: IT’S AS EASY AS 1, 1, 2, 3 13

Problems for Lecture 5

1. Prove Binet’s formula (5.6) by mathematical induction.

2. Use Binet’s formula to prove the limit

lim Fn+1 /Fn = Φ.

n→∞

3. Use the linearization formulas

Φn = Fn Φ + Fn−1 (5.7)
n
(−φ) = − Fn φ + Fn−1 (5.8)

to derive Binet’s formula.

4. Use the generating function for the Fibonacci sequence

∞
x
∑ Fn xn = 1 − x − x2
n =1

to derive Binet’s formula.

5. Determine the analogue to Binet’s formula for the Lucas numbers, defined as

L n +1 = L n + L n −1

with the initial values L1 = 1 and L2 = 3. Again it will be simpler to define the value of
L0 and use it and L1 as the initial values.

6. Use Binet’s formula for Fn and the analogous formula for Ln to show that
√
Ln + 5Fn
n
Φ = .
2

Solutions to the Problems

Practice Quiz | The golden ratio
1. Define the golden ratio Φ and the golden ratio conjugate φ by
√ √
5+1 5−1
Φ= , φ= .
2 2

Select all that are true.

a) φ = Φ − 1

b) Φ = 1/φ

c) φ2 = φ − 1

d) Φ2 = Φ + 1

2. The analogue to Binet’s formula for the Lucas numbers is given by

a) Ln = Φn + (−φ)n

Φn − (−φ)n
b) Ln = √
5

Φn + (−φ)n
c) Ln = √
5
d) Ln = Φn − (−φ)n

3. Select all that are true.

a) Φn = Fn Φ + Fn−1

b) Φn = Fn Φ − Fn−1

c) φn = − Fn φ + Fn−1

d) (−φ)n = − Fn φ + Fn−1

Solutions to the Practice quiz

14
 Week II

Identities, Sums and Rectangles

In this week’s lectures, we learn about the Fibonacci Q-matrix and Cassini’s identity. Cassini’s
identity is the basis for a famous dissection fallacy colorfully named the Fibonacci bamboozlement.
A dissection fallacy is an apparent paradox arising from two arrangements of different area from
one set of puzzle pieces. We also derive formulas for the sum of the first n Fibonacci numbers,
and the sum of the first n Fibonacci numbers squared. Finally, we show how to construct a golden
rectangle, and how this leads to the beautiful image of spiraling squares.

15
Lecture 6 | The Fibonacci Q-matrix
View this lecture on YouTube

month J F M A M J J A S O N D J
juvenile 1 0 1 1 2 3 5 8 13 21 34 55 89
adult 0 1 1 2 3 5 8 13 21 34 55 89 144

Table 6.1: Fibonacci’s rabbit population consists of juveniles and adults.

Consider again Fibonacci’s growing rabbit population of juvenile and adult rabbit pairs
shown in Table 6.1. Let an denote the number of adult rabbit pairs at the start of month
n, and let bn denote the number of juvenile rabbit pairs. The number of adult pairs at the
start of month n + 1 is just the sum of the number of adult and juvenile pairs at the start
of month n. The number of juvenile pairs at the start of month n + 1 is just the number of
adult pairs at the start of month n. This can be written as a system of recursion relations
given by

a n + 1 = a n + bn ,
bn + 1 = a n ;

or in matrix form as ! ! !
a n +1 1 1 an
= . (6.1)
bn +1 1 0 bn

The matrix in (6.1) is called the Fibonacci Q-matrix, defined as

!
1 1
Q= . (6.2)
1 0

Repeated multiplication by Q advances the population additional months. For example,

advancing k months is achieved by
! !
an+k an
= Qk .
bn + k bn

Powers of the Q-matrix are related to the Fibonacci sequence. Observe what happens
when we multiply an arbitrary matrix by Q. We have
! ! !
1 1 a b a+c b+d
= .
1 0 c d a b

Multiplication of a matrix by Q replaces the first row of the matrix by the sum of the first
and second rows, and the second row of the matrix by the first row.

16
 WEEK II. IDENTITIES, SUMS AND RECTANGLES 17

If we rewrite Q itself in terms of the Fibonacci numbers as

!
F2 F1
Q= ,
F1 F0

and then make use of the Fibonacci recursion relation, we find

! ! !
1 1 F2 F1 F3 F2
Q2 = = .
1 0 F1 F0 F2 F1

In a similar fashion, Q3 is given by

! ! !
1 1 F3 F2 F4 F3
Q3 = = ,
1 0 F2 F1 F3 F2

and so on. The self-evident pattern can be seen to be

!
n Fn+1 Fn
Q = . (6.3)
Fn Fn−1
 WEEK II. IDENTITIES, SUMS AND RECTANGLES 18

Problems for Lecture 6

1. Prove (6.3) by mathematical induction.

2. Using the relation Qn Qm = Qn+m , prove the Fibonacci addition formula

Fn+m = Fn−1 Fm + Fn Fm+1 . (6.4)

3. Use the Fibonacci addition formula to prove the Fibonacci double angle formulas

F2n−1 = Fn2−1 + Fn2 , F2n = Fn ( Fn−1 + Fn+1 ) . (6.5)

4. Show that
F2n = Ln Fn .

Solutions to the Problems

Lecture 7 | Cassini’s identity
View this lecture on YouTube

Last lecture’s result for the Fibonacci Q-matrix is given by

!
n Fn+1 Fn
Q = , (7.1)
Fn Fn−1

with !
1 1
Q= . (7.2)
1 0

From the theory of matrices and determinants (see Appendix B), we know that

det AB = det A det B.

Repeated application of this result yields

det Qn = (det Q)n . (7.3)

Applying (7.3) to (7.1) and (7.2) results directly in Cassini’s identity (1680),

Fn+1 Fn−1 − Fn2 = (−1)n . (7.4)

Examples of this equality can be obtained from the first few numbers of the Fibonacci
sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . . We have

2 × 5 − 32 = 1,
3 × 8 − 52 = −1,
5 × 13 − 82 = 1,
2
8 × 21 − 13 = −1
13 × 34 − 212 = 1.

Cassini’s identity is the basis of an amusing dissection fallacy, called the Fibonacci
bamboozlement, discussed in the next lecture.

19
 WEEK II. IDENTITIES, SUMS AND RECTANGLES 20

Problems for Lecture 7

1. Prove Cassini’s identity by mathematical induction.

2. Using the Cassini’s identity (7.4) and the Fibonacci addition formula (6.4), prove Cata-
lan’s identity
Fn2 − Fn−r Fn+r = (−1)n−r Fr2 . (7.5)

Solutions to the Problems

Lecture 8 | The Fibonacci bamboozlement
View this lecture on YouTube

Cassini’s identity
Fn+1 Fn−1 − Fn2 = (−1)n

can be interpreted geometrically: Fn+1 Fn−1 is the area of a rectangle of side lengths Fn+1
and Fn−1 , and Fn2 is the area of a square of side length Fn . Cassini’s identity states that the
absolute difference in area between the rectangle and the square is only one unit of area.
As n becomes large, this one unit of area difference becomes small relative to the areas
of the square and the rectangle, and Cassini’s identity becomes the basis of an amusing
dissection fallacy, called the Fibonacci bamboozlement.
To perform the Fibonacci bamboozlement, one dissects a square with side length Fn in
such a way that by rearranging the pieces, one appears able to construct a rectangle with
side lengths Fn−1 and Fn+1 , with either one unit of area larger or smaller than the original
square.
We illustrate this bamboozlement in Fig. 8.1 using a square of area 8 × 8 = 64, and
a rectangle of area 5 × 13 = 65, corresponding to n = 6 in Cassini’s identity. We begin
by dissecting a square into two rectangles, the bottom rectangle of dimension 8-by-5 and
the top rectangle of dimension 8-by-3. Here, 5 and 3 are the two Fibonacci numbers
immediately preceeding 8.
The bottom 8-by-5 rectangle is then further dissected into two equal trapezoids. The
bases of the two trapezoids are the Fibonacci numbers 5 and 3, and the heights are 5. The
top rectangle is further dissected into two equal right triangles. The bases of the triangles
are the Fibonacci number 8 and the heights of the triangles are the Fibonacci number 3.
The dissected square is shown in Fig. 8.1a.
To construct a rectangle of dimension 5-by-13, one of the trapezoids fits into the bot-
tom of the rectangle and the other trapezoid fits into the top of the rectangle. The two
triangles then fill the remaining spaces. The resulting rectangle is shown in Fig. 8.1b, and
it superficially appears that the the square has been recombined to form a rectangle of a
larger area.
The honestly reconstructed rectangle, however, is shown in Fig. 8.2, where the missing
unit area is seen to be almost evenly distributed along the diagonal of the rectangle.
Why is the missing (or extra) unit area distributed along the diagonal of the rectangle?
In our example, the side slope of the trapezoids is given by F5 /F3 = 5/2 = 2.5 while the
slope of the triangle’s hypotenuse is given by F6 /F4 = 8/3 ≈ 2.67. This slight mismatch
in slopes results in a steady increase or decrease in distance between the trapezoid and
the triangle when they are aligned. Here, the gap between the trapezoid and the triangle
can be easily hidden by splitting the difference between the aligned pieces, as done in the
dishonestly constructed rectangle.

21
 WEEK II. IDENTITIES, SUMS AND RECTANGLES 22

(a) Square of dimension 8-by-8 and area 64. (b) Rectangle of dimension 13-by-5 and area 65.

Figure 8.1: The Fibonacci Bamboozlement.

Figure 8.2: The honest rectangle. The white space shows the missing unit area.
 WEEK II. IDENTITIES, SUMS AND RECTANGLES 23

Problems for Lecture 8

1. Cut an 8 × 8 chess board, or ruled paper, into two trapezoids and two triangles, and
fool your friends by using the pieces to reconstruct a 5 × 13 rectangle.
Practice Quiz | The Fibonacci bamboozlement
1. Select all that are true.

a) Fn+m = Fn−1 Fm + Fn Fm+1

b) Fn+m = Fm−1 Fn + Fm Fn+1

c) Fn+m = Fn−1 Fm + Fm−1 Fn

d) Fn+m = Fn+1 Fm + Fm+1 Fn

2. Select all that are true.

a) F2n−1 = Fn ( Fn−1 + Fn )

b) F2n−1 = Fn2−1 + Fn2

c) F2n = Fn ( Fn−1 + Fn )

d) F2n = Fn ( Fn−1 + Fn+1 )

3. What is the value of ( Fn+1 Fn−1 + Fn+2 Fn ) − ( Fn2 + Fn2+1 )?

a) 0

b) 2

c) Fn−2

d) Fn

Solutions to the Practice quiz

24
Lecture 9 | Sum of Fibonacci numbers
View this lecture on YouTube

In this lecture, I derive the summation identity

n
∑ Fi = Fn+2 − 1. (9.1)
i =1

For example, consider the first eight Fibonacci numbers, 1, 1, 2, 3, 5, 8, 13, 21. With n = 6 in
(9.1), we have
n
∑ Fi = 1 + 1 + 2 + 3 + 5 + 8 = 20,
i =1

and
Fn+2 − 1 = 21 − 1 = 20.

One can use mathematical induction to prove (9.1), but a direct derivation uses the
relation Fn = Fn+2 − Fn+1 . Constructing a list of identities, we have

Fn = Fn+2 − Fn+1
Fn−1 = Fn+1 − Fn
Fn−2 = Fn − Fn−1
.. ..
. .
F2 = F4 − F3
F1 = F3 − F2 .

Adding all the left hand sides yields the sum over the first n Fibonacci numbers, and
adding all the right-hand-sides results in the cancellation of all terms except the first and
the last. Using F2 = 1 results in (9.1).

25
 WEEK II. IDENTITIES, SUMS AND RECTANGLES 26

Problems for Lecture 9

1. Prove by mathematical induction that the sum over the first n Fibonacci numbers is
given by
n
∑ Fi = Fn+2 − 1. (9.2)
i =1

2. Prove by construction that the sum over the first n Lucas numbers is given by

n
∑ Li = Ln+2 − 3. (9.3)
i =1

3. Prove by construction that the sums over the first n odd or n even Fibonacci numbers
are given by
n n
∑ F2i−1 = F2n , ∑ F2i = F2n+1 − 1.
i =1 i =1

Solutions to the Problems

Lecture 10 | Sum of Fibonacci numbers squared
View this lecture on YouTube

In this lecture, I derive a combinatorial identity obtained by summing over the squares of
the Fibonacci numbers:
n
∑ Fi2 = Fn Fn+1 . (10.1)
i =1

For example, consider the first seven Fibonacci numbers, 1, 1, 2, 3, 5, 8, 13. With n = 6 in
(10.1), we have
12 + 12 + 22 + 32 + 52 + 82 = 8 × 13,

where by doing the arithmetic one finds that both sides are equal to 104.
To prove (10.1), we work with the right-hand side, using the Fibonacci recursion rela-
tion. We have

Fn Fn+1 = Fn ( Fn + Fn−1 )
= Fn2 + Fn−1 Fn
= Fn2 + Fn−1 ( Fn−1 + Fn−2 )
= Fn2 + Fn2−1 + Fn−2 Fn−1
= ...
= Fn2 + Fn2−1 + · · · + F22 + F1 F2 .

Because F2 = F1 , the identity (10.1) is proved.

We will revisit this combinatorial identity in a later lecture.

27
 WEEK II. IDENTITIES, SUMS AND RECTANGLES 28

Problems for Lecture 10

1. Prove (10.1) by mathematical induction

2. Prove by construction that the sum of the first n Lucas numbers squared is given by

n
∑ L2i = Ln Ln+1 − 2. (10.2)
i =1

Solutions to the Problems

Practice Quiz | Fibonacci sums
n
1. When deriving ∑ Fi = Fn+2 − 1, the number one comes from
i =1

a) F0

b) F1

c) F2

d) F3 − F2
n
2. To derive ∑ F2i−1 = F2n , one first writes F2n−1 = F2n − F2n−2 . Directly underneath, one
i =1
then writes

a) F2n−2 = F2n−3 + F2n−4

b) F2n−3 = F2n−2 − F2n−4

c) F2n−3 = F2n−2 + F2n−1

d) F2n−4 = F2n−2 − F2n−3

n
3. When deriving ∑ Fi2 = Fn Fn+1 , we need the equality
i =1

a) F1 F2 = F12

b) F1 F2 = F22

c) F2 + F4 = F32

d) F3 F5 − F2 = F42

Solutions to the Practice quiz

29
Lecture 11 | The golden rectangle
View this lecture on YouTube

A golden rectangle is a rectangle whose side lengths are in the golden ratio. In a classical
construction, first one draws a square. Second, one draws a line from the midpoint of one
side to a corner of the opposite side. Third, one draws an arc from the corner to an exten-
sion of the side with the midpoint. Fourth, one completes the rectangle. The procedure is
illustrated in Fig. 11.1.

√
1 5/2 1

1 1/2

(a) Construct a square. (b) Draw a line from midpoint to corner.

√ √
1/2 5/2 (1 + 5)/2

(c) Draw an arc using the internal line as radius. (d) Complete the golden rectangle.

Figure 11.1: Classical construction of the golden rectangle.

30
 WEEK II. IDENTITIES, SUMS AND RECTANGLES 31

Problems for Lecture 11

1. Use the online software GeoGebra to construct a golden rectangle. Or try it with a real
straightedge and a compass!
Lecture 12 | Spiraling squares
View this lecture on YouTube

1 φ

Figure 12.1: Two golden rectangles. The full rectangle and the rectangle next to the square
are both golden rectangles. Here, φ = Φ − 1 = 1/Φ.

To construct a golden rectangle of length L = Φ and width W = 1, a smaller rectangle

was attached to a unit square as illustrated in Fig. 12.1. The smaller rectangle has vertical
length L = 1 and horizontal width W = Φ − 1, but since Φ − 1 = 1/Φ, the smaller
rectangle satisfies L/W = Φ, and so it too is a golden rectangle.
This smaller golden rectangle can again be subdivided into a still smaller square and
golden rectangle, and this process can be continued ad infinitum. At each subdivision,
the length of the square is reduced by a factor of φ = 1/Φ.
The subdivisions can be done in either a clockwise or counterclockwise fashion. For
clockwise, the square is positioned first on the left, then top, then right, and then bottom
of the rectangle, and so on. Eventually, we obtain Fig. 12.2, where the side lengths of some
of the squares are written in their centers as powers of φ.
Notice that each golden rectangle in Fig. 12.2 is a reduced-scale copy of the whole.
Objects containing reduced-scale copies of themselves are called self-similar.

32
 WEEK II. IDENTITIES, SUMS AND RECTANGLES 33

φ
1 φ4

φ3
φ5
φ6

φ 2

Figure 12.2: Spiraling squares. The side lengths of the squares are the numbers in their
centers.
 WEEK II. IDENTITIES, SUMS AND RECTANGLES 34

Problems for Lecture 12

1. Prove that
∞
∑ φ2i = Φ.
i =0

A visual proof of this identity is given by Fig. 12.2, where the left-hand-side is the sum
of the areas of all the imbedded squares and the right-hand-side is the area of the big
rectangle.

Solutions to the Problems

 Week III

The Most Irrational Number

In this week’s lectures, we learn about the golden spiral and the Fibonacci spiral. Because of the
relationship between the Fibonacci numbers and the golden ratio, the Fibonacci spiral eventually
converges to the golden spiral. You will recognize the Fibonacci spiral because it is the icon of our
course. We next learn about continued fractions. To construct a continued fraction is to construct
a sequence of rational numbers that converges to a target irrational number. The golden ratio is
the irrational number whose continued fraction converges the slowest. We say that the golden ratio
is the irrational number that is the most difficult to approximate by a rational number, or that
the golden ratio is the most irrational of the irrational numbers. We then define the golden angle,
related to the golden ratio, and use it to model the growth of a sunflower head. Use of the golden
angle in the model allows a fine packing of the florets, and results in the unexpected appearance of
the Fibonacci numbers in the head of a sunflower.

35
Lecture 13 | The golden spiral
View this lecture on YouTube

The celebrated golden spiral is a special case of the more general logarithmic spiral whose
radius r is given by
r = aebθ , (13.1)

where θ is the usual polar angle, and a and b are constants. Jacob Bernoulli (1655-1705)
studied this spiral in depth and gave it the name spira mirabilis, or miraculous spiral,
asking that it be engraved on his tombstone with the enscription “Eadem mutata resurgo”,
roughly translated as “Although changed, I arise the same.” A spiral was engraved at the
bottom of his tombstone, but sadly it was not his beloved logarithmic spiral.
The golden spiral is a logarithmic spiral whose radius either increases or decreases by
a factor of the golden ratio Φ with each one-quarter turn, that is, when θ increases by
π/2. The golden spiral therefore satisfies the equation

r = aΦ2θ/π . (13.2)

In our figure of the spiraling squares within the golden rectangle, the dimension of
each succeeding square decreases by a factor of Φ, with four squares composing each full
turn of the spiral. It should then be possible to inscribe a golden spiral within our figure
of spiraling squares. We place the central point of the spiral at the accumulation point of
all the squares, and fit the parameter a so that the golden spiral passes through opposite
corners of the squares. The resulting beautiful golden spiral is shown in Fig. 13.1.

36
 WEEK III. THE MOST IRRATIONAL NUMBER 37

Figure 13.1: The golden spiral. The central point is where the squares accumulate.
 WEEK III. THE MOST IRRATIONAL NUMBER 38

Problems for Lecture 13

1. Prove that the accumulation point of all the spiraling squares (called the eye of God
by the author Clifford Pickover) is the intersection point of the diagonal lines of the two
largest golden rectangles, as illustrated below. Find the coordinates of this intersection
point, where the origin of the coordinate system is taken to be the lower left-hand corner
of the largest golden rectangle.

φ
1 φ4

φ
φ5
φ6

3 φ 2

Solutions to the Problems

Lecture 14 | An inner golden rectangle
View this lecture on YouTube

Figure 14.1: Spiral center. The intersection of the red and blue diagonal lines marks the
accumulation point of all the golden rectangles, and locates the center of the golden spiral.

Consider again the spiralling squares shown in Fig. 14.1. As shown in the problems, if the
diagonals of the two largest golden rectangles are drawn, their intersection point marks
the center of a golden spiral.
By symmetry, we should be able to mark four possible spiral centers. These four
centers are located in Fig. 14.2 as the intersection of the red and blue diagonals. If we then
draw the rectangle with vertices at the four spiral centers, we obtain yet another golden
√ √
rectangle, with horizontal length L = Φ/ 5 and vertical width W = 1/ 5.

39
 WEEK III. THE MOST IRRATIONAL NUMBER 40

√1
1 5

Φ
√
5

Figure 14.2: An inner golden rectangle. The four spiral centers in a golden rectangle are
indicated by the intersections of the red and blue diagonals. These four points form the
vertices of√
another golden rectangle, whose sides are reduced from that of the original by
the factor 5.
 WEEK III. THE MOST IRRATIONAL NUMBER 41

Problems for Lecture 14

1. Show that the inner golden rectangle with corners at the centers of the four possible
√
golden spirals is reduced in scale from the outer golden rectangle by the factor 5.

Solutions to the Problems

Lecture 15 | The Fibonacci spiral
View this lecture on YouTube

Consider again the sum of the Fibonacci numbers squared:

n
∑ Fi2 = Fn Fn+1 . (15.1)
i =1

This identity can be interpreted as an area formula. The left-hand-side is the total area of
squares with sides given by the first n Fibonacci numbers; the right-hand-side is the area
of a rectangle with sides Fn and Fn+1 .
For example, consider n = 2. The identity (15.1) states that the area of two unit squares
is equal to the area of a rectangle constructed by placing the two unit squares side-by-side,
as illustrated in Fig. 15.1a.
For n = 3, we can position another square of side length two directly underneath the
first two unit squares. Now, the sum of the areas of the three squares is equal to the
area of a 2-by-3 rectangle, as illustrated in Fig. 15.1b. The identity (15.1) for larger n is
made self-evident by continuing to tile the plane with squares of side lengths given by
consecutive Fibonacci numbers.
The most beautiful tiling occurs if we keep adding squares in a clockwise, or coun-
terclockwise, fashion. Fig. 15.2 shows the iconic result obtained from squares using the
first six Fibonacci numbers, where quarter circles are drawn within each square thereby
reproducing the Fibonacci spiral.
Consider the close similarity between the golden spiral in Fig. 13.1 and the Fibonacci
spiral in Fig. 15.2. Both figures contain spiralling squares, but in Fig. 15.2 the squares spiral
outward, and in Fig. 13.1 the squares spiral inward. Because the ratio of two consecutive
Fibonacci numbers approaches the golden ratio, the Fibonacci spiral, as it spirals out, will
eventually converge to the golden spiral.

42
 WEEK III. THE MOST IRRATIONAL NUMBER 43

1 1

1 1
2

(a) n = 2: 12 + 12 = 1 × 2. (b) n = 3: 12 + 12 + 22 = 2 × 3.

Figure 15.1: Illustrating the sum of the Fibonacci numbers squared. The center numbers
represent the side lengths of the squares.

5
8
11
2 3

Figure 15.2: The sum of Fibonacci numbers squared for n = 6. The Fibonacci spiral is
drawn.
Practice Quiz | Spirals
1. A golden spiral is a logarithmic spiral whose radius increases or decreases by a factor
of Φ with each turn.

a) full

b) one-half

c) one-quarter

d) one-eighth

2. If counterclockwise spiraling squares are drawn with the first square on the right side
of the largest golden rectangle, then the origin of the golden spiral occurs in the
of the largest golden rectangle.

a) top left

b) bottom left

c) top right

d) bottom right

3. A 5 × 8 rectangle can be divided into squares with side lengths given by the first
Fibonacci numbers.

a) 5

b) 6

c) 7

d) 8

Solutions to the Practice quiz

44
Lecture 16 | Fibonacci numbers in nature
View this lecture on YouTube

Figure 16.1: The flowering head of a sunflower.

Consider the photo of a sunflower shown in Fig. 16.1, and notice the apparent spirals
in the florets radiating out from the center to the edge. These spirals appear to rotate
both clockwise and counterclockwise. By counting them, one finds 21 clockwise spirals
and 34 counterclockwise spirals. Surprisingly, the numbers 21 and 34 are consecutive
Fibonacci numbers. In the following lectures, we will try to explain why this might not
be a coincidence.

45
Lecture 17 | Continued fractions
View this lecture on YouTube

The appearance of consecutive Fibonacci numbers in some sunflower heads can be re-
lated to a very special property of the golden ratio. To reveal that property requires first
a short lesson on continued fractions.
Recall that a rational number is any number that can be expressed as the quotient of
two integers, and an irrational number is any number that is not rational. Rational num-
bers have finite continued fractions; irrational numbers have infinite continued fractions.
A finite continued fraction represents a rational number x as

1
x = a0 + , (17.1)
1
a1 +
1
a2 +
.. 1
.+
an

where a1 , a2 , . . . , an are positive integers and a0 is any integer. The convenient shorthand
form of (17.1) is
x = [ a0 ; a1 , a2 , . . . , a n ].

If x is irrational, then n → ∞.
Now for some examples. To construct the continued fraction of the rational number
x = 3/5, we can write

1 1
3/5 = =
5/3 1 + 2/3
1 1
= = ,
1 1
1+ 1+
3/2 1 + 1/2

which is of the form (17.1), so that 3/5 = [0; 1, 1, 2].

To construct the continued fraction of an irrational number, say π, we can write

π = 3 + 0.14159 . . .
1
= 3+
7.06251 . . .
1
= 3+ ,
1
7+
15.99659 . . .

and so on, yielding the beginning sequence π = [3; 7, 15, . . . ]. The historically important
first-order approximation is given by π ≈ [3; 7] = 22/7 = 3.142857 . . . , which was already
known by Archimedes in ancient times.

46
 WEEK III. THE MOST IRRATIONAL NUMBER 47

Finally, to determine the continued fraction for the golden ratio Φ, we can use a trick
and write
1
Φ = 1+ ,
Φ
which is a recursive definition that can be continued as

1
Φ = 1+ ,
1
1+
Φ

and so on, yielding the remarkably simple form

Φ = [1; 1̄],

where the bar indicates an infinite repetition.

Because the trailing ai ’s are all equal to one, the continued fraction for the golden ratio
(and other related numbers with trailing ones) converges especially slowly. Furthermore,
the successive rational approximations to the golden ratio are just the ratios of consecutive
Fibonacci numbers, that is, 1/1, 2/1, 3/2, 5/3, 8/5, and so on. Because of the very slow
convergence of this sequence, we say that the golden ratio is the most difficult number to
approximate by a rational number. More poetically, the golden ratio has been called the
most irrational of the irrational numbers.
 WEEK III. THE MOST IRRATIONAL NUMBER 48

Problems for Lecture 17

√ √ √
1. Starting with 2 = 1 + ( 2 − 1), find a recursive definition for 2 and use it to derive
its continued fraction.
√
2. Use the same trick of Problem 1 to find the continued fraction for 3.

3. Show that e = [2; 1, 2, 1, 1, 4, . . . ]

4. Define xn to be the nth rational approximation to x obtained from its continued fraction,
where, for example, x0 = [ a0 ; ], x1 = [ a0 ; a1 ], and x2 = [ a0 ; a1 , a2 ]. Using Φ = [1; 1̄], verify
that Φ0 , Φ1 , Φ2 , and Φ3 are just the ratios of consecutive Fibonacci numbers.

5. Prove by induction that

Fn+2
Φn = . (17.2)
Fn+1

Solutions to the Problems

Lecture 18 | The golden angle
View this lecture on YouTube

Figure 18.1: The golden angle g is determined from requiring x/y = Φ.

Our model of the sunflower will make use of the golden angle. The golden angle is
defined as the acute angle g that divides the circumference of a circle into two arcs with
lengths in the golden ratio (see Fig. 18.1).
The golden ratio Φ and the golden ratio conjugate φ satisfy

x y
Φ= , φ= ,
y x

with Φ = 1 + φ. We can determine the golden angle by writing

g y φ φ
= = = = φ2 ;
2π x+y 1+φ Φ

and since φ2 = 1 − φ, we obtain

g = 2π (1 − φ).

Expressed in degrees, this is g ≈ 137.5◦ .

To determine the continued fraction for g/2π, we write

g y 1
= =
2π x+y 1+Φ
1
= ,
1
1+1+
1
1+
1+...

which yields g/2π = [0; 2, 1]. The trailing ones in the continued fraction ensure that g/2π
is difficult to represent as a rational number. Indeed, the successive rational approxima-
tions to g/2π can be computed to be 1/2, 1/3, 2/5, 3/8, 5/13, and so on, which is just
the sequence given by the ratio Fn /Fn+2 .

49
 WEEK III. THE MOST IRRATIONAL NUMBER 50

Problems for Lecture 18

1. Define xn to be the nth rational approximation to x obtained from its continued fraction,
where, for example, x0 = [ a0 ; ], x1 = [ a0 ; a1 ], and x2 = [ a0 ; a1 , a2 ]. Using g/2π = [0; 2, 1̄],
determine g0 /2π, g1 /2π, g2 /2π, and g3 /2π.

2. Prove by induction that

gn Fn
= . (18.1)
2π Fn+2

Solutions to the Problems

Lecture 19 | A simple model for the growth
of a sunflower
View this lecture on YouTube

We can now understand a simple model for the growth of a sunflower head, and why
the Fibonacci numbers might appear. Suppose that during development, florets are cre-
ated close to the center of the head and subsequently move radially outward with constant
speed during growth. Also suppose that as each new floret is created at the center, it is
rotated through a constant angle before moving radially. Our goal is to derive an an-
gle of rotation that in some sense is optimum: the resulting sunflower head consists of
well-spaced florets.
Let us denote the rotation angle by 2πα. We first consider the possibility that α is a
rational number, say n/m, where n and m are positive integers with no common factors,
and n < m. Since after m rotations florets will return to the radial line on which they
started, the resulting sunflower head consists of florets lying along m straight lines. A
simulation of such a sunflower head for α = 1/7 is shown in Fig. 19.1a, where one
observes seven straight lines. Evidently, rational values for α do not result in well-spaced
florets.
What about irrational values? For α irrational, no number of rotations will return
the florets to their first radial line. Nevertheless, the resulting sunflower head may still
not have well-spaced florets. For example, if α = π − 3, then the resulting sunflower head
looks like Fig. 19.1b. There, one can see seven counterclockwise spirals. Recall that a good
rational approximation to π is 22/7, which is slightly larger than π. On every seventh
counterclockwise rotation, new florets fall just short of the radial line of florets created
seven rotations ago.
The irrational numbers that are most likely to construct a sunflower head with well-
spaced florets are those that can not be well-approximated by rational numbers. Here,
we choose the golden angle, taking α = 1 − φ. The rational approximations to 1 − φ are
given by Fn /Fn+2 , so that the number of spirals observed will correspond to the Fibonacci
numbers.
Two simulations of the sunflower head with α = 1 − φ are shown in Fig. 19.2. These
simulations differ only by the choice of radial velocity, v0 . In Fig. 19.2a, one counts 13
clockwise spirals and 21 counterclockwise spirals; in Fig. 19.2b, one counts 21 counter
clockwise spirals and 34 clockwise spirals, the same as the sunflower head shown in Fig.
16.1.

51
 WEEK III. THE MOST IRRATIONAL NUMBER 52

(a) (b)
Figure 19.1: Simulation of the sunflower model for (a) α = 1/7; (b) α = π − 3 and
counterclockwise rotation.

(a) (b)
Figure 19.2: Simulation of the sunflower model for α = 1 − φ and clockwise rotation.
(a) v0 = 1/2; (b) v0 = 1/4.
Practice Quiz | Fibonacci numbers in nature
1. The first two rational approximations to π from its continued fraction are 3 and 22/7.
What is the next rational approximation?

a) 311/99

b) 333/106

c) 349/111

d) 355/113
√
2. The first three rational approximations to 2 from its continued fraction are 1, 3/2,
and 7/5. What is the next rational approximation?

a) 13/9

b) 16/11

c) 17/12

d) 22/15

3. The golden angle is given by g = 2π (1 − φ). The nth rational approximation to g/2π
from its continued fraction is given by

a) Fn+2 /Fn

b) Fn+1 /Fn

c) Fn /Fn+1

d) Fn /Fn+2

Solutions to the Practice quiz

53
Appendices

54
Appendix A | Mathematical induction
View this lecture on YouTube

Mathematical induction is a method of proof used to establish a statement about the

natural numbers. The standard example used to illustrate this form of proof is

n ( n + 1)
1+2+3+···+n = , (A.1)
2

valid for n a positive integer. We will suppose that this formula is known, and that our
task is to prove it using mathematical induction.
The first step in the proof is to establish what is called the base case. Here, we prove
that the given statement is true for the smallest integer for which it is claimed to be valid:
Base case: For n = 1, the left-hand side of (A.1) equals one, and the right-hand side of
(A.1) equals (1 × 2)/2 = 1, so that (A.1) is true for n = 1.
The next step is called the induction step. Here one assumes that the statement is true for
n = k, and then proves it is true for n = k + 1. Once the induction step is proved, then the
statement is declared true for all integers greater than or equal to the base case.
Why is the proof then complete? Well, if the statement is true for n = 1 as shown in
the base case, then the induction step shows it is also true for n = 2. And if the statement
is true for n = 2, then the induction step shows it is true for n = 3. Continuing ad infinitum
leads to the conclusion that the statement is true for all the natural numbers.
So let us proceed to prove the induction step. The method of proof usually writes
the left-hand side of the statement when n = k + 1, and then makes use of the induction
hypothesis—the assumption that the statement is true for n = k—and some additional
information to obtain the right-hand side of the statement.

Induction step: Now, suppose (A.1) is true for n = k. Then

k ( k + 1)
1 + 2 + 3 + · · · + k + ( k + 1) = + ( k + 1) (from induction hypothesis)
2
k ( k + 1) + 2( k + 1)
= (from combining fractions)
2
(k + 1)(k + 2)
= , (from factoring)
2

and since (k + 2) = (k + 1) + 1, we have shown that A.1 is true for n = k + 1. By the

principle of induction, A.1 is therefore true for all natural numbers.
Because statements about the Fibonacci numbers Fn are typically statements true for
n = 1, 2, 3, . . . , proofs can often make use of mathematical induction. Oftentimes, the
induction step requires the assumption that the statement is true for both n = k − 1 and
n = k. When this happens, the base case must verify the truth of the statement for both
n = 1 and 2. Then if the statement is true for n = 1 and 2, it must be true for n = 3. And
if the statement is true for n = 2 and 3, it must be true for n = 4. Continuing ad infinitum
leads to the conclusion that the statement is true for all natural numbers.

55
Appendix B | Matrix algebra
For those readers who have never studied matrices or linear algebra, it will be helpful
to understand a few basic concepts. A matrix with n rows and m columns is called an
n-by-m matrix. Here, we need only consider the simple case of two-by-two matrices.
A two-by-two matrix A, with two rows and two columns, can be written as
!
a b
A= .
c d

The first row has elements a and b, the second row has elements c and d. The first column
has elements a and c; the second column has elements b and d.

B.1 Addition and Multiplication

View this lecture on YouTube

Matrices can be added and multiplied. Matrices can be added if they have the same
dimension, and addition proceeds element by element, following
! ! !
a b e f a+e b+ f
+ = .
c d g h c+g d+h

Matrices can be multiplied if the number of columns of the left matrix equals the number
of rows of the right matrix. A particular element in the resulting product matrix, say in
row k and column l, is obtained by multiplying and summing the elements in row k of the
left matrix with the elements in column l of the right matrix. For example, a two-by-two
matrix can multiply a two-by-one column vector as follows
! ! !
a b x ax + by
= .
c d y cx + dy

The first row of the left matrix is multiplied against and summed with the first (and only)
column of the right matrix to obtain the element in the first row and first column of
the product matrix, and so on for the element in the second row and first column. The
product of two two-by-two matrices is given by
! ! !
a b e f ae + bg a f + bh
= .
c d g h ce + dg c f + dh

56
 APPENDIX B. MATRIX ALGEBRA 57

B.2 Determinants

View this lecture on YouTube

Consider the system of equations given by

ax + by = 0,
(B.1)
cx + dy = 0,

which can be written in matrix form as

! ! !
a b x 0
= .
c d y 0

When does there exist a nontrivial (not identically zero) solution for x and y?

To answer this question, we solve directly the system of equations given by (B.1). Mul-
tiplying the first equation by d and the second by b, and subtracting the second equation
from the first, results in
( ad − bc) x = 0.

Similarly, multiplying the first equation by c and the second by a, and subtracting the first
equation from the second, results in

( ad − bc)y = 0.

Therefore, a nontrivial solution of (B.1) exists only if ad − bc = 0. The quantity ad − bc

defines the determinant of the two-by-two matrix, that is
!
a b
det = ad − bc. (B.2)
c d

The determinants of larger square matrices can be found similarly. Just for fun, I can show
you the determinant of a three-by-three matrix:
 
a b c
det  d e f  = a(ei − f h) − b(di − f g) + c(dh − eg).
 

g h i

We will need the following result to prove Cassini’s identity:

det AB = det A det B.

Although this is a general result for all n-by-n square matrices, we need only the result
for the 2-by-2 case, which can be easily proved by an explicit calculation.
 APPENDIX B. MATRIX ALGEBRA 58

Let ! !
a b e f
A= , B= .
c d g h

Then !
ae + bg a f + bh
AB = ,
ce + dg c f + dh

and

det AB = ( ae + bg)(c f + dh) − ( a f + bh)(ce + dg)

= ( ace f + adeh + bc f g + bdgh) − ( ace f + ad f g + bceh + bdgh)
= ( adeh + bc f g) − ( ad f g + bceh)
= ad(eh − f g) − bc(eh − f g)
= ( ad − bc)(eh − f g)
= det A det B.
Appendix C | Problem and practice quiz solutions

Solutions to the Problems for Lecture 1

1. We calculate the first few terms.

F0 = F2 − F1 = 0,
F−1 = F1 − F0 = 1,
F−2 = F0 − F−1 = −1,
F−3 = F−1 − F−2 = 2,
F−4 = F−2 − F−3 = −3,
F−5 = F−3 − F−4 = 5,
F−6 = F−4 − F−5 = −8.

The correct relation appears to be

F−n = (−1)n+1 Fn . (C.1)

We now prove (C.1) by mathematical induction.

Base case: Our calculation above already shows that (C.1) is true for n = 1 and n = 2, that
is, F−1 = F1 and F−2 = − F2 .

Induction step: Suppose that (C.1) is true for positive integers n = k − 1 and n = k. Then
we have

F−(k+1) = F−(k−1) − F−k (from definition)

= (−1)k Fk−1 − (−1)k+1 Fk (from induction hypothesis)
k +2
= (−1) ( Fk−1 + Fk )
= (−1)k+2 Fk+1 , (from recursion relation)

so that (C.1) is true for n = k + 1. By the principle of induction, (C.1) is therefore true for
all positive integers.

2. 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322

3. We now prove (1.2) by mathematical induction.

Base case: To prove that (1.2) is true for n = 1, we write F1 p + F2 q = p + q = f 3 . To prove

that (1.2) is true for n = 2, we write F2 p + F3 q = p + 2q = f 3 + f 2 = f 4 .

Induction step: Suppose that (1.2) is true for positive integers n = k − 1 and n = k. Then

59
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 60

we have

f k +3 = f k +2 + f k +1
= ( Fk p + Fk+1 q) + ( Fk−1 p + Fk q) (from induction hypothesis)
= ( Fk + Fk−1 ) p + ( Fk+1 + Fk ) q
= Fk+1 p + Fk+2 q, (from recursion relation)

so that (1.2) is true for n = k + 1. By the principle of induction, (1.2) is therefore true for
all positive integers.

4. To generate the Lucas sequence, we take p = 1 and q = 3. Therefore, we have

Ln = Fn−2 + 3Fn−1 (from (1.2))

= 2Fn−1 + ( Fn−1 + Fn−2 )
= Fn−1 + ( Fn−1 + Fn ) (from recursion relation)
= Fn−1 + Fn+1 . (from recursion relation)

5. We have

1 1
(L + Ln+1 ) = (( Fn−2 + Fn ) + ( Fn + Fn+2 )) (from (1.3))
5 n −1 5
1
= ( Fn−2 + 2Fn + Fn + Fn+1 ) (from recursion relation)
5
1
= ( Fn−2 + 3Fn + Fn + Fn−1 ) (from recursion relation)
5
= Fn . (from recursion relation)

6. We write

f ( x ) = F1 x + F2 x2 + F3 x3 + F4 x4 + . . .
x f (x) = F1 x2 + F2 x3 + F3 x4 + . . .
x2 f ( x ) = F1 x3 + F2 x4 + . . . .

We then subtract the second and third equation from the first, and use F1 = F2 = 1 and
Fn+1 − Fn − Fn−1 = 0 to obtain

(1 − x − x2 ) f ( x ) = x,

resulting in
x
f (x) = .
1 − x − x2
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 61

Solutions to the Problems for Lecture 2

1. Consider the set of different possible strings. This set may be divided into two nonover-
lapping subsets: those strings that start with one and those strings for which one and two
are interchanged. For the former, the remaining n − 1 numbers can form an−1 different
strings. For the latter, the remaining n − 2 numbers may can form an−2 different strings.
The total number of different strings is therefore given by the Fibonacci recursion relation

a n = a n −1 + a n −2 .

Together with a1 = 1 = F2 and a2 = 2 = F3 , we obtain an = Fn+1 .

2. Again consider the set of different possible strings. This set may be divided into two
nonoverlapping subsets: those strings for which the one and n are not interchanged, and
those strings for which they are interchanged. For the former, the number of different
strings is given by an = Fn+1 . For the latter, the number of different strings is given by
an−2 = Fn−1 . We therefore have

bn = Fn+1 + Fn−1 .

From (1.3), the relation satisfied by bn is the same as that satisfied by the nth Lucas number,
so that bn = Ln .

Solutions to the Practice quiz: The Fibonacci numbers

1. c. See also Lecture 1. The relevant table for the rabbit pair population is

month J F M A M J J A S O N D J
juvenile 1 0 1 1 2 3 5 8 13 21 34 55 89
adult 0 1 1 2 3 5 8 13 21 34 55 89 144
total 1 1 2 3 5 8 13 21 34 55 89 144 233

The number of adult rabbit pairs in the fifth month is 3.

2. c. See also Lecture 1, Problem 1. The Fibonacci numbers can be extended to negative
indices using the recursion relation. The result is F−n = (−1)n+1 Fn . When n = 5, we have
F−5 = F5 = 5.

3. c. See also Lecture 1, Problem 4. If we line up the Fibonacci numbers and the Lucas
numbers properly, we have

Fibonacci 0 1 1 2 3 5 8 13
Lucas 1 3 4 7 11 18
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 62

and it can be observed (without proof) that Ln = Fn−1 + Fn+1 . We can also use the
Fibonacci recursion relation to lower the index of Fn+1 (and Fn ). We have

Fn+1 = Fn + Fn−1 = ( Fn−1 + Fn−2 ) + Fn−1 = 2Fn−1 + Fn−2 .

Therefore,
Ln = Fn−1 + Fn+1 = 3Fn−1 + Fn−2 .

Both A and B are true.

Solutions to the Problems for Lecture 3

1.

(a)
√
5+1
Φ−1 = −1
√ 2
5−1
=
2
= φ,

(b)
√
1 2 1− 5
= √ × √
Φ 1+ 5 1− 5
 √ 
2 1− 5
=
−4
√
5−1
=
2
= φ.

(c)

√ !2
2 5+1
Φ =
2
√
5+2 5+1
=
√ 4
5+3
=
2
= Φ + 1.
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 63

(d)

√ !2
2 5−1
φ =
2
√
5−2 5+1
=
√ 4
− 5+3
=
2
= −φ + 1.

2. We multiply
1
= Φ−1
Φ
by Φ and rearrange to obtain
Φ2 = Φ + 1.

Multiplying both sides by Φn−1 yields the desired result:

Φ n +1 = Φ n + Φ n −1 .

3. We substitute φ = 1/Φ into

1
= Φ−1
Φ
to obtain
1
φ= − 1.
φ
Multiplying both sides by φn and rearranging terms yields the desired result:

φ n −1 = φ n + φ n +1 .

Solutions to the Problems for Lecture 4

1. Write
Fk+n F F F
= k + n × k + n −1 × · · · × k +1 .
Fk Fk+n−1 Fk+n−2 Fk
Then taking limk→∞ , and using
Fj
lim = Φ,
j→∞ Fj−1
one obtains directly
Fk+n
lim = Φn .
k→∞ Fk
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 64

2. We prove (4.2) by mathematical induction.

Base case: For n = 1, the relation (4.2) becomes Φ = Φ, which is true.

Induction step: Suppose that (4.2) is true for positive integer n = k. Then we have

Φk+1 = ΦΦk
= Φ ( Fk Φ + Fk−1 ) (from induction hypothesis)
2
= Fk Φ + Fk−1 Φ
= Fk (Φ + 1) + Fk−1 Φ (from Φ2 = Φ + 1)
= ( Fk + Fk−1 ) Φ + Fk
= Fk+1 Φ + Fk (from recursion relation)

so that (4.2) is true for n = k + 1. By the principle of induction, (4.2) is therefore true for
all positive integers.

3. We prove (4.3) by mathematical induction.

Base case: For n = 1, the relation (4.3) becomes −φ = −φ, which is true.
Induction step: Suppose that (4.3) is true for positive integer n = k. Then we have

(−φ)k+1 = −φ(−φ)k
= −φ (− Fk φ + Fk−1 ) (from induction hypothesis)
2
= Fk φ − Fk−1 φ
= Fk (−φ + 1) − Fk−1 φ (from φ2 = −φ + 1)
= − ( Fk + Fk−1 ) φ + Fk
= − Fk+1 φ + Fk , (from recursion relation)

so that (4.3) is true for n = k + 1. By the principle of induction, (4.3) is therefore true for
all positive integers.

Solutions to the Problems for Lecture 5

1. We prove 5.6 by mathematical induction.

√
Base case: When n = 1, the left side of (5.6) is F1 = 1 and the right side is (Φ + φ)/ 5 = 1,
so (5.6) is true for n = 1. When n = 2, the left side of (5.6) is F2 = 1 and the right side is
√
(Φ2 − φ2 )/ 5. We have
√ √
( Φ2 − φ2 ) ( 5 + 1)2 − ( 5 − 1)2
√ = √
5 4 5
√
4 5
= √
4 5
=1
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 65

so (5.6) is also true for n = 2.

Induction step: We will need to make use of the identities

Φ n +1 = Φ n −1 + Φ n , (C.2)
n −1 n n +1
φ = φ +φ . (C.3)

Now, suppose (5.6) is true for n = k − 1 and n = k. Then

Φk+1 − (−φ)k+1 (Φk−1 + Φk ) − (−1)k+1 (φk−1 − φk )

√ = √ (from (C.2) and (C.3))
5 5
(Φ k − 1 k −
− (−φ) ) + (Φk ) − (−φ)k
1
= √ (from reorganizing terms)
5
= Fk−1 + Fk (from induction hypothesis)
= Fk+1 , (from recursion relation)

so (5.6) is true for n = k + 1. By the principle of induction, (5.6) is therefore true for all
positive integers.

2.

Fn+1 Φn+1 − (−φ)n+1

lim = lim
n→∞ Fn n→∞ Φn − (−φ)n
Φ + (−1)n φ(φ/Φ)n
= lim . (divide numerator and denominator by Φn )
n→∞ 1 + (−1)n+1 ( φ/Φ )n

And since
lim (φ/Φ)n = 0,
n→∞

we obtain
lim Fn+1 /Fn = Φ.
n→∞

3. Subtract (5.8) from (5.7) to obtain

Fn (Φ + φ) = Φn − (−φ)n .
√
With Φ + φ = 5, we obtain Binet’s formula

Φn − (−φ)n
Fn = √ .
5

4. To derive Binet’s formula, we will Taylor series expand the function f ( x ) = x/(1 − x −
x2 ) and equate the coefficients of the resulting power series to the Fibonacci numbers.
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 66

The roots of the quadratic equation 1 − x − x2 = 0 are given by φ and −Φ so we can

write
x x
= .
1 − x − x2 (φ − x )(Φ + x )
A partial-fraction expansion results in

Φ
 
x 1 φ
= √ −
(φ − x )(Φ + x ) 5 φ−x Φ+x
 
1 1 1
= √ − ,
5 1 − Φx 1 + φx

where the last step uses φΦ = 1. We now use the Taylor-series expansions

1
= 1 + Φx + Φ2 x2 + Φ3 x3 + . . . ,
1 − Φx
1
= 1 + (−φ) x + (−φ)2 x2 + (−φ)3 x3 + . . . .
1 − (−φ) x

Subtracting the second expansion from the first results in

 
1 1
− = (Φ − (−φ)) x + (Φ2 − (−φ)2 ) x2 + (Φ3 − (−φ)3 ) x3 + . . . .
1 − Φx 1 + φx

Therefore,

Φ − (−φ) Φ2 − (−φ)2 Φ3 − (−φ)3

     
x 2
= √ x+ √ x + √ x3 + . . . ,
1 − x − x2 5 5 5

and equating the coefficients of this Taylor-series expansion with the coefficients of the
generating function for the Fibonacci sequence results in Binet’s formula

Φn − (−φ)n
Fn = √ .
5

5. The derivation follows the method we used to obtain Binet’s formula, but here the
initial values differ. We can use L0 = L2 − L1 = 2, and L1 = 1. The general solution to the
Fibonacci recursion relation is given by

Ln = c1 Φn + c2 (−φ)n .

Application of the two initial values that yields the Lucas sequence results in the system
of equations given by

c1 + c2 = 2,
c1 Φ − c2 φ = 1.
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 67

Multiplying the first equation by φ and adding it to the second equation results in

c1 (Φ + φ) = 2φ + 1.
√
Now 2φ + 1 = Φ + φ = 5. Therefore c1 = 1 and c2 = 1. Our solution is therefore

Ln = Φn + (−φ)n .

6. Binet’s formula and the analogous formula for the Lucas numbers are given by

Φn − (−φ)n
Fn = √ , Ln = Φn + (−φ)n .
5
√
Add the equation for Ln to the equation for Fn multiplied by 5, and divide by two to
obtain √
n Ln + 5Fn
Φ = .
2

Solutions to the Practice quiz: The golden ratio

1. a, b, d. See also Lecture 3, Problem 1. The golden ratio, Φ, and the negative of the
golden ratio conjugate, −φ, are the solutions of the quadratic equation x2 − x − 1 = 0.
Therefore, Φ2 = 1 + Φ and φ2 = 1 − φ. Also,
√ √
( 5 − 1)( 5 + 1) 5−1
φΦ = = = 1,
2×2 4

so that φ = 1/Φ and Φ = 1/φ. Notice too, that

√
Φ+φ = 5, Φ − φ = 1,

the latter yielding the relationships Φ = 1 + φ and φ = Φ − 1.

2. a. See also Lecture 5, Problem 5. The Lucas sequence is 1, 3, 4, 7, 11, . . . . To find an

analytical formula, we can solve Ln+1 = Ln + Ln−1 with initial values L0 = 2 and L1 = 1.
The general solution to the difference equation is

Ln = c1 Φn + c2 (−φ)n ,

and applying the values of L0 and L1 results in

c1 + c2 = 2, c1 Φ − c2 φ = 1.

Multiplying the first equation by φ and adding to the second equation gives (Φ + φ)c1 =
1 + 2φ. Since 1 + 2φ = (1 + φ) + φ = Φ + φ, we have c1 = 1. The first equation also gives
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 68

c2 = 1 and we have the simple formula

Ln = Φn + (−φ)n .

3. a, d. See also Lecture 4, Problems 2 and 3. The golden ratio and the negative of the
golden ratio conjugate, Φ and −φ, are solutions of the quadratic equation x2 − x − 1 = 0.
Therefore, Φ2 = Φ + 1 and (−φ)2 = (−φ) + 1. We can build powers of Φ and (−φ) as
follows:

Φ2 = Φ + 1 = F2 Φ + F1 ,
Φ3 = Φ2 + Φ = 2Φ + 1 = F3 Φ + F2 ,
Φ4 = 2Φ2 + Φ = 3Φ + 2 = F4 Φ + F3 ,
Φ5 = 3Φ2 + 2Φ = 5Φ + 3 = F5 Φ + F4 ,
... = ...,
Φn = Fn Φ + Fn−1 .

(−φ)2 = (−φ) + 1 = − F2 φ + F1 ,
(−φ)3 = (−φ)2 + (−φ) = 2(−φ) + 1 = − F3 φ + F2 ,
(−φ)4 = 2(−φ)2 + (−φ) = 3(−φ) + 2 = − F4 φ + F3 ,
(−φ)5 = 3(−φ)2 + 2(−φ) = 5(−φ) + 3 = − F5 φ + F4 ,
... = ...,
(−φ)n = − Fn φ + Fn−1 .

Solutions to the Problems for Lecture 6

1. We prove (6.3) by mathematical induction.

Base case: For n = 1, we obtain from (6.3)

!
1 1
Q= ,
1 0

which is just the definition.

 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 69

Induction step: Suppose that (6.3) is true for n = k. Then we have

Qk+1 = QQk
! !
1 1 Fk+1 Fk
= (from induction hypothesis)
1 0 Fk Fk−1
!
Fk+1 + Fk Fk + Fk−1
=
Fk+1 Fk
!
Fk+2 Fk+1
= , (from recursion relation)
Fk+1 Fk

so that (6.3) is true for n = k + 1. By the principle of induction, (6.3) is therefore true for
all positive integers.

2. We will use the formula !

n Fn+1 Fn
Q = .
Fn Fn−1

The relation Qn Qm = Qn+m is written as

! ! !
Fn+1 Fn Fm+1 Fm Fn+m+1 Fn+m
= .
Fn Fn−1 Fm Fm−1 Fn+m Fn+m−1

Equating the (2, 1) elements of the resulting matrices yields (6.4).

3. The first result can be obtained by taking m = n − 1 in (6.4); the second result can be
obtained by taking m = n.

4. Using Ln = Fn−1 + Fn+1 in the second formula of (6.5) yields the desired result.

Solutions to the Problems for Lecture 7

1. We prove (7.4) by mathematical induction.

Base case: When n = 1 the left side of (7.4) is F2 F0 − F12 = −1 and the right side is
(−1)1 = −1, so (7.4) is true for n = 1.
Induction step: Suppose (7.4) is true for n = k. Then

Fk+2 Fk − Fk2+1 = ( Fk + Fk+1 ) Fk − Fk2+1 (from recursion relation)

= Fk2 + Fk+1 ( Fk − Fk+1 )
= Fk2 − Fk+1 Fk−1 (from recursion relation)
= −(−1)k (from induction hypothesis)
k +1
= (−1) ,
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 70

so (7.4) is true for n = k + 1. By the principle of induction, (7.4) is therefore true for all
positive integers.

2. We first rewrite (7.5) using a simple substitution. Let x = n − r and y = r. Then

n = x + y and (7.5) becomes

Fx2+y − Fx Fx+2y = (−1) x Fy2 . (C.4)

We write

2
Fx2+y − Fx Fx+2y = Fx−1 Fy + Fx Fy+1


− Fx−1 F2y + Fx F2y+1 Fx (from (6.4))
= Fx2−1 Fy2 + 2Fx−1 Fx Fy Fy+1 + Fx2 Fy2+1
 
− Fx−1 Fx Fy−1 Fy + Fy Fy+1 − Fx2 Fy2 + Fy2+1


(from (6.4))
 
= Fx−1 Fx Fy Fy+1 − Fy−1 + Fy2 Fx2−1 − Fx2


 
= Fy2 Fx−1 ( Fx−1 + Fx ) − Fx2 (from recursion relation)
 
= Fy2 Fx−1 Fx+1 − Fx2 (from recursion relation)

= (−1) x Fy2 , (from (7.4))

which proves (C.4), and hence (7.5).

Solutions to the Practice quiz: The Fibonacci bamboozlement

1. a, b. See also Lecture 6, Problem 2 We used the relationship Qn Qm = Qn+m to prove

the Fibonacci addition formula Fn+m = Fn−1 Fm + Fn Fm+1 . Since the left-hand side of the
equation is symmetric in n and m, we can switch these two indices to obtain an equivalent
relationship Fn+m = Fm−1 Fn + Fm Fn+1 . The other two relationships can be shown false by
substituting in n = m = 1.

2. b, d. See also Lecture 6, Problem 3 and 4 The Fibonacci addition formula can be
used to prove the Fibonacci double angle formulas given by F2n−1 = Fn2−1 + Fn2 and F2n =
Fn ( Fn−1 + Fn+1 ). Relationship a. can be shown false by substituting n = 3 and relationship
d. can be shown false by substituting n = 2.

3. a. See also Lecture 7. We make use of Cassini’s identity Fn+1 Fn−1 − Fn2 = (−1)n . We
have
( Fn+1 Fn−1 + Fn+2 Fn ) − ( Fn2 + Fn2+1 ) = ( Fn+1 Fn−1 − Fn2 ) + ( Fn+2 Fn − Fn2+1 ) = (−1)n +
(−1)n+1 = 0.
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 71

Solutions to the Problems for Lecture 9

1. We prove (9.2) by mathematical induction.

Base case: When n = 1 the left side of (9.2) is F1 = 1 and the right side is F3 − 1 = 1, so
(9.2) is true for n = 1.
Induction step: Suppose (9.2) is true for n = k. Then

k +1 k
∑ Fi = ∑ Fi + Fk+1
i =1 i =1

= Fk+2 − 1 + Fk+1 (from induction hypothesis)

= ( Fk+1 + Fk+2 ) − 1
= Fk+3 − 1, (from recursion relation)

so (9.2) is true for n = k + 1. By the principle of induction, (9.2) is therefore true for all
positive integers.

2. We use the relation Ln = Ln+2 − Ln+1 . Constructing a list of identities, we obtain

L n = L n +2 − L n +1
L n −1 = L n +1 − L n
L n −2 = L n − L n −1
.. ..
. .
L2 = L4 − L3
L1 = L3 − L2 .

Adding all the left hand sides yields the sum over the first n Lucas numbers, and adding
all the right-hand-sides results in the cancellation of all terms except the first and the last.
Using L2 = 3 results in (9.3).

3. Here, we use the relation Fn+1 = Fn+2 − Fn . The first list of identities is

F2n−1 = F2n − F2n−2

F2n−3 = F2n−2 − F2n−4
F2n−5 = F2n−4 − F2n−6
.. ..
. .
F3 = F4 − F2
F1 = F2 − F0 .

Adding the equations yields ∑in=1 F2i−1 = F2n − F0 , and since F0 = 0 the result for odd
Fibonacci numbers is obtained.
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 72

The second list of identities is

F2n = F2n+1 − F2n−1

F2n−2 = F2n−1 − F2n−3
F2n−4 = F2n−3 − F2n−5
.. ..
. .
F4 = F5 − F3
F2 = F3 − F1 .

Adding the equations yields ∑in=1 F2i = F2n+1 − F1 , and since F1 = 1 the result for even
Fibonacci numbers is obtained.

Solutions to the Problems for Lecture 10

1. We prove (10.1) by mathematical induction.

Base case: When n = 1 the left side of (10.1) is F12 = 1 and the right side is F1 F2 = 1, so
(10.1) is true for n = 1.
Induction step: Suppose (10.1) is true for n = k. Then

k +1 k
∑ Fi2 = ∑ Fi2 + Fk2+1
i =1 i =1

= Fk Fk+1 + Fk2+1 (from induction hypothesis)

= Fk+1 ( Fk + Fk+1 )
= Fk+1 Fk+2 , (from recursion relation)

so (10.1) is true for n = k + 1. By the principle of induction, (10.1) is therefore true for all
positive integers.

2. Write

L n L n +1 = L n ( L n + L n −1 )
= L2n + Ln−1 Ln
= L2n + Ln−1 ( Ln−1 + Ln−2 )
= L2n + L2n−1 + Ln−2 Ln−1
= ...
= L2n + L2n−1 + · · · + L22 + L1 L2

Because L1 = 1 and L2 = 3, we have L1 L2 = L21 + 2, and bringing the two to the left-hand-
side proves the identity (10.2).
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 73

Solutions to the Practice quiz: Fibonacci sums

n
1. c. See also Lecture 9. To derive ∑ Fi = Fn+2 − 1, one can sum
i =1

Fn = Fn+2 − Fn+1
Fn−1 = Fn+1 − Fn
Fn−2 = Fn − Fn−1
.. ..
. .
F2 = F4 − F3
F1 = F3 − F2 .

To obtain the desired result, we need to use F2 = 1.

n
2. b. See also Lecture 9, Problem 3. To derive ∑ F2i−1 = F2n , one can sum
i =1

F2n−1 = F2n − F2n−2

F2n−3 = F2n−2 − F2n−4
F2n−5 = F2n−4 − F2n−6
.. ..
. .
F3 = F4 − F2
F1 = F2 − F0 ,

so that the second equation written is F2n−3 = F2n−2 − F2n−4 .

n
3. a. See also Lecture 10. To derive ∑ Fi2 = Fn Fn+1 , one writes
i =1

Fn Fn+1 = Fn ( Fn + Fn−1 )
= Fn2 + Fn−1 Fn
= Fn2 + Fn−1 ( Fn−1 + Fn−2 )
= Fn2 + Fn2−1 + Fn−2 Fn−1
= ...
= Fn2 + Fn2−1 + · · · + F22 + F1 F2 .

To obtain the desired result, we need to use F1 F2 = F12 .

 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 74

Solutions to the Problems for Lecture 12

1. Let x = ∑i∞=0 φ2i . Then

x = 1 + φ2 + φ4 + φ6 + . . . ,
φ2 x = φ2 + φ4 + φ6 + . . . .

Subtracting equations, one obtains (1 − φ2 ) x = 1, or

1
x=
1 − φ2
Φ2
= (from φ = 1/Φ)
Φ2 − 1
Φ2
= (from Φ2 − Φ − 1 = 0)
Φ
= Φ.

Solutions to the Problems for Lecture 13

1. We first obtain the equations for the two diagonal lines. Recall that Φ = 1 + φ = 1/φ.
With the origin of the coordinate system at the lower left-hand corner of the largest golden
rectangle, the longer diagonal passes through the boundary points (0, 1) and (Φ, 0), and
the shorter diagonal passes through the boundary points (1, 0) and (Φ, 1). The two diag-
onal lines can then be determined to be

y = −φx + 1 (largest diagonal), (C.5)

y = Φx − Φ (smallest diagonal). (C.6)

Now, the figure of the spiralling squares is self-similar, and the first unrotated copy
of the whole can be seen to have the attached square of side length φ4 . If we can show
that the drawn diagonal lines pass through the same boundary points of the reduced-size
copy, then these two lines continue to pass through all smaller copies and must eventually
intersect at the accumulation point of all the spiralling squares.
The longer diagonal of the reduced-size copy must pass through its boundary points
(1, φ2 ) and (1 + φ3 , φ3 ), and we need to show that these points satisfy (C.5). We will need
to make use of the following relationship proved earlier:

φ2 = −φ + 1.

We proceed by substituting in the x values into the equation for the diagonal line to show
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 75

that we obtain the correct y values. For x = 1, (y = φ2 ), we have

y = −φ + 1,
= φ2 ,

and for x = 1 + φ3 , (y = φ3 ), we have

y = − φ (1 + φ3 ) + 1
= 1 − φ − φ4
= 1 − φ − (1 − φ )2
= 1 − φ − 1 + 2φ − φ2
= φ (1 − φ )
= φ3 .

Similarly, the shorter diagonal of the reduced-size copy must pass through its bound-
ary points (1 + φ3 , φ2 ) and (1 + φ4 , φ3 ), and we need to show that these points satisfy
(C.6). For 1 + φ3 , (y = φ2 ), we have

y = Φ(1 + φ3 ) − Φ,
= φ2 ,

and for x = 1 + φ4 , (y = φ3 ), we have

y = Φ (1 + φ4 ) − Φ
= φ3 ,

completing our proof.

The accumation point of the squares is found from the intesection of (C.5) and (C.6).
Equating the values of y gives us the equation

−φx + 1 = Φx − Φ,
√
whose explicit solution can be found to be x = (5 + 3 5)/10. The value of y can now be
√
found from (C.5) and is given by y = (5 − 5)/10. The approximate numerical values for
the coordinates are ( x, y) ≈ (1.1708, 0.2764).

Solutions to the Problems for Lecture 14

1. We have already found that the coordinates of one of the centers of a golden spiral is
given by
√ √ !
5+3 5 5− 5
( x, y) = , . (C.7)
10 10

Note that the origin of the largest golden rectangle is taken to be at the bottom-left corner.
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 76

The centers of the four possible golden spirals are symmetric about the mid-point
of the largest golden rectangle, the midpoint having coordinates (Φ/2, 1/2). The four
vertices can then be determined from (C.7) to have coordinates
√ √ ! √ √ !
Φ 5+ 5 1 5 Φ 5+ 5 1 5
+ , − , − , − ,
2 20 2 10 2 20 2 10
√ √ ! √ √ !
Φ 5+ 5 1 5 Φ 5+ 5 1 5
− , + , + , + .
2 20 2 10 2 20 2 10

The length of the two sides of the rectangle can then be calculated to be
√
1+ 5 1
L= √ , W= √ ,
2 5 5
√
which is just a golden rectangle reduced in dimensions by the factor of 5.

Solutions to the Practice quiz: Spirals

1. c. See also Lecture 13. Below is a picture of the golden spiral.

As the curve spirals in, the sides of each successively smaller square reduces by a factor
of Φ, and each square is traversed by a one-quarter turn of the spiral.

2. b. See also Lecture 14. Below is a picture of counterclockwise spiraling squares with
the first square on the right side of the largest golden rectangle. The origin of the golden
spiral occurs in the bottom left of the largest golden rectangle.

3. a. See also Lecture 15. The formula for the sum of the Fibonacci numbers squared is
n
∑ Fi2 = Fn Fn+1 . The right-hand side represents the area of an Fn -by-Fn+1 rectangle, and
i =1
the left-hand side represents the sum of the areas of n squares. With n = 5, we have
F5 = 5 and F6 = 8 and the area of the 5-by-8 rectangle on the right-hand side splits into
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 77

the sum of the areas of n = 5 squares with side lengths given by the first five Fibonacci
numbers.

Solutions to the Problems for Lecture 17

1. We have
√ √
2 = 1 + ( 2 − 1)
1
= 1+ √ ,
1+ 2

which is a recursive definition that can be iterated as follows:

√ 1
2 = 1+ √
1+ 2
1
= 1+
1
2+ √
1+ 2
1
= 1+ ,
1
2+
1
2+ √
1+ 2

√
and so on, so that 2 = [1; 2̄].
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 78

2. We have
√ √
3 = 1 + ( 3 − 1)
2
= 1+ √ ,
1+ 3

which is a recursive definition that can be iterated as follows:

√ 2
3 = 1+ √
1+ 3
2
= 1+
2
2+ √
1+ 3
1
= 1+
1
1+ √
1+ 3
1
= 1+ ,
1
1+
2
2+ √
1+ 3
√
and so on, so that 3 = [1; 1, 2].
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 79

3. We have

e = 2 + 0.718281 . . .
1
= 2+
1.392211 . . .
1
= 2+
1
1+
2.549646 . . .
1
= 2+
1
1+
1
2+
1.819350 . . .
1
= 2+
1
1+
1
2+
1
1+
1.220479 . . .
1
= 2+ ,
1
1+
1
2+
1
1+
1
1+
4.535573 . . .

giving us the beginning of the expansion e = [2; 1, 2, 1, 1, 4, . . . ]. Remarkably, this expan-

sion continues in a regular fashion as

e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, . . . ]

and is sometimes called Euler’s continued fraction.

4. We have
1 F2
Φ0 = [1; ] = 1 = = ,
1 F1
1 2 F3
Φ1 = [1; 1] = 1 + = 2 = = ,
1 1 F2
1 3 F4
Φ2 = [1; 1, 1] = 1 + = = ,
1 2 F3
1+
1
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 80

1 5 F5
Φ3 = [1; 1, 1, 1] = 1 + = = .
1 3 F4
1+
1
1+
1

5. We prove (17.2) by mathematical induction.

Base case: Our previous calculation already shows that (17.2) is true for n = 0, 1, 2, and 3.

Induction step: Suppose that (17.2) is true for positive integers n = k. Then we write

Fk+3 Fk+1 + Fk+2

= (from recursion relation)
Fk+2 Fk+2
Fk+1
= 1+
Fk+2
1
= 1+ (from induction hypothesis)
Φk
= Φ k +1 (from inspection of the continued fraction)

so that (17.2) is true for n = k + 1. By the principle of induction, (17.2) is therefore true
for all non-negative integers.

Solutions to the Problems for Lecture 18

1. We have
g0 /2π = [0; ] = 0,
1 F1
g1 /2π = [0; 2] = = ,
2 F3
1 1 F2
g2 /2π = [0; 2, 1] = = = ,
1 3 F4
2+
1
1 2 F3
g3 /2π = [0; 2, 1, 1] = = = .
1 5 F5
2+
1
1+
1

2. We prove (18.1) by mathematical induction.

Base case: Our previous calculation already shows that (18.1) is true for n = 1, 2, and 3.
 APPENDIX C. PROBLEM AND PRACTICE QUIZ SOLUTIONS 81

Induction step: Suppose that (18.1) is true for positive integers n = k. Then we write

Fk+1 Fk+1
= (from recursion relation)
Fk+3 Fk+1 + Fk+2
1
=
Fk+2
1+
Fk+1
1
= (from Φk = Fk+2 /Fk+1 )
1 + Φk
g k +1
= (from inspection of the continued fraction)
2π

so that (18.1) is true for n = k + 1. By the principle of induction, (18.1) is therefore true
for all positive integers.

Solutions to the Practice quiz: Fibonacci numbers in nature

1. b. See also Lecture 17. The third rational approximation to π from its continued frac-
tion is given by

1 15 333
3+ 1
= 3+ = .
7 + 15 106 106

√
2. c. See also Lecture 17, Problem 1. The fourth rational approximation to 2 from its
continued fraction is given by

1 1 5 17
1+ 1
= 1+ 2
= 1+ = .
2+ 2+ 5
12 12
2+ 12

3. d. See also Lecture 18, Problem 2. The nth rational approximation to g/2π is given by

gn 1 1 Fn Fn
= = = = .
2π 1 + Φn Fn
1 + Fn + 1 Fn + Fn+1 Fn+2