7/27/2019 21121058 Fibonacci Numbers
1/31
FibonacciFibonacciNumbersNumbers
By: Sara Miller
Advisor: Dr. Mihai Caragiu
7/27/2019 21121058 Fibonacci Numbers
2/31
AbstractAbstractv We will investigate various ways of
proving identities involving FibonacciNumbers, such as, induction, linear
algebra (matrices), and combinatorics(0-1 sequences).
vWe will also look at one educationalactivity.
7/27/2019 21121058 Fibonacci Numbers
3/31
SummarySummary
v 1. Introductionv 2. Mathematical Induction
v 3. Linear Algebra (matrices)v 4. Combinatorics (0-1 sequences)
v 5. Educational Activity
7/27/2019 21121058 Fibonacci Numbers
4/31
1. Introduction1. Introduction
vLeonardo PisanoO Born around 1175 in Pisa, Italy
O His nickname was Fibonacci
O He traveled extensively with his father
O Wrote book: Liber Abbaciin 1220
Presented a numerical series now referredto as the Fibonacci numbers
7/27/2019 21121058 Fibonacci Numbers
5/31
Fibonacci NumbersFibonacci Numbers
v 1, 1, 2 , 3, 5, 8, 13, 21, 34, 55,
89, 144, 233,
7/27/2019 21121058 Fibonacci Numbers
6/31
Rabbit ProblemRabbit Problemv
A certain man put a pair of rabbits in aplace surrounded by a wall. How manypairs of rabbits can be produced from
that pair in a year if it is supposed thatevery month each pair begets a new pair
from which the second month on becomesproductive? (Liber Abbaci, chapter 12, p.283-4)
7/27/2019 21121058 Fibonacci Numbers
7/31
Chart of Rabbit ProblemChart of Rabbit ProblemMonth Adult Pairs Baby Pairs Total Pairs
January 1 0 1
February 1 1 2
March 2 1 3
April 3 2 5
May 5 3 8June 8 5 13
July 13 8 21
August 21 13 34
September 34 21 55
October 55 34 89
November 89 55 144
December 144 89 233
January 233 144 377
7/27/2019 21121058 Fibonacci Numbers
8/31
The Fibonacci LinearThe Fibonacci LinearRecurrenceRecurrence
1 11 2
f and f= =
1 2f f fn n n
= +
Initial Conditions:
Recurrence relation:
7/27/2019 21121058 Fibonacci Numbers
9/31
1 2 3 4 5 6 7
1 1 2 3 5 8 13fn
n
7/27/2019 21121058 Fibonacci Numbers
10/31
2. Mathematical Induction2. Mathematical Induction
2.1 Sum of Squares of Fibonacci Numbers:
2 2 2...1 2 1 , 1+ + + = + f f f f fn n n n
I will initially carry out the proof of this identityby induction. Then I will provide a visual proof.
7/27/2019 21121058 Fibonacci Numbers
11/31
Proof by induction:
(a)For 1n = the formula takes the form
2 21 (1)(1) thus 1 11 1 2
f f f
= = =
Thus the first part of the induction(basis step) is finished.
7/27/2019 21121058 Fibonacci Numbers
12/31
(b) Assuming the formula holds true for n, we willprove it for 1n+ .
Therefore,
2 2 2...
1 2 1
f f f f fn nn
+ + + =
+
And we will prove
2 2 2 2...1 2 1 1 2
f f f f f fn n n n+ + + + =+ + +
7/27/2019 21121058 Fibonacci Numbers
13/31
Indeed,2 2 2 2
...1 2 1f f f fn n+ + + +
+
2
1 1
f f f
n n n
= +
+ +
By inductive hypothesis
1 1
f f fnn n
= ++ +
1 2
f fn n
=+ +
By1 2
f f fnn n+ =
+ +
Thus the induction is complete, and I have proved that
the formula holds for all n.
QED.
7/27/2019 21121058 Fibonacci Numbers
14/31
Visual ProofVisual Proof
2 2 2...
1 2 1f f f f fn n n
+ + + =+
7/27/2019 21121058 Fibonacci Numbers
15/31
... , 151 3 2 1 2
+ + + + =
f f f f f nn n
2.2 Sum of Odd Fibonacci Numbers:
7/27/2019 21121058 Fibonacci Numbers
16/31
... 1 , 00 2 4 2 2 1
+ + + + =
+
f f f f f n
n n
2.3 Sum of Even Fibonacci Numbers:
7/27/2019 21121058 Fibonacci Numbers
17/31
2... , 1
1 2 2 3 3 4 2 1 2 2
f f f f f f f f f n
n n n
+ + + + =
Proof:
(a)For 1n = the formula takes the form 2 21 1 =1 thus 1 1
1 2 2
f f f
= =
Thus the first part of the induction (basis step)
is finished.
2.4 Sum of Products of Consecutive Fibonacci
Numbers:
7/27/2019 21121058 Fibonacci Numbers
18/31
(b) Assuming the formula holds true for n, we will proveit for
1n+.
For the inductive step, we will assume
2...1 2 2 3 3 4 2 1 2 2
f f f f f f f f fn n n
+ + + + =
And we will prove
2...1 2 2 3 3 4 2 1 2 2 2 1 2 1 2 2 2 2f f f f f f f f f f f f fn n n n n n n
+ + + + + + = + + + +
7/27/2019 21121058 Fibonacci Numbers
19/31
Indeed,
...1 2 2 3 3 4 2 1 2 2 2 1 2 1 2 2
f f f f f f f f f f f fn n n n n n
+ + + + + + + + +
2 2 2 2 1 2 1 2 2
f f f f fn n n n n
= + ++ + +
By inductive Hypothesis
2 2 2 1 2 1 2 2
f f f f fn n n n n
= + ++ + +
7/27/2019 21121058 Fibonacci Numbers
20/31
2 2 2 1 2 1 2 2f f f f f
n n n n n
= + ++ + +
2 2 2 2 1 2 2f f f f
n n n n= +
+ + +
2 2 2 2 1f f f
n n n
= ++ +
2 2 2
fn= + By
2 2 1 2 2f f fn n n+ =+ +
Thus the induction is complete, and I have provedthat the formula holds for all n.
QED
7/27/2019 21121058 Fibonacci Numbers
21/31
3. Linear Algebra (Matrices)3. Linear Algebra (Matrices)
3.1 Cassinis Identity:
2 11 1
nf f fnn n = +
First we will introduce the transition matrix1 1
1 0T
=
It is easy to see that this matrix satisfies
1 for all 1
1
f fnn T nff nn
+ =
7/27/2019 21121058 Fibonacci Numbers
22/31
It is easy to prove (by induction) that
1
1
f fnnnT
f fn n
+=
for any n=1,2,3,
7/27/2019 21121058 Fibonacci Numbers
23/31
Lets take the determinants of both sides:
2det 1 1nT f f f nn n = +
But,
det det 1n nnT T
= =
Therefore,
2 11 1
nf f fnn n
= +
Thus we have proven the Cassinis Identity.
QED
7/27/2019 21121058 Fibonacci Numbers
24/31
4. Combinatorics4. Combinatorics
4.1 0 - 1 Sequences
One important fact is that the number of 0 1 sequences
of length n without consecutive 1s is for every 12f nn + .
Lets prove this!
7/27/2019 21121058 Fibonacci Numbers
25/31
First denote by An the number of 0-1 sequences of
length n without consecutive 1s.
Here is an example of a string of length 8 without
consecutive 1s:
0 1 0 0 1 0 1 0
7/27/2019 21121058 Fibonacci Numbers
26/31
For 1n = , we have a single , so we have two possibilities a 0
or a 1,
Thus 2 , 21 1 2 3
A f f= = =+
therefore2
A fn n=
+
holds true for 1n= .
For 2n= , we have two , so we have three possibilities 00,
01, 10
Thus 3 , 3
2 2 2 4
A f f= = =+
and
2
A fnn
=+
holds true
for 2n = .
Thus the first part of the induction (basis step) is finished.
7/27/2019 21121058 Fibonacci Numbers
27/31
I shall prove the induction step in the following way:
Assume is true for all .2A f k nk k=
7/27/2019 21121058 Fibonacci Numbers
28/31
0 1 0 0 1 0 1 0
1A
n cellsn Ending with a 0
0 1 0 0 1 0 1 0
2 cellsn
0 1 0 0 1 0 0 1 2
An
Ending with a 1
Therefore,1 2 1 2 2 2 1 2
A A A f f f f fn nn n n n n n= + = + = + =
+ + + +QED
7/27/2019 21121058 Fibonacci Numbers
29/31
We consider the identity 2 21 2 1
f f fn n n+ =
+ +
1n 1n 1n 1n 2n 2n
0
0 1 0
central cell central cell is 0 central cell is 1
2 1 1 2 1n n
+ = 21 1 1f f f
n n n =+ + + 2f f fn n n =
Therefore, 2 22 1 1f f fnn n= ++ + .
4.2 An Example of Combinatorial Proof:
7/27/2019 21121058 Fibonacci Numbers
30/31
Many activities can be used in the classroom to
generate and investigate Fibonacci sequences. One isto have students place 1 and 2 cent stamps across the
top of a postcard (facing with correct side up) in
different arrangements to make up certain postageamounts. The number of different arrangements will
be a Fibonacci number.
5. Educational Activity:
7/27/2019 21121058 Fibonacci Numbers
31/31
END :O)~