[an error occurred while processing this directive]

Math 896 Section 700
Experimentation, Conjecture and Reasoning
Spring 2005

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

Key Concepts

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

Vocabulary

Vocabulary

  1. 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

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 Fn”
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:

Fn+2 = Fn+1 + Fn = 1 .Fn+1 + 1 .Fn (1) 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.

F = F + F = 3 .F + 2 .F (3) n+4 n+3 n+2 n+2 n 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) Fn+3 = Fn+2 + Fn+1 = 21 .Fn+1 + 13 .Fn (7) 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) = F gcd(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 = 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 V~ -- V~ -- ^P = - 1/f = - ( 5 - 1)/2 = (1 - 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~ 5- P - P

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 |P^n |--> 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:

  1. Write down a natural number, say 38.
  2. 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.
  3. Subtract the Fibonacci number from the given number and look at the new number, in this case, 4
  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.
  5. Continue this process, in the example we are down to 1, and so stop
  6. 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:

P8 P6 P 30 ~~ V~ --+ V~ --+ V~ -- 5 5 5

Then the number of miles in 30 kilometers would be approximately

30 P7 P5 1 --- ~~ V~ --+ V~ --+ V~ -- ~~ F7 + F5 + F0 = 13 + 5 + 1 = 19. P 5 5 5

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 + 1 , so in kilometers, this is 34 + 13 + 2 = 49 . The actual conversion is 48.28 kilometers, pretty close.

Sample Worked Problems

Problem 13, Page 59, Even More Fibonacci Relationships

Compute the first few terms of the new combined sequence to be (for n = 3, 4,..., 10 respectively)

4,7,18,29, 47,76

Now that can be compared to the Lucas sequence: L1 = 2, L2 = 1, L3 = 3, L4 = 4, L5 = 7, L6 = 11, L7 = 18, L8 = 29, L9 = 47, L10 = 76. The coincidence is too similar to be ignored! It certainly appears that Fn+2 -Fn-2 = Ln+1. Let’s try it with an integer larger than we have tried yet: say n = 14. Then we would check to see if F16 - F12 = L15. This translates into 987 - 144 = 843 which is true. It certainly appears as if we have a relationship figured out. We could prove this relationship in several possible ways, including mathematical induction, and Binet’s formula as well as some other ways that are simpler but use concepts introduced in advanced courses (namely the linearity of the recursion formula and superposition of solutions.)

The problem does not call for it, but for another example, here is a proof using mathematical induction: First consider the initial case with n = 3, or the assertion that F5 + F1 = L4. This we demonstrate directly by substituting the values: 5 - 1 = 4. Now assume that we know that Fn+2 - Fn-2 = Ln+1 is true for all values of 3 < n < N and we wish to show that FN+2 - Fn-2 = Ln+1 is true. (Incidentally, this is called the Strong Induction Method, which is an equivalent formulation of the more familiar simple induction method.) We apply the definition of the Fibonacci numbers to the equation whose truth we are trying to establish. We find that if we can establish the truth of

(FN+1 + FN )- (FN -3 + FN -4) = LN + LN -1

then we will be done. But this last equation can be rearranged into

(FN+1 - FN- 3) + (FN - FN -4) + FN- 4 = LN + LN - 1.

Each parenthesized term on the left is equivalent to the corresponding term on the right by the Strong Induction hypothesis. We are done.

Problems 34 and 35, A big fib and Decomposing naturals

The problem statement is “Suppose we have a natural number that is not a Fibonacci number, let’s call it N. Suppose that F is the largest Fibonacci number that does not exceed N. Show that the number N - F must be smaller than the Fibonacci number that comes right before F.

In order to show this, it helps to be slight more definite with the notation. Say that the largest Fibonacci number smaller than N is Fn. Then the Fibonacci number that comes right before Fn is Fn-1. Also, the Fibonacci number that comes right after is Fn+1. But since N is not a Fibonacci number, and Fn is the largest Fibonacci number less than N, we know that N < Fn+1. Since Fn+1 = Fn + Fn-1, then N < Fn - Fn-1. Rearranging, N - Fn < Fn-1.

Now use mathematical induction in the strong form to show that every natural number can be written as a sum of distinct non-consecutive Fibonacci numbers. First, 1 can be written as the trivial sum of the first Fibonacci number by itself: 1 = F1. Let N be given. Now assume that every number less than N can be written as the sum of distinct non-consecutive Fibonacci numbers. Then let F be the largest Fibonacci number less than N, so N = F + (N - F). But we just showed that N - F is less than the immediately previous Fibonacci number. By the strong induction hypothesis, N - F can be written as the sum of distinct non-consecutive Fibonacci numbers. The proof is done. (This is what the book problem alludes to as systematically reducing the problem to a smaller problem.)

Problem 39, Generalized Sums

Consider first the generalized Fibonacci relation Fn+1 = Fn + Fn-1, with starting terms F0 = 1 and F1 = 1. Then as in Problem 38, the first 15 terms in the sequence are 1, 1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363, 8119, 19601, 47321, 114243. We observe that these grow quite rapidly,w with large gaps between the terms. Now we ask if every natural number can be expressed as the sum of distinct non-consecutive generalized Fibonacci numbers? The answer is no, and we can illustrate why not with several counter-examples: 11 can be written as the sum of several generalized Fibonacci numbers, but they are not non-consecutive, 11 = 7 + 3 + 1. Likewise for 12: 12 = 7 + 3 + 1 + 1. But 13 cannot be expressed as the sum of distinct generalized Fibonacci numbers, we would have to repeat one 13 = 7 + 3 + 3, or another 13 = 7 + 3 + 1 + 1 + 1. Similarly for 14, 15 and 16. It gets worse, since the largest number we can express even with all 5 of the first 5 terms of the generalized Fibonacci sequence is 1 + 1 + 3 + 7 + 17 = 22. So there is no way to reproduce the natural numbers 23 < n < 40 as a sum of distinct generalized Fibonacci numbers. We would have to use multiple copies of some of the generalized Fibonacci numbers.

Problems to Work for Understanding

  1. Solidifying Ideas: pages 59: 9,10,11,12,14
  2. New Ideas: page 61: 29, 30
  3. Habits of Mind: page 62: number 40

Reading Suggestion:

  1. 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]