DEFINITION

Fibonacci sequence

Posted by: Margaret Rouse

WhatIs.com

  







The Fibonacci sequence is a set of numbers that starts with a one or a zero,
followed by a one, and proceeds based on the rule that each number (called
a Fibonacci number) is equal to the sum of the preceding two numbers. If
the Fibonacci sequence is denoted F (n), where n is the first term in the
sequence, the following equation obtains for n = 0, where the first two terms
are defined as 0 and 1 by convention:

F (0) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

In some texts, it is customary to use n = 1. In that case, the first two terms
are defined as 1 and 1 by default, and therefore:

F (1) = 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

The Fibonacci sequence is named for Leonardo Pisano (also known as

Leonardo Pisano or Fibonacci), an Italian mathematician who lived from
1170 - 1250. Fibonacci used the arithmetic series to illustrate a problem
based on a pair of breeding rabbits:

"How many pairs of rabbits will be produced in a year, beginning with a

single pair, if in every month each pair bears a new pair which becomes
productive from the second month on?" The result can be expressed
numerically as: 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

Fibonacci numbers are of interest to biologists and physicists because they

are frequently observed in various natural objects and phenomena. The
branching patterns in trees and leaves, for example, and the distribution of
seeds in a raspberry are based on Fibonacci numbers.

A Sanskrit grammarian, Pingala, is credited with the first mention of the

sequence of numbers, sometime between the fifth century B.C. and the
second or third century A.D. Since Fibonacci introduced the series to
Western civilization, it has had a high profile from time to time. In The Da
Vinci Code, for example, the Fibonacci sequence is part of an important
clue. Another application, the Fibonacci poem, is a verse in which the
progression of syllable numbers per line follows Fibonacci's pattern.

The Fibonacci sequence is related to the golden ratio, a proportion (roughly

1:1.6) that occurs frequently throughout the natural world and is applied
across many areas of human endeavor. Both the Fibonacci sequence and the
golden ratio are used to guide design for architecture, websites and user
interfaces, among other things.

This was last updated in October 2016

Continue Reading About Fibonacci

sequence
 Platonic Realms provides more calculations of the Fibonacci
sequence.
 MathForum has more information and a visual representation
of the Fibonacci sequence.
 What do CIOs need to know about enterprise UX and UI?
 How to design using the Fibonacci sequence
 Design for yourself, really: Wise words from UX experts

Related Terms
algorithm
An algorithm (pronounced AL-go-rith-um) is a procedure or formula for solving a
problem, based on conducting a sequence of ... See complete definition

independent variable
An independent variable is a variable that is manipulated to determine the
value of a dependent variable.See complete definition

natural number
A natural number is a number that occurs commonly and obviously in nature. See 
complete definition

Word of the Day

CNCF

The Cloud Native Com

(CNCF) is an open so
that promotes the adop
computing.

Word of the Day Arc

20 Newest and Upd

 IPv6 address
 order to cash (O
 Spring Framew
 OpenAPI Speci
  Maven
 feature flagging
 VLAN (virtual L
 Jenkins X
 Kong
 paravirtualizati
 progressive pro
 email address i
(EAI)
 application arc
 container regis
 Middleware as
 API endpoint
BDEFINITION

Fibonacci sequence
  The Fibonacci sequence is a set of numbers that starts with a one
or a zero, followed by a one, and proceeds based on the rule that
each number (called a Fibonacci number) is equal to the sum of the
preceding two numbers. If the Fibonacci sequence is denoted F (n),
where n is the first term in the sequence, the following equation
obtains for n = 0, where the first two terms are defined as 0 and 1 by
convention:

F (0) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

In some texts, it is customary to use n = 1. In that case, the first two

terms are defined as 1 and 1 by default, and therefore:

F (1) = 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

The Fibonacci sequence is named for Leonardo Pisano (also known

as Leonardo Pisano or Fibonacci), an Italian mathematician who
lived from 1170 - 1250. Fibonacci used the arithmetic series to
illustrate a problem based on a pair of breeding rabbits:

"How many pairs of rabbits will be produced in a year, beginning with

a single pair, if in every month each pair bears a new pair which
becomes productive from the second month on?" The result can be
expressed numerically as: 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

Fibonacci numbers are of interest to biologists and physicists

because they are frequently observed in various natural objects and
phenomena. The branching patterns in trees and leaves, for
example, and the distribution of seeds in a raspberry are based on
Fibonacci numbers.

A Sanskrit grammarian, Pingala, is credited with the first mention of

the sequence of numbers, sometime between the fifth century B.C.
and the second or third century A.D. Since Fibonacci introduced the
series to Western civilization, it has had a high profile from time to
time. In The Da Vinci Code, for example, the Fibonacci sequence is
part of an important clue. Another application, the Fibonacci poem, is
a verse in which the progression of syllable numbers per line follows
Fibonacci's pattern.

The Fibonacci sequence is related to the golden ratio, a proportion

(roughly 1:1.6) that occurs frequently throughout the natural world
and is applied across many areas of human endeavor. Both the
Fibonacci sequence and the golden ratio are used to guide design for
architecture, websites and user interfaces, among other things.

Tllerin The Mathematical Magic of

the Fibonacci Numbers
This page looks at some patterns in the Fibonacci numbers
themselves, from the digits in the numbers to their factors
and multiples and which are prime numbers. There is an
unexpected pattern in the initial digits too. We also relate
Fibonacci numbers to Pascal's triangle via the original rabbit
problem that Fibonacci used to introduce the series we now
call by his name. We can also make the Fibonacci numbers
appear in a decimal fraction, introduce you to an easily
learned number magic trick that only works with Fibonacci-
like series numbers, see how Pythagoras' Theorem and
right-angled triangles such as 3-4-5 have connections with
the Fibonacci numbers and then give you lots of hints and
suggestions for finding more number patterns of your own.

Take a look at the Fibonacci Numbers List or, better, see

this list in another browser window, then you can refer to
this page and the list together.

Contents of this page

The   icon means there is a You do the maths... section of

questions to start your own investigations.
The   calculator icon indicates that there is a live
interactive calculator in that section.

 1 Patterns in the Fibonacci Numbers

 1.1 The Final Digits
 1.2 Digit Sums
o 1.2.1 A new research question for you to try
 1.3  Fibonacci Number Digit Sums Calculator
 2 Factors of Fibonacci Numbers

 2.1  You do the maths...

 3 Every number is a factor of some Fibonacci number

 3.1 Are there any numbers n where FEP(n) = n?

 3.2 FEP(n) = n – 1
 3.3 FEP(n) = n + 1
 3.4 FEP(n) = n + 5
 3.5 Other patterns in FEP(n)
 3.6  Fibonacci Factors Calculator
 3.7 Fibonacci Numbers with Index number factor
 3.8 Fibonacci numbers where i ± 1 is a factor of Fib(i)

o 3.8.1  You do the maths...

 3.9 The first Fibonacci number with a given prime as a

factor: FEP(p) for prime p

 4 Fibonacci common factors

  4.1 Neighbouring Fibonacci Numbers have no common
factors

 5 Fibonacci Numbers and Primes

 5.1 Fibonacci numbers and special prime factors

 5.2 Fib(prime) and Carmichael's Theorem
 5.3 No primes next to Fibonacci's!
 5.4 Almost no primes next to Fibonacci's powers either!!
 5.5 A Prime Curio
 5.6 Another Prime Curio
 5.7 More Links and References on Prime Numbers

 6 Remainders after division or Fibonacci MOD n

 6.1   Fibonacci Number Remainder (mod) cycles

Calculator
 6.2 Some interesting facts about Pisano periods
 6.3 A fast algorithm for computing Pisano periods?
 6.4 Pisano Periods for moduli 2 - 299
 6.5 The relationship between the Pisano Period mod n and
FEP(n)

o 6.5.1  You do the maths...

 7 Benford's Law and initial digits

 7.1  You do the maths...

 7.2 When does Benford's Law apply?

o 7.2.1  You do the maths...

 8 Every number starts some Fibonacci Number

 8.1 Is there a Fibonacci number that ends with any given

number?

 9 The Fibonacci Numbers in Pascal's Triangle

 9.1 Why do the Diagonals sum to Fibonacci numbers?

 9.2 Another arrangement of Pascal's Triangle
 9.3 Fibonacci's Rabbit Generations and Pascal's Triangle
  9.4   A Galton's Quincunx Simulator

o 9.4.1  You do the maths...

 10 The Fibonacci Series as a Decimal Fraction

 10.1 A Generating Function for the Fibonacci Numbers

 10.2 Fibonacci decimals
 10.3   An exact Fractions Calculator

o 10.3.1  You do the maths...

 11 A Fibonacci Number Trick

 11.1 A Lightning Calculation

 11.2 So how did Alice do it?
 11.3 Why does it work?
 11.4   Practice here with "Bill"

 12 Another Number Pattern

 13 Fibonacci Numbers and Pythagorean Triangles

 13.1 Using the Fibonacci Numbers to make Pythagorean

Triangles
 13.2   Pythagorean Triples from Fibonacci-type Series
Calculator
 13.3 Fibonacci Numbers as the sides of Pythagorean
Triangles

o 13.3.1 Square Fibonacci Numbers

 13.4 Other right-angled triangles and the Fibonacci Numbers

o 13.4.1  You do the maths...

 14 Maths from the Fibonacci Spiral diagram

 15 ..and now it's your turn!

 15.1  You do the maths...

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More.. 
 1 Patterns in the Fibonacci Numbers
1.1 The Final Digits

Here are some patterns people have already noticed in the

final digits of the Fibonacci numbers:

 Look at the final digit in each Fibonacci number -

the units digit:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,
987, ...

 Is there a pattern in the final digits?

0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, ...

 Yes!
It takes a while before it is noticeable. In fact, the series is
just 60 numbers long and then it repeats the same
sequence again and again all the way through the Fibonacci
series - for ever. We say the series of final digits
repeats with a cycle length of  60.
 Suppose we look at the final two digits in the
Fibonacci numbers. Do they have a pattern?

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

610, 987, ...

 Yes, there is a pattern here too. After Fib(300) the last

two digits repeat the same sequence again and again. The
cycle length is 300 this time.

So what about the last three digits? 

and the last four digits?
and so on??

 For the last three digits, the cycle length is 1,500
 for the last four digits,the cycle length is 15,000 and
 for the last five digits the cycle length is 150,000
 and so on...

1.2 Digit Sums
Michael Semprevivo suggests this investigation for you to
try. 
If we add all the digits of a number we get its digit sum.

Find Fibonacci numbers for which the sum of the

digits of Fib(n) is equal to its index number n: 
For example:-

Fib(10)=55
the tenth Fibonacci number is Fib(10) = 55. 
The sum of its digits is 5+5 or 10 and that is also the index
number of 55 (10-th in the list of Fibonacci numbers). So the
index number of Fib(10) is equal to its digit sum.
Fib(11)=89
This time the digit sum is 8+9 = 17.
But 89 is not the 17th Fibonacci number, it is the 11th (its
index number is 11) so the digit sum of 89 is not equal to its
index number.

Can you find other Fibonacci numbers with a digit

sum equal to its index number?

Here are two more examples of the numbers we seek:

Fib(1)=1 and Fib(5)=5. 
There is also one more whose index number is less than 10
- what is it?

Can you find any more in this table of

Fibonacci numbers up to Fib(300)? 
As a check, you should be able to find TEN (including those
above) up to Fib(200).
How many are there up to Fib(300)?
This makes a nice exercise in computer programming so the
computer does the hard work.

A more difficult question is Does this series (of Fibonacci

numbers which have a digit sum equal to their index
number) go on for ever?

Robert Dawson of Saint Mary's University, Nova Scotia,

Canada summarises a simple statistical argument (originally
in the article referred to below by David Terr) that suggests
there may be only a finite number (in fact, just 20 numbers)
in this series:
 "The number of decimal
digits in Fib(N) can be shown
to be about 0.2 N, and the
average value of a decimal
digit is (0+1+...+8+9)/10 = 4·5.
Thus, unless the digits of
Fibonacci numbers have
some so-far undiscovered
pattern, we would expect the
digit sum to be about 0.9 N.
This falls further behind N as
N gets larger. Fib(2222) (with
465 digits) is the largest
known Fibonacci number
with this property. There are
no others with N<5000, and it
seems likely that Fib(2222) is
actually the largest one.
However, no proof exists!"

1.2.1 A new research question for you to try

If you want to try a new investigation, how about converting

the Fibonacci numbers to a base other than 10 (binary is
base 2 or undecimal is base 11, for example) and seeing
what you get for the digit sums in different bases. Are there
any bases where the Fibonacci numbers with a sum of their
base B digits equal to their index numbers form an infinite
series? In which bases is it a finite series?

  On the Sums of Digits of Fibonacci

Numbers David Terr, Fibonacci Quarterly, vol. 34, August
1996, pages 349-355.
  Two series in Sloane's Encyclopedia of Integer
Sequences are relevant here: A020995 for the index
numbers and A067515 for the Fibonacci numbers
themselves

1.3  Fibonacci Number Digit Sums Calculator

C A L C U L A T O R of Digit Sums of Fibonacci Numbers
for i=
in base  as a list
up to

R E S U L T S     CLEAR 
Digit Fraction Number Pythag
: Factors Remainders Quincunx
Sums s trick Tris

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More.. 

2 Factors of Fibonacci Numbers

There are some fascinating and simple patterns in the
Fibonacci numbers when we consider their factors. You
might like to click here to open a new browser window which
shows the first 300 Fibonacci numbers and their factors. It
will be helpful in the following investigations:
2.1  You do the maths...
1. Where are the even Fibonacci Numbers? 
Write down the index numbers i where Fib(i) is even. 
Do you notice a pattern? 
Write down the pattern you find as clearly as you can first in
words and then in mathematics. Notice that 2=F(3) also.
2. Now find where there are Fibonacci numbers which
are multiples of 3.
and again write down the pattern you find in words and then in
mathematics. Again notice that 3=F(4).
3. What about the multiples of 5? These are easy to spot
because they end with 0 or 5. 
Again, write down the pattern you find.
4. You can try and spot the multiples of 8, if you like now. 
Why 8? Because we have found the multiples of 2, then 3, then 5 and
now 8 is the next Fibonacci number!
5. Do you think your patterns also have a pattern? That is, for any
Fibonacci Number F can you tell me where you think all its
multiples will appear in the whole list of Fibonacci Numbers?
So every  Fibonacci  number is a factor of (an infinite
number of) Fibonacci numbers, that is:

Fibonacci numbers as Factors of

Fibonacci numbers
 1
i 3 4 5 6 7 8 9 11 12 ...
0
Fib(i) 2 3 5 8 13 21 34 55 89 144 ...
F 2=Fib(3) Every 3rd Fib number

a 3=Fib(4) Every 4th Fib number

5=Fib(5) Every 5th Fib number
c
8=Fib(6) Every 6th Fib number
t

o
F(k) ... F(all multiples of k)
r

s
Putting this into words we have:
Every 3-rd Fibonacci number is a multiple of 2 i.e. a multiple
of F(3)
Every 4-th Fibonacci number is a multiple of 3 i.e. a multiple
of F(4)
Every 5-th Fibonacci number is a multiple of 5 i.e. a multiple
of F(5)
Every 6-th Fibonacci number is a multiple of 8 i.e. a multiple
of F(6)

which suggests the general rule: 

Every k-th Fibonacci number is a multiple of F(k)

or, expressed mathematically,

F(nk) is a multiple of F(k) for all values of n and k from 1
up.

  A Primer For the Fibonacci Numbers: Part IX M

Bicknell and V E Hoggatt Jr in The Fibonacci Quarterly Vol 9
(1971) pages 529 - 536 has several proofs that F(k) always
divides exactly into F(nk): using the Binet Formula; by
mathematical induction and using generating functions.
  A free book with the whole collection of parts of the
Primer is available online as a PDF or as separate parts from
the Fibonacci Association.
 3 Every number is a factor of some
Fibonacci number
But what about numbers that are not Fibonacci numbers? 
Which other numbers exactly divide into (are factors of)
Fibonacci numbers?
The surprising answer is that there are an infinite
number of Fibonacci numbers with any given number
as a factor!

For instance, here is a table of the smallest Fibonacci

numbers that have each of the integers from 1 to 13 as a
factor:
This index number for n is called the Fibonacci Entry Point
of n.

The smallest i for which Fib(i) is divisible by n

n 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Fib(i) 1 2 3 8 5 144 21 8 144 610 55 144 13 ... A047930
i 1 3 4 6 5 12 8 6 12 15 10 12 7 ... A001177
Since Fib(15) is the smallest Fibonacci number with 10 as a
factor, then, using the result of the previous section, we
then know that

Fib( any multiple of 15 ) also

has 10 as a factor

thus Fib(15), Fib(30), Fib(45), Fib(60), ..., Fib(15k), ... all

have 10 as a factor. This applies to all numbers n as the
factor of some Fibonacci number.

Here is a graph of the series, the index number i of the first

Fibonacci number that has a factor of n for n up to various
values: 

Show the graph up to n= 25 100 250 500 1000 3000

 The Fibonacci Series beginning 0,1,1,... is the only (general)
Fibonacci sequence beginning a,b,a+b,... which has all the
primes as factors of some number in the series. This was
proved by Brother U Alfred in the reference.

  Primes which are factors of all Fibonacci

sequences,Brother U Alfred, Fib Quart, 2 (1964), pages 33-
38. PDF
  If we take each number n = 1,2,3,... and find the
smallest i for which Fib(i) has n as a factor, we obtain this
series of index (i) values:
1,3,4,6,5,12,8,6,12,15,10,12,7,24,20,12,9,12,18,30,8,30,...
is Sloane's A001177
  An early reference for the theorem that every number
is a factor of some Fibonacci number seems to be N N
Vorob'ev in his Fibonacci Numbers booklet, published by
Pergamon in 1961 where a proof is also given. Also, he
showed that the first Fibonacci number with a factor i will be
found within the first i2Fibonacci numbers and thereafter at
double, treble etc.. that index number. The original version
is in Russian, Chisla fibonachchi, 1951 and it is now again in
 print as Fibonacci Numbers, N N Vorob'ev, Birkhauser (Jan
2003).
  TheFibonacci Series Modulo m D. D. Wall, The
American Mathematical Monthly (1960) pages 525-532
is the earliest and most comprehensive paper on the subject
of Fibonacci factors and Pisano periods.
Wall uses:

o un for our Fib(n)

o vn for our Lucas(n)
o fn for our General Fibonacci Series beginning with
a and b: G(a,b,n)
o k(m) for the Pisano period of the Fibonacci
numbers modulo m
o h(a,b,m) for the Pisano period of the General
Fibonacci sequence G(a,b,n) modulo m

In the following sections we use the name FEP(n) for the

Fibonacci Entry Point of n, the smallest index of a Fibonacci
number that has n as a factor and look at some patterns
and special cases.

3.1 Are there any numbers n where FEP(n) = n?

There are some numbers such as 5 that are also their own
entry points since Fib(5) = 5 is the first Fibonacci number with
an factor of 5.
Are there others?
Yes! For instance Fib(12) = 144, the twelfth Fibonacci number
is the first one with a factor of 12.
A list of those values of n where FEP(n) = n with n up to 1000
is

1, 5, 12, 25, 60, 125, 300, 625

This is a combination of two series which becomes clear if

you factorize each of these numbers. 
Can you find the next two numbers? 

3.2 FEP(n) = n – 1
 Fib(10) = 55 = 11 × 5 so the tenth is the first Fibonacci
number with 11 as a factor: FEP(11) = 10. 
Fib(18) = 2584 = 19 × 136 so the 18th Fibonacci number is
the first with 19 as a factor: FEP(19) = 18
The list of the first n where FEP(n) = n – 1 is:
11, 19, 31, 59, 71, 79, 131, 179, 191, ... A106535
Is there a formula for these values?
Brother U Alfred showed that all these terms end in 1 or 9:

  Primes which are factors of all Fibonacci

sequences,Brother U Alfred, Fib Quart, 2 (1964), pages 33-
38.

3.3 FEP(n) = n + 1

There is also a sequence of numbers with an FEP just one

more than the number itself: i.e. FEP(n) = n + 1:
for instance 
3 is a factor of Fib(4) = 3 and
7 is a factor of Fib(8) = 21 
and the list of the first few n where FEP(n) = n + 1 is:
2, 3, 7, 23, 43, 67, 83, 103, 127, 163, 167, ... A000057 
All these values end in 3 or 7 but is there a formula for
these? 
Factoring shows that all these are prime.
Brother U Alfred showed that all these terms end in 3 or 7 -
see the reference in the previous section.

3.4 FEP(n) = n + 5

Benoit Cloitre noticed a connection between the n where

FEP(n) = n + 1 and those n with FEP(n) = n + 5: 
FEP(n) = n + 5: n= 10 15 35 115 215 335 415 515 635 ...
FEP(n) = n + 1: n= 2 3 7 23 43 67 83 103 127 ...
Can you find the connection? 

3.5 Other patterns in FEP(n)

There are also many other patterns in FEP(n). Here, for

instance, are the equations of some of straight lines that lie
on or near apparent lines of points in one of the
graphs above:

It looks as if for any n, FEP(n) ≤ 2n but the only proof we

have is that FEP(n) ≤ n2 in the Vorob'ev reference above.

3.6  Fibonacci Factors Calculator

C A L C U L A T O R Fibonacci Factors
for i=
up to

R E S U L T S     CLEAR 
Digit Fraction Number Pythag
: Factors Remainders Quincunx
Sums s trick Tris

3.7 Fibonacci Numbers with Index number factor

Earlier we saw that every number is a factor of some

Fibonacci number, the first index number being called the
FEP of that number.
Once we know the index number of the first Fibonacci
number with n as a factor, FEP(n), then all the multiples of
that index are also Fibonacci numbers with n as a factor.
This since FEP(24) is 12, then Fib(12) has a factor of 24 and
so does Fib(24), Fib(36), Fib(48), etc.
So now we can ask the question:
Which Fibonacci numbers Fib(n) have n as a factor?
For instance F(12)=144 which has 12 as a factor;
F(25)=75025 which has 25 as a factor;
but F(15)=610 which does not have 15 as a factor.

Here are the first few Fibonacci numbers F(n) with n as a

factor:

n Fib(n) = n × m
1 1= 1 × 1
5 5= 5 × 1
12 144 = 12 × 12
24 46368 = 24 × 1932
25 75025 = 25 × 3001
36 14930352 = 36 × 414732

The series of indices of such Fibonacci numbers is:

1, 5, 12, 24, 25, 36, 48, 60, 72, 96, ... A023172
Can you identify which numbers are in this sequence? 

3.8 Fibonacci numbers where i ± 1 is a factor of Fib(i)

i–1 is a factor of F(i)

Prime factors of F(i)
i
i–1 the rest
2 1 1
3 2 1
4 3 1
8 7 3
1
13 29
4
1
17 23×19
8
2
23 25×32×7
4
3
37 113×9349
8
4
43 3×89×199×307
4
 4
47 26×32×7×23×1103
8
5
53 23×17×19×109×5779
4
6
67 3×1597×3571×63443
8
7
73 149×2221×54018521
4
8
83 24×32×13×29×211×281×421×1427
4
9
97 13×29×6168709×599786069
8
Fibonacci index numbers i where Fib(i) has i–1
as a factor:
2, 3, 4, 8, 14, 18, 24, 38, 44, 48, 54, 68, 74, 84, 98,
104, ... A100993
Though all the i listed here are one more than a prime (i-1 is
prime), this is not true in general. The smallest such is 324,
which has 323 as a factor of Fib(324) but 323=17×19. See
the notes on A100993 in the link.
i+1 is a factor of F(i)
Prime factors of F(i)
i
i+1 the rest
10 11 5
18 19 23×17
28 29 3×13×281
30 31 23×5×11×61
40 41 3×5×7×11×2161
58 59 19489×514229
60 61 24×32×5×11×31×41×2521
70 71 5×11×13×29×911×141961
78 79 23×233×521×859×135721
88 89 3×7×43×199×263×307×881×967
10
101 3×52×11×41×151×401×3001×570601
0
10
109 24×34×17×19×53×107×5779×11128427
8
13
131 5×11×233×521×2081×24571×14736206161
0
Fibonacci index numbers i where Fib(i) has i+1
as a factor:
 10,18,28,30,40,58,60,70,78,88,100,108,130,138,... 
A100992
All these i are one less than a prime (i+1 is prime) this is
not always true. The smallest such is 441 since 442 is a
factor of Fib(441) and 442 is not prime.
Are there any more patterns hidden here in the factors of
Fibonacci numbers?
If so, let me know (click on Dr Ron Knott at the foot of this
page for contact details) and I'll try to include some of them
here.
3.8.1  You do the maths...
You might find this Table of Fibonacci Factors useful.
1. Another variation is to look at the remainder when we divide
Fib(i) by i.
Which index numbers, i, when we divide Fib(i) by i, have a
remainder of 1? 
For example, the smallest is Fib(2)=1 which obviously has a
reminder of 1 when we divide Fib(2) by 2;
the next is Fib(11)=89 which, when we divide 11 leaves a
remainder of 1.
So your answer should start 2, 11, ... 
2. What about those index numbers i where Fib(i) has a
remainder of 1 less than i when Fib(i) is divided by i?
This time we start again with Fib(2)=1 since it leaves a
remainder of 2-1 when we divide it by i=2;
Also Fib(3)=2 and Fib(4)=3 are also one less than their index
numbers and the next is Fib(7)=13 which leaves a remainder of
7-1=6 when we divide 13 by 7.
So this time your answer starts: 1, 2, 3, 4, 7, ... 

3.9 The first Fibonacci number with a given prime as a

factor: FEP(p) for prime p

Above we looked at all n and which was the first Fibonacci

number for which that n was a factor.
In this section, we concentrate only on those n which are
prime numbers.
If we look at the prime numbers and ask when they first
appear as a factor of a Fibonacci number, we find they do so
within the first p+1 Fibonacci numbers. In this table, i is the
 index of the first Fibonacci number that has the prime as a
factor:
Prime p 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
first
index 3 4 5 8 10 7 9 18 24 14 30 19 20 44 16 27 58 15 68 70
i
The first-index numbers seem to be either equal to the
prime (as for p=5) or one less (as p=11) or 1 more (p=7) in
many cases. What about the others? 
They are factors of p+1 (as in the case of p=17 where 9 is a
factor of p+1=18) or of p–1 (e.g. p=29 where the index 14
is a factor of p-1=28). 
This is true in general.

This series on the lower row:

3,4,5,8,10,7,9,18,24,14,30,19,20,44,16,27,58,15,68,70,...
is Sloane's A001602. It is a subsequence of A001177 above,
selecting the numbers at the prime positions. 
The smallest Fibonacci number which has the nth prime as a
factor gives the series: 2, 3, 5, 21, 55, 13, 34, 2584, ...
which is A051694. But as these Fibonacci numbers get large
rapidly, it is easier to use the index numbers of such
Fibonacci numbers to get the series above (A001602). 
Vajda (reference at foot of this page), on page 84 states:

Let F(u), u > 0, be the

smallest Fibonacci number
divisible by the prime p. The
subscript u is called the rank
of apparition of p, and we
know that it is a factor of, or
equal to, p–1 or p+1.
An alternative name is the
Fibonacci entry point (FEP)
and this applies to any
number, not just the primes.

  Clark Kimberling has a brief biography of Lucas

  more information on Edouard Lucas (1842-1891)
at the St. Andrews MacTutor site
  On another of Ron Knott's Maths pages we look at the
Lucas numbers, a series of numbers with the same rule as
 the Fibonacci numbers but starting with 2 and 1. In many
senses Lucas numbers and Fibonacci numbers are twin
series.

4 Fibonacci common factors

One of the fundamental divisibility properties of Fibonacci
numbers concerns factors common to two Fibonacci
numbers.
If a number is a factor of both F(n) and F(m) then it is also
a factor of F(m+n).
This is a consequence of the formula:
F(n+m) = F(m–1) F(n) + F(m) F(n+1)
which is a special case of formula (8) in Vajda (reference at
foot of this page)

But this is also part of a more general result about factors

common to two Fibonacci numbers. 
If g is the greatest divisor of both F(m) and F(n) then it is
also a Fibonacci number. Which Fibonacci number? Its index
number is the greatest divisor common to the two
indices m and n!
If we use gcd(a,b) to mean the greatest common divisor
(factor) of  a  and  b then we have:

gcd( F(m), F(n) ) = F( gcd(m,n) )

  This result is Theorem 11 in Fibonacci Numbers, N N

Vorob'ev (2003 translation of the 1951 Russian original).

This section was suggested by an email from Allyn Shell .

4.1 Neighbouring Fibonacci Numbers have no common

factors

You might have noticed that no even Fibonacci number is

next to another even Fibonacci number, or, no two
neighbouring Fibonacci's have a common factor of 2. 
In the last section we saw that Fib(3)=2 so we would expect
the even Fibonacci numbers (with a factor of 2) to appear
every at every third place in the list of Fibonacci numbers.
 The same happens for a common factor of 3, since such
Fibonacci's are at every 4-th place (Fib(4) is 3).

In fact, there will not be a Fibonacci number as a common

factor between two neighbouring Fibonacci's for the same
reason.

But what about other numbers as factors such as 6 or

7?

The answer is that no number (bigger than 1) is a factor of

two  neighbouring  Fibonacci numbers. 
Two numbers that have no common factors are
called relatively prime (to each other).

There is a proof of this that Tom E Ace wrote to me about --

and it is so simple!

 If A and B have a common factor then it must also be a

factor of A+B.
 If A and B have no common factor, then neither do B
and A+B
for if B and A+B had a common factor, then
their difference would too but their difference is just A.

So in any Fibonacci-type series which starts with A and B, if

A and B are relatively prime then so are all pairs of
consecutive numbers in the series.
Alternatively, if A and B have a common factor then so do B
and A+B (the next pair in the series) and so on, so that this
factor is a factor of all numbers in the series.

Since F(1)=1 and F(2)=1 have no common factor, then no

neighbouring pairs in the Fibonacci series have a common
factor.
We have just shown that

F(n) and F(n+1) are relatively prime.

Now let's look at Fibonacci numbers that have no factors at

all (apart from 1 and themselves of course), the prime
Fibonacci numbers:
 5 Fibonacci Numbers and Primes
We have seen from investigations above that F(nk) is a
multiple of F(k) for all values of n and k = 1,2,... 
This means that if the subscript has factors (i.e. is
composite, is not a prime) then so is that Fibonacci number
-- with one exception: can you find it?
So what about those Fibonacci numbers with no
factors (apart from 1 and itself, of course)? 
These are the Fibonacci numbers that are primes.
We can now deduce that 
Any Fibonacci number that is a prime number must also
have a subscript that is a prime number
again with one little exception - can you find it? Hint: you
won't have to search far for it  .

Unfortunately, the converse is not always true: 

that is, it is not true that if a subscript is prime then so is
that Fibonacci number. 
The first case to show this is the 19th position (and 19 is
prime) but
F(19)=4181 and F(19) is not prime because 4181=113x37.

In fact, a search using Maple finds that the list of index

numbers, i, for which Fib(i) is prime begins as follows:

1
i 3 4 5 7 13 17 23 29 43 47 83
1
F( 1 8 23 159 2865 5142 4334944 29712150 9919485309475
2 3 5
i) 3 9 3 7 7 29 37 73 5497
Now you should be able to spot the odd one out: that one
number, i, which is not a prime in the list above, even
though Fib(i) is.

The series continues (updated January 2007):

i Fib(i) Number of digits Prime?

131 10663404174...72169 28
137 19134702400...23917 29
359 47542043773...76241 75
 431 52989271100...62369 90
433 13872771278...68353 91
449 30617199924...65949 94
509 10597999265...29909 107
569 36684474316...65869 119
571 96041200618...74629 119
2971 35710356064...16229 621
4723 50019563612...91957 987
5387 29304412869...55833 1126
9311 34232086066...76289 1946
9677 10565977873...70357 2023
14431 35575535439...75869 3016
25561 38334290314...14961 5342
30757 30434499662...75737 6428
35999 99214776140...24001 7523
37511 96802910427...75089 7839  Jun 2005
50833 13159270824...02753 10624  Oct 2005
81839 97724940760...46561 17103
104911 5660323637...84189 21925 ?
130021 2706998033...75321 27173 ?
148091 6904738850...74809 30949 ?
201107 3371962609...27913 42029 ?
397379 8912712429...66921 83047 ?
433781 3296782330...74981 90655 ?
590041 8448035604...82641 123311 ?
593689 2059052250...74289 124074 ?
604711 5962634693...37389 126377 ?
Those marked   are definitely prime;
those marked? are probably prime but have not been
proved so (explained here).
  The largest known Fibonacci prime, F(81839) was
reported in April 2001 by David Broadbent and Bouk de
Water
  The series of index numbers i of the prime Fib(i):
3,4,5,7,11,13,17,23,29,43,47,83,... is Sloane's A001605
  The glossary entry on Chris Caldwell's The Prime
Pages under Fibonacci Prime has more information and
references.

5.1 Fibonacci numbers and special prime factors

Every Fibonacci number is marked in a special way. 

If we look at the prime factors of a Fibonacci number, there
will be at least one of them that has never before appeared
as a factor in any earlier Fibonacci number. This is known
as Carmichael's Theorem and applies to all Fibonacci
numbers except 4 special cases:

1. Fib(1)=1 (has no prime factors),

2. Fib(2)=1 (has no prime factors),
3. Fib(6)=8 which only has prime factor 2 which is also
Fib(3),
4. Fib(12)=144 which also only 2 and 3 as its prime
factors and these have appeared earlier as Fib(3)=2
and Fib(4)=3.

Apart from these special cases, the theorem is true for all
Fib(n).

Those prime factors that have never appeared earlier in the

table are shown like this.

Here is the first part of a table of Fibonacci numbers and

their prime factors: 

The first 25 Fibonacci numbers Factored n : F(n)=factorisation

0 : 0 = 
1 : 1 = 
2 : 1 = 
3 : 2 PRIME
4 : 3 PRIME
5 : 5 PRIME
6 : 8 = 23
7 : 13 PRIME
 8 : 21 = 3 x 7
9 : 34 = 2 x 17
10 : 55 = 5 x 11
11 : 89 PRIME
12 : 144 = 24 x 32
13 : 233 PRIME
14 : 377 = 13 x 29
15 : 610 = 2 x 5 x 61
16 : 987 = 3 x 7 x 47
17 : 1597 PRIME
18 : 2584 = 23 x 17 x 19
19 : 4181 = 37 x 113
20 : 6765 = 3 x 5 x 11 x 41
21 : 10946 = 2 x 13 x 421
22 : 17711 = 89 x 199
23 : 28657 PRIME
24 : 46368 = 25 x 32 x 7 x 23
25 : 75025 = 52 x 3001
[See the whole list up to Fib(300) on the next web page in a
new window.]

  A Result about the Primes Dividing Fibonacci

Numbers by M S Boase in Fibonacci Quarterly vol 39
(2001), pages 386-391 contains a proof of this result but
does not refer to it as Carmichael's Theorem. The problem is
traced back to an analogous result proved by K Zsigmondy
in 1892.
  A Simple Proof of Carmichael's Theorem on
Primitive Divisors by M Yabuta in Fibonacci Quarterly vol
39 (2001), pages 439-443 also contains a proof and refers
to the following article...
  On the Numerical Factors of the Arithmetic
Forms αn±β n by R D Carmichael in Annals of Maths vol 15
(1913) pages 30-70, where Carmichael refers to such first-
occurrence-prime-factors as characteristic factors

5.2 Fib(prime) and Carmichael's Theorem

Shane Findley of Dover, USA, points out that all the factors

of Fib(p) when p is a prime number are characteristic prime
factors. 
Let's have a look at what this means in terms of our Table of
Fibonacci Factors.
 This relies on two properties of Fib(i) that we have already
seen (on this page):

1. In the Factors of Fibonacci Numbers section we saw

that
if i itself has a factor k (so that we can write i as nk) 
then Fib(nk) has Fib(k) as a factor also.
2. Also, if Fib(i) is a prime number then i itself must be
prime - see the Fibonacci Primes section.

So if i is prime - and let's call it p here to remind ourselves

we are considering the special case of Fib(i) for a prime
number i - then p will have no factors and therefore Fib(p)
also can have no earlier Fibonacci numbers as its factors. 
Note that this does not mean Fib(p) itself must be prime,
only that no smaller  Fibonacci number  can be a factor.
We found an example of this in Fib(19) which is 4181 = 37 x
113, and, although 19 is a prime number, Fib(19) is not. 
Carmichael's Theorem says that there are special prime
factors of Fib(p) that have not occurred earlier in our list of
Fibonacci numbers. 
So, if p is a prime number, then

 either Fib(p) is prime - in which case this is the first

time we have seen this prime number in the list of Fibonacci
factors
 or else, if Fib(p) has factors, at least one of them is
new - a characteristic factor.

But Shane's observation is that all the prime factors of

Fib(p) are characteristic factors!

To put this more simply for a prime number p, Fib(p) is

either

 a prime itself or
 is a product of prime factors that all appear to be
characteristic (appear for the first time in our list of
Fibonacci factors).

Here is a selection of lines from the Factors Table for those

Fib(i) where i is a prime number. You will notice that either
they are prime numbers or else their factors are all
shown like this to show they are characteristic factors:

The Fibonacci Numbers Fib(p)

where p is a prime number less than 100
n : F(n)=factorisation
2 : 1
3 : 2 PRIME
5 : 5 PRIME
7 : 13 PRIME
11 : 89 PRIME
13 : 233 PRIME
17 : 1597 PRIME
19 : 4181 = 37 x 113
23 : 28657 PRIME
29 : 514229 PRIME
31 : 1346269 = 557 x 2417
37 : 24157817 = 73 x 149 x 2221
41 : 165580141 = 2789 x 59369
43 : 433494437 PRIME
47 : 2971215073 PRIME
53 : 53316291173 = 953 x 55945741
59 : 956722026041 = 353 x 2710260697
61 : 2504730781961 = 4513 x 555003497
67 : 44945570212853 = 269 x 116849 x 1429913
71 : 308061521170129 = 6673 x 46165371073
73 : 806515533049393 = 9375829 x 86020717
79 : 14472334024676221 = 157 x 92180471494753
83 : 99194853094755497 PRIME
89 : 1779979416004714189 = 1069 x 1665088321800481
97 : 83621143489848422977 = 193 x 389 x 3084989 x 361040209

5.3 No primes next to Fibonacci's!

Let's look at the numbers next to each Fibonacci number...

.
n 3 4 5 6 7 8 9 10 11 12 13 .
.
.
Fib(
2 3 5 8 13 21 34 55 89 144 233 .
n)
.
Fib( .
1  2  4  7  12  20  33  54  88  143  232  
n) .
3 4 6 9 14 22 35 56 90 145 234
±1 .
We see there are a few small Fibonacci numbers which have
a prime neighbour (shown like this) but then they seem
 to stop. (143=11x13 is not a prime.) 
Is this just a fluke or a feature of all but a few initial
Fibonacci numbers - that their neighbours are never prime?
Toby Gee, a student at John of Gaunt's School, Trowbridge
proved this in the 1996/97 (see the references at the end of
this section).

He gave formulae for the factors too:

For the Fibonacci numbers with even index numbers, that is
F(2n), we have:-

F(2n) + (–1)n = ( F(n+2) + F(n) ) F(n–1)

F(2n) – (–1)n = ( F(n) + F(n–2) ) F(n+1)

and for the odd index numbers, F(2n+1), we have similarly:

F(2n+1) + (–1)n = ( F(n+1) + F(n–1) ) F(n+1)

F(2n+1) – (–1)n = ( F(n+2) + F(n) ) F(n)
All of these are derived from Vajda-15a and Vajda-15b (see
my Fibonacci, Phi and Lucas Numbers Formulae page).

  Letter from Toby Gee in Mathematical Spectrum, vol

29 (1996/1997), page 68.
 Greatest Common Divisors in Altered Fibonacci
Sequences U Dudley, B Tucker Fibonacci Quarterly 1971,
pages 89-91 give these formulae too in an expanded form.

5.4 Almost no primes next to Fibonacci's powers

either!!

So having seen that the Fibonacci numbers influence their

neighbours so that no neighbour is prime, what
about neighbours of the squares of Fibonacci
numbers?

Two formulae answer our question immediately:

{
F(n – 2)F(n + 2) if n is odd
F(n)2 + 1 =
F(n – 1)F(n + 1) if n is even

{
F(n – 1)F(n + 1) if n is odd
F(n)2 – 1 =
F(n – 2)F(n + 2) if n is even
These two formulae tell us that
 the neighbours of F(n)2 are never prime, 
in fact they are always the product of two Fibonacci
numbers!

So we could now investigate the neighbours of the cubes

of Fibonacci Numbers and indeed I will leave you to
discover the formulae that apply in those cases.
You will find that they too are never prime!! 
Spoiler: 

The general result was found by Vernon Hoggatt Jr and

Marjorie Bicknell-Johnson in 1977.

The smaller neighbour of  every power  of every Fibonacci

number (beyond F(3)=4) is always composite.
This is easy to see with a little algebra since xn – 1 always
has x – 1 as a factor no matter what number x is.

For the larger neighbour of a power of a Fibonacci number,

all of them are again composite except in one special case:
when the power is itself a power of 2 (that is, it is 4, 8, 16,
32, ...) AND also the Fibonacci index number is a multiple of
3. In this case the number may be prime!

For example, all these neighbours on the "+1" side of a

power of a Fibonacci number are prime:

F(9)4 + 1 = 1336337
F(198)4 + 1 (165 digits)
F(15)8 + 1 (23 digits) 
F(48)8 + 1 (78 digits) 
F(51)8 + 1 (83 digits) 
F(21)32 + 1 (130 digits)

You will see that all the powers are themselves powers of 2
and all the indices are multiples of 3. It seems that such
primes are quite rare though.

So Fibonacci numbers exert a powerful influence   in that

they (almost always) make any number next to them or
their powers factorize!
 Composites and Primes Among Powers of
Fibonacci Numbers increased or decreased by one V E
Hoggatt Jr and M Bicknell-Johnson, Fibonacci Quarterly vol
15 (1977), page 2.

5.5 A Prime Curio

G. L. Honaker Jr. pointed me to a little curio about the

Fibonacci and the prime numbers: that the number of
primes less than 144, which is a Fibonacci number, is 34,
also a Fibonacci number. He asks:
Can this happen with two larger Fibonacci numbers?
I pass this question on to you - can it? The link to the Prime
Curio page uses the notation that
(N) means the number of primes between 1 and N
and includes N too if N is prime. (See also a graph of this
function.) 
Since the prime numbers begin
2, 3, 5, 7, 11, 13, 17, ...
then  (8)=4 (there are 4 primes between 1 and 8, namely
2, 3, 5 and 7) and  (11)=5.
Here are some smaller values that are also Fibonacci
numbers:
(2) = 1
(3) = 2
(5) = 3
(21) = 8

5.6 Another Prime Curio

M J Zerger noticed that the four consecutive Fibonacci

numbers: F(6)=13, F(7)=21, F(8)=34 and F(9)=55 have a
product of 13x3x7x17x2x5x11 or rearranging the factors
into order: 2x3x5x7x11x13x17 which is the product of the
first seven prime numbers!

5.7 More Links and References on Prime Numbers

  There is a complete list of all Fibonacci numbers and

their factors up to the 1000-th Fibonacci and 1000-th Lucas
numbers and partial results beyond that on Blair Kelly's
Factorisation pages
  Chris Caldwell's Prime Numbers site has a host of
information.
  For the real enthusiast, join the Yahoo group on
the PrimeForm computer program and related matters to
primes. Its Files folder has a section on Lucas and Fibonacci
primes.
  See Neil Sloane's Online Encyclopedia of Integer
Sequences where series number A001605 is the series of i's
for which Fib(i) is known to be prime:
3,4,5,7,11,13,17,23,29,... and contains fairly up-to-date
information on the latest results.
  Factorization of Fibonacci Numbers D E Daykin
and L A G Dresel in The Fibonacci Quarterly, vol 7 (1969)
pages 23 - 30 and 82 gives a method of factoring a Fib(n)
for composite n using the "entry point" of a prime, that is,
the index of the first Fibonacci number for which prime p is
a factor.
  Mathematics Teacher M J Zerger vol 89 (1996) page
26

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More.. 

6 Remainders after division or Fibonacci

MOD n
Earlier on this page we looked at the final digits of a
Fibonacci number
0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, .... A003893
which repeats after 60 digits.
These are the remainders of the Fibonacci numbers when we
divide by 10, or, to use the mathematical term, Fibonacci
numbers modulo 10. 
x modulo n means the remainder when we divide the
whole number x by n and it is also written as x mod n for
short. You may also see x ≡ a (n)meaning x mod n is a.
The final two digits are therefore the Fibonacci numbers
mod 100:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 44, .... A105471
and this cycle repeats after 300 numbers. 
The final three digits are the Fibonacci's mod 1000 with a
cycle length of 1500, and so on.
If we look at the Fibonacci numbers mod 2, then we get
either 0 or 1 as these are the only two remainders we can
have on dividing by 2. However, if the number is even the
remainder is 0 and if it is odd the remainder is 1. This is
called the parity of a number x and so x mod 2 tell us if x is
even or odd. 
For the Fibonacci numbers we have:
0 1 1 2 3 5 8 13 21 ...
Even Odd Odd Even Odd Odd Even Odd Odd ...
0 1 1 0 1 1 0 1 1 ... A011655
and the cycle repeats with a cycle length of 3.
So what about division by other values?
We will always get a cycle that repeats!
The reason is that there are only a finite number of
remainders when we divide by N: the values 0, 1, 2, ..., N-1
(N of them) and therefore there are a finite number
of pairs of remainders (N2) so when we keep adding the
latest two Fibonacci's to get the next, we must eventually
get a pair of remainders that we have had earlier and the
cycle will repeat from that point on.
Here are the Fibonacci numbers mod 3:
0, 1, 1, 2, 0, 2, 2, 1, (0, 1,...) A082115
so the cycle-length of the Fibonacci numbers mod 3 is 8.
For the divisors (moduli) 2, 3, 4, 5, and so on we have the
following cycle lengths for the Fibonacci Numbers:
mod 2 3 4 5 6 7 8 9 10 11 12 ...
cycle length 3 8 6 20 24 16 12 24 60 10 24 ... A001175
The cycle lengths are also called the Pisano periods. You
can investigate the cycle-lengths for different divisors using
this Calculator:

6.1   Fibonacci Number Remainder (mod) cycles

Calculator

C A L C U L A T O R 
窗体顶端

of the Fibonacci numbers mod  up to mod 

R E S U L T S  CLEAR  
窗体底端
: Digit Factors Remainders Quincunx Fraction Number Pythag
 Sums s trick Tris

6.2 Some interesting facts about Pisano periods

 The list of "records" or the highest Pisano period so far,

is given by

1 12 15 20 24 A
mod 2 3 5 6 25 30 50 98 250 490 566 590
0 5 0 6 3 ?
Pisan
o 2 2 6 10 12 30 33 50 60 62 64 150 168 170 174 A
3 8
perio 0 4 0 0 0 0 6 0 0 4 8 0 0 4 0 ?
d


 The Pisano periods can be at most 6 times the modulus
with examples shown in red in the table above. This is only
achieved for moduli that are twice a power of 5:

 for 2×5 = 10, the cycle length is 60

 2×52 = 50 has cycle length 300
 2×53 = 250 with cycle length 1500
 10, 50, 250, 1250,
6250, ... A020699 (or A095687)

 Apart from modulo 2, all the cycle lengths are even.

For mod 2 the cycle is 0,1,1, 0,1,1, ... of length 3
 There are some numbers n where the length of the
cycle mod n is n itself, called fixed points,
for example the Fibonacci numbers mod 24 are
0,1,1,2,3,5,8,13,21,10,7,17,0,17,17,10,3,13,16,5,21,2,23,1
which then repeats so the cycle has length 24: Pisano(24) =
24.
The series of these fixed points of the Pisano function is
(1,) 24, 120, 600, 3000, 15000, 75000,
375000, ... A235702
The entries are all of the form 24×5n so that starting with
24 each of the following is 5 times the previous one.
 A pattern in the primes:

1 2 3
prime p 3 7 17 43 53 ... A071774
3 3 7
Pisano(p) 8 16 2 36 4 7 88 108 =2p+2
 8 8 6

 All these primes end in 3 or 7, but other such primes

are not in this table, for example,

23
prime p 47 107 113263 ... A216067
3
Pisano(p) 32 72 76 52 176 ≠2p+2


 Another primes pattern:

1 4 7
prime p 19 31 59 61 79 109 ... A003147
1 1 1
1 4 7
Pisano(p) 18 30 58 60 78 108 p–1
0 0 0

 All these primes end in 1 or 9, but again there are

exceptions:

prime p 29 89 101 139 151 181 199

Pisano(p) 14 44 50 46 50 90 22

 but you many have noticed that quite a few of the

Pisano periods are factors of p-1.

6.3 A fast algorithm for computing Pisano periods?

The following results are from Marc Renault's page:

 Look at this table of Pisano periods of n, 2n, 3n, ... :

Pisano n 2n 3n 4n 5n 6n 7n
n=2 3 6 24 12 60 24 48
n=3 8 24 24 24 40 24 16
n=4 6 12 24 24 60 24 48
2
n=5 60 40 60 100 120 80
0

 Can you see that Pisano(kn) is a multiple of Pisano(n)

for each of these n?
This can be proved true for all n - see Marc's page as
mentioned above.
So if n divides m which we write as n | m then P(n) | P(m).
 Using the last result, if we find the prime factors of n, n
= p1a1 p2a2 ... then Pisano(n) will be the lowest common
multiple (LCM) of all the Pisano(piai).
 What can we say about Pisano(pa) for a prime p? Wall
conjectured in 1960 (see references) that
Pisano(pa) = pa–1P(p) for all primes p. 
This still seems to be unproven.
If it is true, it means that we can find Pisano(n) for all n
once we know Pisano(p) for all primes p that are (prime)
factors of n. (see A060305)

Here is a table of the Pisano periods for the first 15 primes:

1 1 1 1 2 2 3 3 4 4 4 5 5 6 6 7 7 7 8 8 9
p 23 5 7 ...
1 3 7 9 3 9 1 7 1 3 7 3 9 1 7 1 3 9 3 9 7
1 1 1 1 1
Pisan 2 1 1 2 3 1 4 1 3 7 4 8 3 5 6 7 7 4 A060
38 0 3 4 6 9
o(p) 0 6 0 8 6 8 8 4 0 6 0 8 2 8 0 0 8 4 305
8 6 8 8 6

Is there a formula for the cycle lengths of the Fibonacci

Numbers?
Not quite! It seems to depend on the factorization of the
divisor and the following article is an excellent summary:

  Notes 88.52: Some Properties of finite Fibonacci

Sequences D Vella, A Vella Mathematical Gazette 88
(2004) pages 494-499.
  Dominic Vella's Mathematics page. Dominic and Alfred
Vallas continue to do research on the Fibonacci numbers
mod n and generalised Fibonacci numbers mod n.
  Marc Renault has a list of the Pisano periods for 2 up
to 2002 and his Master's Thesis on Properties of the
Fibonacci Sequence Under Various Moduliis available on
his website too. He also has a useful summary of his results
and A formula for cycle length for almost all moduli.
  That the remainders of the Fibonacci numbers when
divided by a certain number is a cycle seems to have been
known even to the French mathematician (though he was
born in Italy in Turin) Joseph Louis Lagrange (1736-1813)
as early as 1774:
Oeuvres de LaGrange, published in Paris in 1877, pages
5-182.
 However, the numbers were not then called the Fibonacci
Numbers and their periods were not called Pisano periods!
  Fibonacci Series Modulo m D D Wall, The American
Mathematical Monthly, Vol. 67, No. 6 (Jun. - Jul., 1960),
pages 525-532.

There are many interesting relationships in the Pisano

Periods sequence (the series of cycle lengths for modulus 2
upwards). Here is a table of the cycle lengths (the Pisano
periods) for some smaller moduli: 
Add the row label to the column label to find N and the
entry for that row and column is the Pisano period for
modulus N:

6.4 Pisano Periods for moduli 2 - 299

1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2
1 2 3 4 5 6 7 8 9
+0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1
1 3 1 2 1 1 3 1 4 2 6 2 1 1 1 6 2 2 1 4 3 2 4
6 6 6 6 6 5
0. 2 0 2 4 2 2 0 2 2 4 0 4 8 2 8 0 4 4 2 2 6 4 2
0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0
2 1 1 1 1 1 1 2 2 2 1 2 3
1 1 3 4 7 6 7 5 3 5 4 7 9 4 8 5
1. 1 1 5 1 3 9 3 5 4 5 6 7 9
0 6 0 0 2 0 0 0 2 0 8 2 0 2 0 6
6 2 2 0 0 0 6 2 0 0 8 0 2
1 1 2 2 2 3 1 1 4 3 3 4
2 3 4 4 8 3 2 4 7 4 6 3 9 8 4 7 9
23 2 2 1 1 6 3 5 0 5 3 9 4
4 0 8 8 4 0 4 8 2 8 0 6 6 4 8 2 6
0 0 0 6 4 6 0 8 6 0 0 4
1 1 1 1 2 1 1 3 3 1 3 1 2 4 6 2 1 1 5 5
2 4 4 8 4 7 4 7 5
38 0 4 6 2 0 4 4 2 4 2 8 1 8 4 4 4 7 1 6 8
8 8 0 8 8 6 0 2 2
8 8 8 0 8 4 0 8 8 0 8 2 0 8 8 0 6 2 8 8
2 4 2 1 1 5 1 7 1 2 2 3
4 2 3 3 7 9 4 9 8 7 3 2 4 7 7 4 6
46 2 0 4 2 6 8 6 6 2 7 1 3
8 4 6 0 2 6 8 6 4 2 0 4 8 2 2 8 0
8 8 0 0 8 8 8 8 0 6 0 6
1 1 1 2 1 1 2 5 3 1 4 3 2 4 6 1 5 3 5 1 3 5
24 8 2 8 6 4 4
5 0 2 4 0 8 8 4 0 6 4 0 8 8 4 0 6 6 6 4 0 6 8
00 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 1 4 1 1 1 1 3 6 2 1 1 3 1 4 2
22 8 2 4 4 1 4 4 4 3 7 4
6 2 6 0 4 6 6 2 2 3 2 2 7 2 8 4 2 2
44 4 4 8 8 8 8 2 8 6 2 8
0 4 8 4 8 8 0 0 6 4 8 4 0 4 4 0 8
 1 1 1 2 2 1 3 3 2 1 3 2 4 3 2 5 5 3
13 7 7 3 7 8 5 7 4 8 8
7 3 9 6 5 7 1 1 3 3 8 9 4 5 1 5 1 5 6
66 2 6 2 2 0 6 2 8 8 0
6 6 8 6 6 2 6 6 2 0 6 0 6 2 2 6 6 0
1 3 1 1 2 1 1 1 1 1 2 4 1 4
12 4 1 2 4 3 6 7 4 7 4 9 7 6 4
8 6 3 7 9 2 3 2 6 0 4 6 0 3 4
24 8 8 4 2 6 0 2 8 8 8 6 2 0 8
8 6 4 2 8 2 0 8 8 4 4 8 8 4
1 1 1 1 1 2 3 1 1 2 1 2 1 3 2 1 6 3
21 1 5 5 4 7 4 8 4 2 9
9 1 2 0 4 4 1 6 7 4 9 1 3 6 0 6 2 1 3
48 4 6 8 8 8 4 8 6 2 0
2 0 8 4 8 6 4 8 4 6 4 8 8 4 8 0 2 6

6.5 The relationship between the Pisano Period mod n

and FEP(n)

If the initial digits of the Fibonacci series form a cycle of

length 60 (the Pisano period of 10) then Fib(60) is the same
as Fib(0), which is 0. So Fib(60) has the same remainder
mod 10, namely 0, so 10 divides exactly into Fib(60).
The same is true for all Pisano periods mod n: if the Pisano
period mod n is P then Fib(P) has n as a factor.
However, Pisano(n), the Pisano period mod n, may not be
the first Fibonacci number which has n as a factor: for
example
the Fibonacci numbers mod 3 have a cycle of length 8, so
that Fib(8)=Fib(0) mod 3, and in general Fib(n)=Fib(n+8)
mod 3:
i 0 1 2 3 4 5 6 7 8 9 ...
Fib(i) 0 1 1 2 3 5 8 13 21 34 ...
Fib(i) mod 3 0 1 1 2 0 2 2 1 0 1 ...
For 3, there are two 0s in each Pisano cycle of length 8.

Earlier on this page we looked at where a given number first

appears as a factor of a Fibonacci number: the Fibonacci
Entry Point for that number or FEP(n).
So the Pisano period Pisano(n) for n may be the index
number of the first Fibonacci number to have n as a factor --
or it may be some multiple of it.
In fact, it can be proved that the Pisano period Pisano(n) is
either

 equal to the Fibonacci entry point: Pisano(n)=FEP(n) or

 Pisano(n) is twice FEP(n) or
 Pisano(n) is four times FEP(n)

FEP(n) versus Pisano(n)

n 2 3 4 5 6 7 8 9 10 11 12 13 ...
Pisano(n) 3 8 6 20 24 16 12 24 60 10 24 28 ...
FEP(n) 3 4 6 5 12 8 6 12 15 10 12 7 ...
Pisano(n)
1 2 1 4 2 2 2 2 4 1 2 4 ...
FEP(n)
Since F(n) is a factor of F(kn) for all k, then the final row
here tells us how many zeroes there are in the Pisano cycle
mod n. See A001176.
If n itself is a Fibonacci number bigger than 2, as with 5, 8
and 13 in the table here, then this quotient is alternately 2
and 4, that is
Pisano(Fib(2n))=2 and Pisano(Fib(2n+1))=4
with our usual system of indexing Fibonacci which begins
Fib(0)=0 and Fib(1)=1. And here are some investigations to
get you started discovering some of the Pisano period's
fascinating properties:-
6.5.1  You do the maths...
1. What is special about the cycle lengths of moduli 2, 4, 8, 16,
32, 64, ...?
2. Does the same thing happen with the powers of 3: 3, 9, 27,
81, ...?
3. Take pairs of prime numbers such as 3 and 5 or 3 and 13 etc...
Find the Pisano period of each in the pair. How is it related to
the Pisano period of the product of your two primes?
4. Take any two numbers A and B where A is a factor of B.
1. What are the Pisano periods of A and B?
2. What is the Pisano period of their product AB?
3. Is the Pisano period of A a factor of the Pisano period of
B?
5. Look at the complete cycle for any modulus N. It always starts
with 0, 1,... . Here is the complete cycle for 3:
mod 3: 0 1 1 2 0 2 2 1 - it has two zeros.
For 4 : 0 1 1 2 3 1 we have just one zero at the start
and for 5: 0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 - we
have four zeros.
Find a modulus N with some other number of zeros in its cycle.
  The Relation of the Period Modulo m to the Rank
of Apparition of m in the Fibonacci Sequence John
Vinson, Fibonacci Quarterly, vol 1 (1963), pages 37-45.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More.. 

7 Benford's Law and initial digits

[With thanks to Robert Matthews of The Sunday Telegraph for suggesting this
topic.]

Having looked at the end digits of Fibonacci numbers, we

might ask
Are there any patterns in the  initial digits  of Fibonacci
numbers?
What are the chances of a Fibonacci number beginning with
"1", say? or "5"? We might be forgiven for thinking that they
probably are all the same - each digit is equally likely to
start a randomly chosen Fibonacci number. You only need to
look at the Table of the First 100 Fibonacci numbers or
use Fibonacci Calculatorto see that this is not so. Fibonacci
numbers seem far more likely to start with "1" than any
other number. The next most popular digit is "2" and "9" is
the least probable!

This law is called Benford's Law and appears in many

tables of statistics. Other examples are a table of
populations of countries, or lengths of rivers. About one-
third of countries have a population size which begins with
the digit "1" and very few have a population size beginning
with "9".

Here is a table of the initial digits as produced by

the Fibonacci Calculator:

Initial digit frequencies of fib(i) for i from 1 to 100:

Digit: 1 2 3 4 5 6 7 8 9
Frequency: 30 18 13 9 8 6 5 7 4 100 values
Percent: 30 18 13 9 8 6 5 7 4
What are the frequencies for the first 1000 Fibonacci
numbers or the first 10,000? Are they settling down to fixed
values (percentages)? Use the Fibonacci Calculator to collect
the statistics. According to Benford's Law, large numbers of
items lead to the following statistics for starting figures for
the Fibonacci numbers as well as some natural phenomena
Digit:  1  2  3  4  5  6  7  8  9
Percentage: 30 18 13 10  8  7  6  5  5

7.1  You do the maths...

1. Look at a table of sizes of countries. How many countries areas
begin with "1"? "2"? etc..
2. Use a table of population sizes (perhaps of cities in your
country or of countries in the world). It doesn't matter if the
figures are not the latest ones. Does Benford's Law apply to
their initial digits?
3. Look at a table of sizes of lakes and find the frequencies of
their initial digits.
4. Using the Fibonacci Calculator make a table of the first digits of
powers of 2. Do they follow Benford's Law? What about powers
of other numbers?
5. Some newspapers give lists of the prices of various stocks and
shares, called "quotations". Select a hundred or so of the
quotations (or try the first hundred on the page) and make a
table of the distribution of the leading digits of the prices. Does
it follow Benford's Law?
6. What other sets of statistics can you find which do show
Benford's Law? What about the number of the house where the
people in your class live? What about the initial digit of their
home telephone number?
7. Generate some random numbers of your own and look at the
leading digits.
You can buy 10-sided dice (bi-pyramids) or else you can cut
out a decagon (a 10-sided polygon with all sides the same
length) from card and label the sides from 0 to 9. Put a small
stick through the centre (a used matchstick or a cocktail stick or
a small pencil or a ball-point pen) so that it can spin easily and
falls on one of the sides at random. (See the footnote
about dice and spinners on the "The Golden Geometry of the
Solid Section or Phi in 3 dimensions" page, for picture and
more details.)
Are all digits equally likely or does this device show Benford's
Law?
8. Use the random number generator on your calculator and
make a table of leading-digit frequencies. Such functions will
often generate a "random" number between 0 and 1, although
some calculators generate a random value from 0 to the
maximum size of number on the calculator. Or you can use the
 random number generator in the Fibonacci Calculator to both
generate the values and count the initial digit frequencies, if
you like.
Do the frequencies of leading digits of random values conform
to Benford's Law?
9. Measure the height of everyone in your class to the nearest
centimetre. Plot a graph of their heights. Are all heights equally
likely? Do their initial digits conform to Benford's Law? Suppose
you did this for everyone in your school. Would you expect the
same distribution of heights?
10. What about repeatedly tossing five coins all at once and
counting the number of heads each time?
What if you did this for 10 coins, or 20?
What is the name of this distribution (the shape of the
frequency graph)?

7.2 When does Benford's Law apply?

Random numbers are equally likely to begin with each of the

digits 0 to 9. This applies to randomly chosen real numbers
or randomly chosen integers.
Randomly chosen real numbers
If you stick a pin at random on a ruler which is 10cm long and
it will fall in each of the 10 sections 0cm-1cm, 1cm-2cm, etc.
with the same probability. Also, if you look at the initial
digits of the points chosen (so that the initial digit of
0.02cm is 2 even though the point is in the 0-1cm section) then
each of the 9 values from 1 to 9 is as likely as any other
value.
Randomly chosen integers
This also applies if we choose random integers. 
Take a pack of playing cards and remove the jokers, tens, jacks
and queens, leaving in all aces up to 9 and the kings. Each
card will represent a different digit, with a king representing
zero. Shuffle the pack and put the first 4 cards in a row to
represent a 4 digit integer. Suppose we have King, Five, King,
Nine. This will represent "0509" or the integer 509 whose first
digit is 5. The integer is as likely to begin with 0 (a king)
as 1 (an ace) or 2 or any other digit up to 9.
But if our "integer" began with a king (0), then we look at the
next "digit". 
These have the same distribution as if we had chosen to put
down just 3 cards in a row instead of 4. The first digits all
have the same probability again. If our first two cards had
been 0, then we look at the third digit, and the same applies
again.
So if we ignore the integer 0, any randomly chosen (4 digit)
integer begins with 1 to 9 with equal probability. (This is not
 quite true of a row of 5 or more cards if we use an ordinary
pack of cards - why?)
So the question is, why does this all-digits-equally-
likely property not apply to the first digits of each of the
following:

 the Fibonacci numbers,

 the Lucas numbers,
 populations of countries or towns
 sizes of lakes
 prices of shares on the Stock Exchange

Whether we measure the size of a country or a lake in

square kilometres or square miles (or square anything),
does not matter - Benford's Law will still apply. 
So when is a number random? We often meant that we
cannot predict the next value. If we toss a coin, we can
never predict if it will be Heads or Tails if we give it a
reasonably high flip in the air. Similarly, with throwing a dice
- "1" is as likely as "6". Physical methods such as tossing
coins or throwing dice or picking numbered balls from a
rotating drum as in Lottery games are always unpredictable.

The answer is that the Fibonacci and Lucas Numbers are

governed by a Power Law.
We have seen that Fib(i) is round(Phii/ 5) and Lucas(i) is
round(Phii). Dividing by sqrt(5) will merely adjust the scale -
which does not matter. Similarly, rounding will not affect the
overall distribution of the digits in a large sample.

Basically, Fibonacci and Lucas numbers are powers of Phi.

Many natural statistics are also governed by a power law -
the values are related to Bi for some base value B. Such
data would seem to include the sizes of lakes and
populations of towns as well as non-natural data such as the
collection of prices of stocks and shares at any one time. In
terms of natural phenomena (like lake sizes or heights of
mountains) the larger values are rare and smaller sizes are
more common. So there are very few large lakes, quite a
few medium sized lakes and very many little lakes. We can
see this with the Fibonacci numbers too: there are 11
Fibonacci numbers in the range 1-100, but only one in the
next 3 ranges of 100 (101-200, 201-300, 301-400) and
 they get increasingly rarer for large ranges of size 100. The
same is true for any other size of range (1000 or 1000000
or whatever).

7.2.1  You do the maths...

1. Type a power expression in the Eval(i)= box, such
as pow(1.2,i) and give a range of i values from i=1 to i=100.
Clicking the Initial digits button will print the leading digit
distribution. 
Change 1.2 to any other value. Does Benford's Law apply
here?
2. Using Eval(i)=randint(1,100000) with an i range from 1 to 1000
(so that 1000 separate random integers are generated in the
range 1 to 100000) shows that the leading digits are all equally
likely.

  Benford's Law for Fibonacci and Lucas Numbers,

L. C. Washington, The Fibonacci Quarterly vol. 19, 1981,
pages 175-177.
 The original reference: The Law of Anomalous
Numbers F Benford, (1938) Proceedings of the American
Philosophical Society vol 78, pages 551-572.
  The Math Forum's archives of the History of
Mathematics discussion group have an email from Ralph A.
Raimi (July 2000) about his research into Benford's Law. It
seems that Simon Newcomb had written about it much
earlier, in 1881, in American Journal of
Mathematics volume 4, pages 39-40. The
name Benford is, however, the one that is commonly used
today for this law.
  MathTrek by Ivars Peterson (author of The
Mathematical Tourist and Islands of Truth) the editor of
Science News Online has produced this very good, short and
readable introduction to Benford's Law.
  M Schroeder Fractals, Chaos and Power Laws,
Freeman, 1991, ISBN 0-7167-2357-3. This is an interesting
book but some of the mathematics is at first year university
level (mathematics or physics degrees), unfortunately, and
the rest will need sixth form or college level mathematics
beyond age 16. However, it is still good to browse through.
It has only a passing reference to Benford's Law: The
Peculiar Distribution of the Leading Digit on page 116.
 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More.. 

8 Every number starts some Fibonacci

Number
We found that every number is a factor of some Fibonacci
number above but it is also true that we can always find a
Fibonacci number that begins with a given number as its
initial digits.
The first few Fibonacci numbers are 0,1,1,2,3,5,8. We have
to go up to Fib(19)=4181 to find one beginning with 4 and
Fib(15)=641 for 6. The index numbers (ranks) of the
Fibonacci numbers that begin with 1 up to 20 are:
Fibonaccis starting with the number n
1 1
n 123 4 5 6 7 8 9 10 11 12 15 16 17 18 19 20
3 4
Fib(i
)
6 9 1
start 41 750 109 113490 121 1 15 16558 177 183631 196 2036501
123 5 1 88 4
ing 81 25 46 3170 393 3 97 0141 11 1903 418 1074
0 7 4
with
n
rank 1 1 1
13419 5 25 6 21 45 26 7 17 41 22 46 27 51
i 5 6 2
Ross Honsberger (see the references at the end of this
section) gives the proof that we can always find a power of
2 starting with any given number and, in fact, this works for
any other base number as well as 2. The problem goes back
to a Hungarian Mathematical competition problem of 1928
(see references).

On another page we look at the Lucas numbers Lucas(n) =

Fib(n-1) + Fib(n+1) and find that Lucas(i) is Round(Phii) so
the initial-digits-of-powers applies to the Lucas
numbers also.

Lucas numbers starting with the number n

1 1
n 1234 5 6 78 9 10 12 13 14 15 16 17 19 20
1 8
Lucas 123452 640 784 93 1036 1 12 13 141422 151 1677 17393796 1 19 20633
(i) 1 79 3 49 82 1 3 64 324 27 61 001 8 9 239
start
ing
with
 n
rank
102313 23 414 19 24 5 10 15 39 20 25 49 6 11 35
i

  Ingenuity in Mathematics Ross Honsberger,

(Mathematical Association of America), 1975, Essay Six; A
Property of an pages 38-45
  Challenging Mathematical Problems with Elementary
Solutions, Vol 1 A M Yaglon and I M Yaglom, (Dover
paperback edition 1987 of the 1964 original). 
There is also a second volume:
  Challenging Mathematical Problems with Elementary
Solutions, Vol 2 A M Yaglon and I M Yaglom, (Dover
paperback edition 1987 of the 1967 original)
  The original problem and its solution appear in
Hungarian Problem Book II: Based on the Eötvös
Competitions 1906-1928 J Kurschak (compiler) and E
Rapaport (translator), Mathematical Association of America
(1963)

8.1 Is there a Fibonacci number that ends with any

given number?

It seems we can start off, with the aid of a Calculator, and

find Fibonacci numbers ending with all values from 1 to 99.
The list starts...
1 1
n 1 2 3 4 5 6 7 8 9 0 11 12 3 14 15 16 17 18 19 20
61922
04516
66590 57602
Fib 13522 65903 13223
(i) 86753 704 46 54247 1140
end 87863 92524 21587 55886 59301
ing 10 3 6 17 29787 76708 63004 20619 02594 154
wit 3 94 7 8 1 71 42693 1 91258 19824 86853 2415 196 39705 80087
h n 1 2 3 4 5 6 7 8 9 0 1 96512 3 14114 98215 65216 7817 418 52219 55920
ran 1 1 1
k i 1 3 4 9 5 21 4 6 1 5 22 216 7 111 130 168 37 27 112 60
The list of ranks of these Fibonaccis-ending-with-n (their
Fibonacci index numbers) is 1, 3, 4, 9, 5, 21,
14, ... A023183
Jason Earls comments that there seem to be none that end
with 100, 102, 108, 110, 116, 118, ... or in fact any number
beyond 99 that has a remainder of 4 or 6 when divided by
8.
Can you prove he is right? 

9 The Fibonacci Numbers in Pascal's

Triangle
0 1 2 3 4 ...
1 0 1
1 1 1 1 1
1 2 1 2 1 2 1
1 3 3 1 3 1 3 3 1
1 4 6 4 1 4 1 4 6 4 1
... ... ...
Each entry in the triangle on the left is the sum of the two
numbers above it. 
If we re-align the table to look the one on the right then
each number is the sum of the one above it and the one to
the left of that one where a blank space can be taken as "0".
Note that each row starts and ends with "1".

Pascal's Triangle has lots of uses including

 Calculating probabilities. 
If you throw n coins
randomly onto a table then
the chance of getting H heads
among them is the entry in
row N, col H divided by 2n: 
for instance, for 3 coins, n=3
so we use row 3:
3 heads: H=3 is found
in 1 way (HHH)
2 heads: H=2 can be got
in 3 ways (HHT, HTH and
THH)
1 head: H=1 is also found
in 3 possible ways (HTT,
THT, TTH)
 0 heads: H=0 (i.e. all Tails) is
also possible in just 1 way:
TTT

 Finding terms in a Binomial expansion: (a+b)n

EG. (a+b)3 = 1a3 + 3a2b + 3ab2 + 1b3

Can we find the Fibonacci Numbers in Pascal's Triangle? Yes!

The answer lies in the diagonals in the triangle:
1
1 1 1
1 1 2 1
2 1 3 3 1
3 1 4 6 4 1
1
5 1 5 10 5 1
0
2
8 1 6 15 15 6 1
0
3
13 1 7 21 35 21 7 1
5
21 ...

9.1 Why do the Diagonals sum to Fibonacci numbers?

It is easy to see that the diagonal sums really are the

Fibonacci numbers if we remember that each number in
Pascal's triangle is the sum of two numbers in the row above
it (blank spaces count as zero), so that 6 here is the sum of
the two 3's on the row above.

The numbers in any diagonal row are therefore formed from

adding numbers in the previous two diagonal rows as we
see here where all the blank spaces are zeroes and where
we have introduced an extra column of zeros which we will
use later:

1 The green diagonal sums to 5;
the blue diagonal sums to 8;
1 1
the red diagonal sums to 13
1 2 1
1 3 3 1 Each red number is the sum of a blue and a green number
on the row above.
1 4 6 4 1
1
1 5 10 5 1
0
1
1 6 20 15 6 1
5

Notice that the GREEN numbers are on one diagonal and

the BLUE ones on the next. The sum of all the green
numbers is 5 and all the blue numbers add up to 8.
Because all the numbers in Pascal's Triangle are made the
same way - by adding the two numbers above and to the
left  on the row above, then we can see that each red
number is just the sum of a green number and a blue
number and we use up all the blue and green numbers to
make all the red ones.
The sum of all the red numbers is therefore the same as the
sum of all the blues and all the greens: 5+8=13! 
The general principle that we have just illustrated is:

The sum of the numbers on

one diagonal is the sum of
the numbers on the previous
two diagonals.

If we let D(i) stand for the sum of the numbers on the

Diagonal that starts with one of the extra zeros at the
beginning of row i, then

D(0)=0 and D(1)=1

are the two initial diagonals shown in the table above. The
green diagonal sum is D(5)=5 (since its extra initial zero is
in row 5) and the blue diagonal sum is D(6) which is 8. Our
red diagonal is D(7) = 13 = D(6)+D(5).
We also have shown that this is always true: one diagonals
sum id the sum of the previous two diagonal sums, or, in
terms of our D series of numbers:
D(i) = D(i-1) + D(i-2)
But...
D(0) = 1
D(1) = 1
D(i) = D(i-1) + D(i-2)
is exactly the definition of the Fibonacci numbers! So D(i) is
just F(i) and
the sums of the diagonals in Pascal's Triangle are the
Fibonacci numbers!

9.2 Another arrangement of Pascal's Triangle

By drawing Pascal's Triangle with all the rows moved over

by 1 place, we have a clearer arrangement which shows the
Fibonacci numbers as sums of columns:
1  2  3  4  5  6  7  8  9  10
1 . . . . . . . . .
. 1 1 . . . . . . .
. . 1 2 1 . . . . .
. . . 1 3 3 1 . . .
. . . . 1 4 6 4 1 .
. . . . . 1 5 10 10 5
. . . . . . 1 6 15 20
. . . . . . . 1 7 21
. . . . . . . . 1 8
. . . . . . . . . 1
1 1 2 3 5 8 13 21 34 55
This table can be explained by referring to one of
the (Easier) Fibonacci Puzzles - the one about Fibonacci for
a Change. It asks how many ways you can pay n pence (in
the UK) using only 1 pence and 2 pence coins. The order of
the coins matters, so that 1p+2p will pay for a 3p item and
2p+1p is counted as a different answer. [We now have a
new two pound coin that is increasing in circulation too!]
Here are the answers for paying up to 5p using only 1p and
2p coins:
1p 2p 3p 4p 5p
1p 2p  1p+2p 2p+2p  1p+2p+2p
1p+1p 2p+1p  1p+1p+2p 2p+1p+2p
1p+1p+1p 1p+2p+1p 2p+2p+1p 
2p+1p+1p 1p+1p+1p+2p
1p+1p+1p+1p 1p+1p+2p+1p
1p+2p+1p+1p
2p+1p+1p+1p
1p+1p+1p+1p+1p
1 way 2 ways 3 ways 5 ways 8 ways
Let's look at this another way - arranging our answers
according to the number of 1p and 2p coins we use.
Columns will represent all the ways of paying the amount at
the head of the column, as before, but now the rows
represent the number of coins in the solutions:
1
cost: 2p 3p 4p 5p
p
1 coin: 1p 2p      
2 1p+1p 1p+2p 2p+2p
   
coins: 2p+1p
1p+1p+1p 1p+1p+2p 1p+2p+2p
3
    1p+2p+1p 2p+1p+2p
coins:
2p+1p+1p 2p+2p+1p
1p+1p+1p+1p 2p+1p+1p+1p
4 1p+1p+1p+2p
     
coins: 1p+1p+2p+1p
1p+2p+1p+1p
5 1p+1p+1p+1p+1p
       
coins:
If you count the number of solutions in each box, it will be
exactly the form of Pascal's triangle that we showed above!
The
mathematics
is in this
formula:
where the big
brackets with
two numbers n–k–
n–1 n n–k
vertically 1 Or, an
inside them Fib(n)
are a special
mathematical
= k=0 ( k ) equivalen Fib(n)
t formula
is:
= k=1 ( )
k–1

notation for
the entry in
Pascal's
triangle
on row n-k-
1 and
column k

9.3 Fibonacci's Rabbit Generations and Pascal's

Triangle
Here's another explanation of how the Pascal triangle
numbers sum to give the Fibonacci numbers, this time
explained in terms of our original rabbit problem.

Let's return to Fibonacci's rabbit problem and look at it

another way. We shall be returning to it several more times
yet in these pages - and each time we will discover
something different!

We shall make a family

tree of the rabbits but this time we shall be interested only
in the females and ignore any males in the population. If
you like, in the diagram of the rabbit pairs shown here,
assume that the rabbit on the left of each pair is male (say)
and so the other is female. Now ignore the rabbit on the left
in each pair!
We will assume that each mating produces exactly one
female and perhaps some males too but we only show the
females in the diagram on the left. Also in the diagram on
the left we see that each individual rabbit appears several
times. For instance, the original brown female was mated
with a while male and, since they never die, they both
appear once on every line.
Now, in our new family tree diagram, each female rabbit
will appear only once. As more rabbits are born, so the
Family tree grows adding a new entry for each newly born
female. 
As in an ordinary human family tree, we shall show parents
above a line of all their children. 
Here is a fictitious human family tree with the names of the
relatives shown for a person marked as ME:
 The diagram shows that:

 Grandpa Abel and Grandma Mabel are the parents of

my Dad;
 Grandma Freda and Grandpa Fred are the parents of
my Mum.
 Bob is my Dad's brother
 my Mum has two sisters, my aunts Hayley and Jane.
 Aunt Hayley became Hayley Weather when she
married Clement Weather.
 They have two children, my cousins Sonny Weather
and Gale Weather.
 Gale married Gustof Wind and so is now Gale Wind.
 My brother John and his wife Joan have two children,
my nephew Dan and my niece Pam.

In this family tree of human relationships, the = joins

people who are parents or signifies a marriage.
In our rabbit's family tree, rabbits don't marry of course, so
we just have the vertical and horizontal lines:

The vertical line |

points from a mother (above) to the oldest daughter (below);
the horizontal line -
is drawn between sisters from the oldest on the left down to
the youngest on the right;
the small letter r
represents a young female ( a little rabbit) and
the large letter R
shows a mature female (a big Rabbit) who can and does mate
every month, producing one new daughter each time.

As in Fibonacci's original problem (in its variant form that

makes it a bit more realistic) we assume none die and that
each month every mature female rabbit Ralways produces
exactly one female rabbit r (we ignore males) each month. 
So each month:
 each r will change to R (each matures after one
month)
 each R produces a new baby rabbit and so adds
another r at the end of the line below which are its direct
descendants or children), that is produce a new baby rabbit
each month

Here is the Rabbit Family tree as if grows month by month

for the first 9 months and 5 generations:

KEY |:mother above with (first) daughter

below __:joins sisters
R:mother (produces a new female each
month) r:new female
Month:          

1 r
^Initially there is one immature rabbit
(generation 1)

 a language
 API security
 Istio
 AutoRABIT

Join the conversation

 1 comment

窗体顶端

窗体底端