The Mathematics of the Fibonacci series

Take a look at the Fibonacci Numbers List or, better, open another window in your Browser, then you can refer to this page and the list together.

Contents

The i m line means there is a Things to do investigation at the end of the section.

• Patterns in the Fibonacci Numbers o Cycles in the Fibonacci numbers

• Factors of Fibonacci Numbers i m o Fibonacci Primes o A Prime Curio

• Benford's Law and Initial Digits o When does Benford's Law apply?

• The Fibonacci Numbers in Pascal's Triangle i m o Why do the Diagonals sum to Fibonacci numbers? o Another arrangement of Pascal's Triangle o Fibonacci's Rabbit Generations and Pascal's Triangle

• The Fibonacci Series as a Decimal Fraction i m

• A Fibonacci Number Trick

• Another number pattern HEW

• Fibonacci Numbers and Pythagorean Triangles o Using the Fibonacci Numbers to make Pythagorean Triangles

• Maths from the Fibonacci Spiral diagram

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 . .More. . ||1;f;1f°sJ

Patterns in the Fibonacci Numbers

Cycles in the Fibonacci numbers

Here are some patterns people have already noticed:

• There is a cycle in the units column - the cycle of units digits (0,1,1,2,3,5,8,13,21,34,55,...) repeats from n=60 and again every 60 values.

• There is also a cycle in the last two digits, repeating (00, 01, 01, 02, 03, 05, 08, 13, ...) from n=300 with a cycle of length 300.

• 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

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

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 100 Fibonacci numbers and their factors. It will be helpful in the following investigations:

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?

The above investigations should help you to understand 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=1,2,...

This means that if the subscript is composite (not a prime) then so is that Fibonacci number (with one exception - can you find it?) So we now deduce that

Any prime Fibonacci number must have a subscript which is prime

(with one little exception - can you find it? Hint: you won't have to search far for it ©.)

^^ 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) divides exactly into F(nk): using the Binet Formula; by mathematical induction and using generating functions.

Fibonacci Primes

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:

i

3

4

5

7

11

13

17

23

29

43

47

83

131

137

359

431

433

449

Fib(i)

2

3

5

13

89

233

1597

28657

514229

433494437

digits

digits

digits

digits

digits

digits

digits

digits

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.

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.

Two Prime Curios

G. L. Honaker Jr. pointed me to two curious oddities about the Fibonacci numbers and prime number. a Prime Curio that the number of primes less than 144, which is a Fibonacci number, is 34, another 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 tt(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 tt(8)=4 (there are 4 primes between 1 and 8, namely 2, 3, 5 and 7) and tt(1 1)=5. There are some smaller values, too:

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.

There is a nice Primes Calculator at Princeton University's web site.

^^ 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 factorising 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.

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

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 Calculator to 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

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)?

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,

• populations of countries or towns

• 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 (PhiVV5) and Lucas(i) is round (Phi1). 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).

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

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 ofthe Leading Digit on page 116.

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

The Fibonacci Numbers in Pascal's Triangle

col : 0 1 2 3 4 ...

----+ -

1

0 |

1

1 1

r

1 I

1

1

each number

1 2 1

o

2 |

1

2

1

is the sum of

1 3 3 1

w

3 |

1

3

3

1

the one above it and

1 4 6 4 1

4 |

1

4

6

4 1

the one to the above

eg 6 is 3+3 from row above.

eg 6 is 3+3 from row above.

Each entry in the triangle on the left is the sum of the two numbers either side of it but in the row above. A blank space can be taken as "0" so 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 1way (HHH) 2 heads: H=2 can be got in 3ways (HHT, HTH and THH) 1 head: H=1 is also found in 3possible ways (HTT, THT, TTH) 0 heads: H=0 (ie all Tails) is also possible in just 1way: TTT

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

Can you find the Fibonacci Numbers in Pascal's Triangle?

Or, an equivalent formula is:

If that still doesn't help, then this animated diagram might:

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:

Hints

The answer is in the formula on the right: where the big brackets with two numbers vertically inside them are a special mathematical notation for the entry in Pascal's triangle on row n-k-1 and column k

each number is the sum of the one above it and

the one to the above-left.

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:

col : 0 1 2 3 4

----+ -

1

0

1

<--

the first two diagonal sums

/ /

0 |

0

1

/

r

1 |

0

1

1

5 =

sum of green numbers

8=sum of blue numbers

o

2 |

0

1

2

1

13=sum of red numbers

\

|

w

3 |

0

1

3

3

1

\

|

4 |

0

1

4

6

4

1

\

|

5 |

0

1

5

10

10

5 1

\

|

6 |

0

1

6

15

20

15 6 1

7 |

0

#

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

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:

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!

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:

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

1p+1p

1p+2p 2p+1p 1p+1p+1p

2p+2p 1p+1p+2p 1p+2p+1p 2p+1p+1p 1p+1p+1p+1p

1p+2p+2p 2p+1p+2p 2p+2p+1p 1p+1p+1p+2p 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:

cost:

1p

2p

3p

4p

5p

1 coin:

1p

2p

2 coins:

1p+1p

1p+2p 2p+1p

2p+2p

3 coins:

1p+1p+1p

1p+1p+2p 1p+2p+1p 2p+1p+1p

1p+2p+2p 2p+1p+2p 2p+2p+1p

4 coins:

1p+1p+1p+1p

2p+1p+1p+1p 1p+1p+1p+2p 1p+1p+2p+1p 1p+2p+1p+1p

5p:

1p+1p+1p+1p+1p

If you count the number of solutions in each box, it will be exactly the form of Pascal's triangle that we showed above!

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:

Grandpa Grandma Grandma Grandpa Abel===Mabel Freda=====Fred

sister-in-law |brother sister Joan= ==John---ME---Jean

nephew Dan--niece Pam The diagram shows that:

Grandpa Abel and Grandma Mabel are the parents of my Dad and Grandma Freda and Grandpa Fred are the parents of my Mum. Bob is my Dad's brother and 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:

Aunt Uncle -Hayley=Clement

Cousin--Cousin

Sonny Gale===Gustof

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 always produces a babies of which exactly one is a female. Here is the Rabbit Family tree as if grows month by month for the first 8 months:

M o

n

t h

1

2

3

4

r

R

R

I

r

Rr r

RRr R

Rr r

So in month 2, our young female (r of month 1) becomes mature (R) and mates.

In month 3, she becomes a parent for the first time and produces her first daughter, shown on a line below - a new generation. In month 4, the female born in month 3 becomes mature (R) and also her mother produces another daughter (r). In month 5, the original female produces another female child added to the end of the line of the generation of her daughters, while the daughter born the previous month (the second in the line) becomes mature. Also the first daughter produces her own first daughter, so in month 5 the original female becomes a grand-mother and we have started a third line - the third generation. The Family tree is shown for the first 8 months as more females are added to it. We can see that our original female becomes a great-grandmother in month 7 when a fourth line is added to the Family tree diagram - a fourth generation!

Have you spotted the Pascal's triangle numbers in the Rabbit's Family Tree?

The numbers of rabbits in each generation, that is, along each level (line) of the tree, are the Pascal's triangle numbers that add up to give each Fibonacci number - the total number of (female) rabbits in the Tree. In month n there are a total of F(n) rabbits, a number made up from the entry in row (n-k) and column (k-1) of Pascal's triangle for each of the levels (generations) k from 1 to n. In other words, we are looking at this formula and explaining it in terms of generations, the original rabbit forming generation 1 and her daughters being generation 2 and so on:

Was this article helpful?

0 0

Post a comment