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 nth term of the Quintanilla sequence is

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

green line

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.

green line

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

green lineI 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
Leave a comment

1 Comment

  1. Fun lecture on geometric series: Index | Mean Green Math

Leave a Reply

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

WordPress.com Logo

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

Google+ photo

You are commenting using your Google+ 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.

%d bloggers like this: