2.2 Fibonacci Numbers
As an example, lets look at the Fibonacci numbers. They were studied first by Fibonacci during the Middle Ages. They are defined by the following conditions:
\(F(0) = 0, \: F(1) = 1\)
and for all integer arguments, we have
\(F(j+2) = F(j+1) + F(j)\)
In words, each Fibonacci number is the sum of the previous two of them.
These numbers have lots of interesting properties, and we shall look at two of them.
Start by entering the words Fibonacci numbers in say box A1. (In case you ever want to look later at what you are doing now, having a label helps.)
Add the following labels: n in A9, F(n) in B9, Golden ratio in C9, Partial sums in D19, and F(-n) in E9.
Then enter \(0\) in A10 and =A10+1 in A11.
Now copy this down column A to A60.
What do you see? Not much; you see the integers from \(0\) to \(50\).
OK. Now in B10 enter \(0\) and in B11, enter \(1\). Then enter =B10+B11 in B12.
Copy B12 down column B to B60.
You will see the Fibonacci numbers in that column, from argument \(0\) up to \(50\).
Next let us look at the ratio of Fibonacci numbers to their immediate predecessors.
Do this by entering =B12/B11 in C12, and copying it down to C60.
What do you see?
Let’s figure out what the number you are seeing is. Suppose what is in B41 is \(x\) times what is in B40, and what is in B42 is similarly approximately \(x\) times what is in B41 which is approximately \(x^2\)B40.
This means that \(x^2\)B(40) = B(42) = F(42) = F(41) + F(40) = xB(40) + B(40). Divide by B(40) and we get the quadratic equation \(x^2 = x + 1\). So the ratio \(x\) that we are getting is a solution of this equation. The larger solution to this equation, which is what you see, is called the "Golden Ratio".
Now try the following: enter in \(0\) in D10 and =B11+D10 in D11. Copy that down column D to D60.
What you are getting in column D is the sum of the Fibonacci numbers up to the index (in column A) where you are. What can you say about this sum? Compare the entries in column B with those in column D, and describe their relation to each other. Also notice that the entry in D11, =B11+D10, copied down column D as done here, produces partial sums of the entries in column B. That means that the entry in D50, for example is the sum of the first \(51\) Fibonacci numbers.
Here’s something else you can do. The defining property of Fibonacci numbers is
\(f(a+2) = f(a+1) + f(a)\). We can also write that as \(f(a) = f(a+2) - f(a+1)\). This allows us to define Fibonacci numbers with negative arguments. Thus \(f(-1) = f(1)-f(0) = 1-0 = 1\), \(f(-2) = f(0) - f(-1) = -1\), and so on.
So put \(0\) in E10, put \(1\) in E11, and in E12 enter =E10-E11. Then copy E12 down column E to E60.
The entries in column E will be the negative Fibonacci numbers with argument in column A.
What can you say about negative argument Fibonacci numbers?
By the way, the Fibonacci numbers with positive arguments count the number of different ways of inserting \(n-1\) identical dominoes into a \(2\) by \(n-1\) grid, so that each domino covers two adjacent boxes and no box is covered twice.
Exercises:
2.1 Set this all up on your own machine.
2.2 Prove that the Fibonacci numbers count the number of different ways of inserting \(n -1\) dominoes into a \(2\) by \(n-1\) grid, so that each domino covers two adjacent boxes.
2.3 Make a definition of convergence of a sequence that reflects the property of the ratio of Fibonacci numbers to their predecessors that you see in column C.
2.4 This procedure produces a solution to the quadratic equation indicated above. Given any quadratic with integer coefficients, we can produce a recursion as above and by substituting it into B4 and copying it down, look at what happens to it. Try doing this with some quadratics, and find another for which we get a solution like we do for Fibonacci numbers, and one which we don't. What happens with the cubic \(x^3 = x + 1\)?