Fun lecture on geometric series (Part 4): 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. We also used the Bag of Tricks to find that the generating function is

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

green lineTo get a closed-form definition of the Quintanilla sequence, let’s find the partial-fraction decomposition of Q(x). Notice that the denominator factors easily, so that

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

To find the partial fraction decomposition, we need to find the constants A and B so that

\displaystyle \frac{A}{1+x} + \frac{B}{1-2x} = \displaystyle \frac{1}{(1+x)(1-2x)},

or

A(1-2x) + B(1+x) = 1

Perhaps the easiest way of finding A and B is by substituting conveniently easy values of x.

  • If x = \displaystyle \frac{1}{2}, then we obtain \displaystyle \frac{3}{2} B = 1, or B = \displaystyle \frac{2}{3}.
  • If x = -1, then we obtain 3A =1, or A = \displaystyle \frac{1}{3}.

Therefore,

Q(x) = \displaystyle \frac{1}{3} \cdot \frac{1}{1+x} + \frac{2}{3} \cdot \frac{1}{1-2x}

green line

Finally, let’s write the rational functions on the right-hand side as infinite series. Using the formula for an infinite geometric series, we find

Q(x) = \displaystyle \frac{1}{3} \left(1 - x + x^2 - x^3 + x^4 - x^5 \dots \right) + \frac{2}{3} \left( 1 + 2x + 4x^2 + 8x^3 + 16x^4 + 32 x^5 \dots \right)

Notice that this matches the terms of the Quintanilla sequence! For example, the coefficient of the x^5 term is

\displaystyle -\frac{1}{3} + \frac{2}{3}(32) = \displaystyle \frac{63}{3} = 31,

which is a term of the Quintanilla sequence.

In general, the coefficient of the x^n term is

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

This is the long-awaited closed-form expression for the Quintanilla sequence. For example, we quickly see that the 12th term is \displaystyle \frac{2^{13} + 1}{3} = 2731, which was obtained without knowing the 10th and 11th terms.

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: