The Fibonacci sequence is probably one of the most famous — and most widely written-about — number sequences in all of mathematics. So why write about it, if it’s been written about so much already? Well, because I can, and because it’s fun — there are good reasons it’s so popular! I plan to spend the next five posts (at least) talking about the Fibonacci sequence and its connections to other areas of mathematics.
The Fibonacci sequence is defined by the recurrence relation
In English, this says that the first two Fibonacci numbers are both equal to 1, and any Fibonacci number from the third onwards can be obtained by adding the previous two Fibonacci numbers. So the third Fibonacci number is 1 + 1 = 2; the fourth is 1 + 2 = 3; then 2 + 3 = 5; and so on. The first fifteen Fibonacci numbers are
As you can see, they get large fairly quickly. The 31st Fibonacci number is the first to exceed one million, and the 45th is already bigger than one billion.
The definition of the Fibonacci sequence is quite simple, but there’s a LOT more here than meets the eye, which I hope to expand on in subsequent posts. For now, we’ll start with this simple observation: what happens if you sum all the Fibonacci numbers up to a certain point? For example, let’s add up all the Fibonacci numbers up to 5: 1 + 1 + 2 + 3 + 5 = 12. Okay. How about going one further: 1 + 1 + 2 + 3 + 5 + 8 = 20. If we include 13 as well, we get 33. Do you see a pattern? (Hint: compare the sums we got (12,20,33) with the Fibonacci sequence itself.) Does this always work, and if so, can you show why (and if not, can you give an example where it doesn’t)? Feel free to post comments!
The Math Less Traveled 
I’ve noticed that the tenth Fibonacci number is the same as in the sequence of 1, 3, 6, 10…. It’s also the sum of the first five perfect squares (or the first six, if 0 counts).
Indeed. Odd, isn’t it? I don’t think (?) there’s anything deeper than coincidence going on, but it is a neat coincidence.
Incidentally, my dad turns 55 this Sunday. Perhaps the number will be magical for him as well.
It’s been years since my math training, but I think this constitutes a proof: We want to show that
F(1) + F(2) + … + F(n) = F (n+2) – 1. By definition,
F(n+2)=F(n) + F (n+1), so, we can restate what we want to prove as:
F(1) + F(2) + … + F(n) = F(n) + F(n+1) – 1. Subtract F(n) from each side:
F(1) + F(2) + … + F(n-1) = F(n+1) – 1. Which is the same as what we wanted to prove, restated for n-1. In other words, for any n, the statement is true if it is also true for n-1. For any n, then, we can work our way back to the beginning of the sequence, and if it is true for the beginning of the sequence, as you have shown for n=4 and n=5 (and it also works for n=1, 2, 3), then it is true all the way down the line.
naw; this’ll happen all the time (after F(1)):
the sum of the first n fibs is F(n+2) -1.
proof.
base case:
F(1) + F(2) = 2 = F(4) – 1.
now suppose, for some n, that
the sum, as i runs from 1 to n, of F(i)
is F(n+2) – 1 (induction hypothesis).
now consider
the sum, as i runs from 1 to n+1:
F(1) + F(2) + … F(n) + F(n+1).
by our induction hypothesis,
this is equal to F(n+2) + F(n+1) – 1.
by the definition of F, this gives us
F(n+3) -1 (i.e., F( [n+1] +2 ) -1,
as we need to complete our induction).
actually, it works for F(1), too …
the “base case” should actually be
F(1) = 1 = F(3) – 1.
@Dave C, vlorbik: nice!
Pingback: A few related problems… « The Math Less Traveled
Pingback: Explicit Fibonacci numbers | The Math Less Traveled
Pingback: Golden powers | The Math Less Traveled
Pingback: A Fibonacci pattern | The Math Less Traveled