Fun lecture on geometric series (Part 3): The Fibonacci sequence

Every once in a while, I’ll give a “fun lecture” to my students. The rules of a “fun lecture” are that I talk about some advanced applications of classroom topics, but I won’t hold them responsible for these ideas on homework and on exams. In other words, they can just enjoy the lecture without being responsible for its content.

In the two previous posts, I introduced the idea of a generating function and then talked about its application to counting money. In this post, we’ll take on the famous Fibonacci sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots

The Fibonacci sequence starts with two 1s, and each subsequent term is defined as the sum of the two previous terms. Of course, the generating function for this sequence is

f(x) = 1 + x + 2x + 3x^2 + 5x^3 + 8x^4 + 13x^5 + 21x^6 + 34x^7 + 55x^8 + \dots

green lineSlightly less famous than the Fibonacci sequence is (ahem) the Quintanilla sequence. It also begins with two 1s, but each subsequent term is defined as the sum of the previous term and twice the term that’s two back in the sequence. So,

  • The first term is 1
  • The second term is 1
  • The third term is 2(1) + 1 = 3
  • The fourth term is 2(1) + 3 = 5
  • The fifth term is 2(3) + 5 = 11
  • The sixth term is 2(5) + 11 = 21
  • The seventh term is 2(11) + 21 = 43
  • The eighth term is 2(21) + 43 = 85

And so on. The generating function for the Quintanilla sequence is

Q(x) = 1 + x + 3x^2 + 5x^3 + 11x^4 + 21x^5 + 43x^6 + 85x^7 + \dots

Both the Fibonacci and the Quintanilla sequences are examples of recursively defined sequences: we need to know the previous terms in order to get the next term. The major disadvantage of a recursively defined sequence is that, in order to get the 100th term, we need to know the 99th and 98th terms. To get the 98th term, we need the 96th and 97th terms. And so on. There’s no easy way to just plug in 100 to get the answer.

When I mention this to students, they naturally start trying to figure it out on their own. Occasionally, a student will notice that each term is roughly double the previous term. With a little more time, they see that the even terms are one less than double the previous term, while the odd terms are one more than the previous term. That’s entirely correct. However, that’s another example of a recursively defined function. So if a student volunteers this, I’ll use this as an opportunity to note that it’s pretty easy to find a recursive definition for a function, but it’s a lot harder to come up with a closed-form definition.

In order to get a closed-form definition for the sequence — something that we could just plug in 100 and get the answer — we will need to use the generating functions f(x) and Q(x).

green lineTo simplify the infinite series Q(x), we pull something out of the patented Bag of Tricks. In case you’ve forgotten, Socrates gave the Bag of Tricks to Plato, Plato gave it to Aristotle, it passed down the generations, my teacher taught the Bag of Tricks to me, and I teach it to my students.

Here’s the trick: let’s rewrite Q(x) and also figure out -xQ(x) and also -2x^2 Q(x):

Q(x) = 1 + x + 3x^2 + 5x^3 + 11x^4 + 21x^5 + 43x^6 + 85x^7 + \dots

-xQ(x) = \, \, \, -x- x^2 - 3x^3 - 5x^4 -11x^5 - 21x^6 - 43x^7 - \dots

-2x^2Q(x) = \, \, \, \, \, \, -2x^2 -2 x^3 - 6x^4 - 10x^5 - 22x^6 - 42x^7 - \dots

Let’s now add the last three green equations together. Notice that everything on the right-hand cancels except for 1! Therefore,

[1 - x - 2x^2] Q(x) = 1

Q(x) = \displaystyle \frac{1}{1-x-2x^2}

The generating function for the Fibonacci sequence is similarly found. You can probably guess it since the Fibonacci sequence does not involve doubling a previous term.

It turns out that these generating functions can be used to find a closed-form definition for both the Quintanilla sequence and the Fibonacci sequence. More on this tomorrow.

One thought on “Fun lecture on geometric series (Part 3): The Fibonacci sequence

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.