# Fun lecture on geometric series (Part 5): 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 this series of posts, I’m describing a fun lecture on generating functions that I’ve given to my Precalculus students. In the previous post, we looked at the famed Fibonacci sequence

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

We also looked at that (slightly less famous) Quintanilla sequence

$1, 1, 3, 5, 11, 21, 43, 85, \dots$

which is defined so that each term is the sum of the previous term and twice the term that’s two back in the sequence. Using the concept of a generating function, we found that the $n$th term of the Quintanilla sequence is

$Q_n = \displaystyle \frac{2^{n+1} + (-1)^n}{3}$

To close out the fun lecture, I’ll then verify that this formula works by using mathematical induction. As seen below, it’s a lot less work to verify the formula with mathematical induction than to derive it from the generating function.

$n=0$: $Q_0 = \displaystyle \frac{2+1}{3} = 1$.

$n = 1$: $Q_1 = \displaystyle \frac{2^2-1}{3} = 1$.

$n-1$ and $n$: Assume the formula works for $Q_{n-1}$ and $Q_n$.

$n+1$:

$Q_{n+1} = Q_n + 2 Q_{n-1}$

$Q_{n+1} = \displaystyle \frac{2^{n+1} + (-1)^n}{3} + 2 \cdot \frac{2^n + (-1)^{n-1}}{3}$

$Q_{n+1} = \displaystyle \frac{2^{n+1} + (-1)^n + 2 \cdot 2^n + 2 \cdot (-1)^{n-1}}{3}$

$Q_{n+1} = \displaystyle \frac{2^{n+1} + 2^{n+1} + (-1)^n - 2 \cdot (-1)^n}{3}$

$Q_{n+1} = \displaystyle \frac{2 \cdot 2^{n+1} - (-1)^n}{3}$

$Q_{n+1} = \displaystyle \frac{2^{n+2} + (-1)^{n+1}}{3}$

That’s the formula if $n$ is replaced by $n+1$, and so we’re done.

Let me note parenthetically that the above simplification is not all intuitive when encountered by students for the first time — even really bright students who know the laws of exponents cold and who know full well that $x + x = 2x$ and $x - 2x = -x$. That said, I’ve found that simplifications like $2^{n+1} + 2^{n+1} = 2 \cdot 2^{n+1} = 2^{n+2}$ are usually a little intimidating to most students at first blush, though they can quickly get the hang of it.

By this point, I’m usually near the end of my 50-minute fun lecture. Since students are not responsible for replicating the contents of the fun lecture, I’ve found that most students are completely comfortable with this pace of presentation.

Then I ask my students which way they’d prefer: generating functions or mathematical induction? They usually respond induction. However, they also are able to realize that the thing that makes mathematical induction is also the challenge: they have to guess the correct formula and then use induction to verify that the formula actually works. On the other hand, with generating functions, there’s no need to guess the correct answer… you just follow the steps and see what comes out the other side.

Finally, to close the fun lecture, I tell them that the above steps can be used to find a closed-form expression for the Fibonacci sequence. (I devised the Quintanilla sequence for pedagogical purposes: since the denominator of its generating function easily factors, the subsequent steps aren’t too messy.) I won’t go through all the steps here, so I’ll leave it as a challenge for the reader to start with the generating function

$f(x) = \displaystyle \frac{1}{1-x-x^2}$,

factor the denominator by finding the two real roots of $1 - x - x^2 = 0$, and then mimicking the above steps. If you want to cheat, just use the following Google search to find the answer: http://www.google.com/#q=fibonacci+%22generating+function%22

I conclude this post with some pedagogical reflections. I taught this fun lecture to about 10 different Precalculus classes, and it was a big hit each time. I think that my students were thoroughly engaged with the topic and liked seeing an unorthodox application of the various topics in Precalculus that they were learning (sequences, series, partial fractions, factoring polynomials over $\mathbb{R}$, mathematical induction). So even though they would likely receive a fuller treatment of generating functions in a future course like Discrete Mathematics, I liked giving them this little hint of what was lying out there for them in the future.

I covered the content of this series of five posts in a 50-minute lecture. I’d usually finish the proof by induction as time expired and then would challenge them to think about how to similarly find the formula for the Fibonacci sequence. The rules of a “fun lecture” were important to pull this off — I made it clear that students would not have to do this for homework, so the pressure was off them to understand the fine details during the lecture. Instead, the idea was for them to appreciate the big picture of how topics in Precalculus can be used in future courses.

Next Post