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}$

To 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}$

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.