[an error occurred while processing this directive] [an error occurred while processing this directive]

$QuestionofDay$

Question of the Day

What mathematical identities do you know? Do you know any identities or relationships that are satisfied by special sets of integers, such as the sequence of odd numbers and the sets of square numbers? What is the difference between an identity and a formula?

Key Concepts

The Fibonacci sequence satisfies a number of identities among it members.
The Fibonacci numbers have some remarkable divisibility properties.

Vocabulary

An identity is an equation that is satisfied by any number that replaces the letter for which the equation is defined, that is, the equation is true for all values of the variable.

Mathematical Ideas

Identities about Fibonacci numbers

Cassini’s Identity

This section is adapted from: Concrete Mathematics Second Edition, R. L Graham, D. E. Knuth, O. Patashnik, Addison-Wesley, 1994, pages 290-301.

One of the oldest theorems about Fibonacci numbers is due to the French astronomer Jean-Dominique Cassini in 1680. Cassini also discovered the dark gap between the rings A and B of Saturn, now known as the Cassini division. Cassini deduced that

Fn+1Fn - 1- F 2 = (- 1)n n

Try it with a few of the Fibonacci numbers. For example, $13 .5 - 82 = 1$ .

In some ways this is inconvenient, because it relates Fibonacci numbers which are two indices apart. However, because $Fn+1 = Fn + Fn -1$ , we can write $Fn = Fn+1 - Fn- 1$ . Then substituting into Cassini’s identity, we get

F 2n+1- Fn+1Fn - F2n = (- 1)n.

Try this also with a few of the Fibonacci numbers to test it out. For example, $132 - 13 .8 - 82 = 1$

Divisibility of Fibonacci numbers

In this section, we will do a mathematical experiment in numerical pattern finding and investigation. We will make a conjecture about the pattern and try to prove it with the identities we developed above.

Consider the following table which I constructed so that you could study some Fibonacci relationships easily without having to do large amounts of computation:

n	F_n	“Divisors of F˙n”
1	1	${1}$
2	1	${1}$
3	2	${1, 2}$
4	3	${1, 3}$
5	5	${1, 5}$
6	8	${1,2, 4,8}$
7	13	${1,13}$
8	21	${1,3,7,21}$
9	34	${1,2,17, 34}$
10	55	${1,5,11, 55}$
11	89	${1,89}$
12	144	${1, 2,3,4,6,8,9,12, 16,18,24,36, 48,72,144}$
13	233	${1,233}$
14	377	${1,13,29, 377}$
15	610	${1, 2,5,10,61,122, 305,610}$
16	987	${1, 3,7,21,47,141, 329,987}$
17	1597	${1,1597}$
18	2584	${1, 2,4,8,17,19,34, 38,68,76,136, 152,323,646, 1292,2584}$
19	4181	${1,37,113, 4181}$
20	6765	${1,3,5, 11,15,33,41, 55,123,165,205, 451,615, 1353,2255, 6765}$

The first column is just index numbers. The second column is the Fibonacci number corresponding to that index. The third column is the set of positive integers that divide evenly into the Fibonacci number.

Start with a simple observation that you may notice after examining the table for a while. Among the divisors of $F6 = 8$ is $F3 = 2$ . Among the divisors of $F8 = 21$ is $F4 = 3$ . Among the divisors of $F10 = 55$ is $F5 = 5$ . Among the divisors of $F12 = 144$ is $F6 = 8$ . Are we ready to make a conjecture? We might conjecture that $F n$ evenly divides $F 2n$ . Can we test our conjecture? For instance, $F7 = 13$ certainly divides $F14 = 377$ . And $F8 = 21$ divides $F16 = 987$ . Can you test a few more?

This can be proved in the following way. First observe by definition, and then by a quick substitution:

F = F + F = 1 .F + 1 .F (1) n+2 n+1 n n+1 n Fn+3 = Fn+2 + Fn+1 = 2 .Fn+1 + 1 .Fn (2)

Now use the definition of Fibonacci numbers again, and the previous information, and continue.

Fn+4 = Fn+3 + Fn+2 = 3 .Fn+2 + 2 .Fn (3) Fn+5 = Fn+2 + Fn+1 = 5 .Fn+1 + 3 .Fn (4) Fn+6 = Fn+2 + Fn+1 = 8 .Fn+1 + 5 .Fn (5) Fn+7 = Fn+2 + Fn+1 = 13 .Fn+1 + 8 .Fn (6) F = F + F = 21 .F + 13 .F (7) n+3 n+2 n+1 n+1 n Fn+3 = Fn+2 + Fn+1 = 34 .Fn+1 + 21 .Fn (8) (9)

Notice that from the 3rd line on, each line is the sum of the two previous lines, and so the coefficients are the Fibonacci numbers! Therefore we have proved:

Fn+k = FkFn+1 + Fk -1Fn

(Check this out by substituting a few numbers for $k$ to make sure it matches what you see above.)

Now substitute $k = n$ to get

F2n = FnFn+1 + Fn-1Fn = Fn(Fn+1 + Fn-1).

So $Fn$ does indeed divide $F2n$ , indeed with quotient $(Fn+1 + Fn-1)$ !

This proof can be generalized to show that $Fkn$ is a multiple of $Fn$ , and even that $gcd(Fm, Fn) = Fgcd(m,n)$ .

Binet’s Formula for the Fibonacci numbers

Let $V~ -- P(1 + 5)/2 = 1.618 ...$ be the symbol for the Golden Ratio. Then recall that $P - 1 = 1/P hi = 0.618 ...$ also appears in so many formulas along with the Golden Ratio that we give it a special symbol $V~ -- f = ( 5- 1)/2$ . And finally, we need one more symbol $^P = - 1/f = -( V~ 5-- 1)/2 = (1 - V~ 5)/2 = - 0.618 ...$ .

Then using either solutions of difference equations or generating functions, (both are ideas form more advanced mathematics) we can prove that

1 ( n n) Fn = V~ -- P - ^P 5

Spell that out a little more explicitly:

(( V~ -)n ( V~ -)n) F = V~ 1- 1-+---5 - 1-----5 n 5 2 2

This is an amazing formula, since it does not look like it is even a rational number, let alone an integer. Yet it is! Try out some small values of $n$ to test it, for example, $n = 0$ , $1$ and $2$ .

With the idea that $n |P ^hi |--> 0$ as $n --> oo$ (more precisely $V ~ - ^P/ 5 < 1/2$ , we can make another interesting formula for the Fibonacci numbers:

n Fn = V~ P-rounded to the nearest integer 5

Fibonacci number bases and a cute conversion

You are familiar with number bases, for example base 2 number systems or the base 10 numbers using place notation with powers of 2 or 10 respectively. One can do the same thing with Fibonacci numbers: That is, every natural number is either a Fibonacci number or it is expressible uniquely as the sum of Fibonacci numbers. Here is how to express a number in the Fibonacci number system:

Write down a natural number, say 38.
Find the largest Fibonacci number that does not exceed the given number, in this case, $F9 = 34$ is the largest Fibonacci number that does not exceed 38.
Subtract the Fibonacci number from the given number and look at the new number, in this case, 4
Now find the largest number that does not exceed this new number, for the example, $F4 = 3$ is the largest Fibonacci number not exceeding 4.
Continue this process, in the example we are down to 1, and so stop
$38 = 38 + 4 + 1 = F9 + F4 + F1 = (100001001)F$

Now we can put this number base idea together with the single- $P$ -term Binet formula above to make a cute number trick.

By pure coincidence $P$ is also very nearly the number of kilometers in a mile. (The exact number of kilometers in a mile is $1.609344$ ) This will give a handy way to convert mentally from kilometers to miles or vice-versa.

Suppose we want to convert, say 30 kilometers to its equivalent in miles. Just use the Fibonacci representation $30 = 21 + 8 + 1$ . That is:

8 6 P V~ --- P V~ --- V~ P- 30 ~~ 5 + 5 + 5

Then the number of miles in 30 kilometers would be approximately

7 5 30- ~~ P V~ ---+ P V~ ---+ V~ 1- ~~ F + F + F = 13 + 5 + 1 = 19. P 5 5 5 7 5 0

The actual number of miles in 30 kilometers is $18.64$ , so this is close enough for mental work.

SO the idea is represent the number of kilometers in the Fibonacci number system and then “shift down a notch” and add up again. This is because by the Binet formula, shifting down divides by $P$ , more or less.

Similarly, to go from miles to kilometers, “shift up a notch”. For example, 30 miles $= 21 + 8+$ , so in kilometers, this is $34 + 13 + 2 = 49$ . The actual conversion is $48.28$ kilometers, pretty close.

Problems to Work for Understanding

Solidifying Ideas: pages 57-58: 2,3,6,7,8
New Ideas: page 61: 1,2
Habits of Mind: page 62: number 2

Reading Suggestion:

Concrete Mathematics Second Edition, R. L Graham, D. E. Knuth, O. Patahsnik, Addison-Wesley, 1994, pages 290-301.

[an error occurred while processing this directive] [an error occurred while processing this directive]

Last modified: [an error occurred while processing this directive]