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:
The Fibonacci sequence starts with two s, and each subsequent term is defined as the sum of the two previous terms. Of course, the generating function for this sequence is
Slightly less famous than the Fibonacci sequence is (ahem) the Quintanilla sequence. It also begins with two s, 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
- The second term is
- The third term is
- The fourth term is
- The fifth term is
- The sixth term is
- The seventh term is
- The eighth term is
And so on. The generating function for the Quintanilla sequence is
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 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 and get the answer — we will need to use the generating functions and .
To simplify the infinite series , 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 and also figure out and also :
Let’s now add the last three green equations together. Notice that everything on the right-hand cancels except for ! Therefore,
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.