## The Fibonacci sequence: an introduction

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 $\begin{array}{rcl}F_1 = F_2 & = & 1 \\ F_n & = & F_{n-1} + F_{n-2} \qquad (n > 2). \end{array}$

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 $1,1,2,3,5,8,13,21,34,55,89,144,233,377,610.$

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! Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in famous numbers, fibonacci, iteration, pattern, sequences. Bookmark the permalink.

### 11 Responses to The Fibonacci sequence: an introduction

1. Steve Gilberg says:

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

2. Brent says:

Indeed. Odd, isn’t it? I don’t think (?) there’s anything deeper than coincidence going on, but it is a neat coincidence.

3. Steve Gilberg says:

Incidentally, my dad turns 55 this Sunday. Perhaps the number will be magical for him as well.

4. Dave C says:

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.

5. vlorbik says:

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

6. vlorbik says:

actually, it works for F(1), too …
the “base case” should actually be
F(1) = 1 = F(3) – 1.

7. Brent says:

@Dave C, vlorbik: nice!