My Favorite One-Liners: Part 28

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them. Today’s quip is one that I’ll use when simple techniques get used in a complicated way.

Consider the solution of the linear recurrence relation

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

where F_0 = 1 and F_1 = 1. With no modesty, I call this one the Quintanilla sequence when I teach my students — the forgotten little brother of the Fibonacci sequence.

To find the solution of this linear recurrence relation, the standard technique — which is a pretty long procedure — is to first solve the characteristic equation, from Q_n - Q_{n-1} - 2 Q_{n-2} = 0, we obtain the characteristic equation

r^2 - r - 2 = 0

This can be solved by any standard technique at a student’s disposal. If necessary, the quadratic equation can be used. However, for this one, the left-hand side simply factors:

(r-2)(r+1) = 0

r=2 \qquad \hbox{or} \qquad r = -1

(Indeed, I “developed” the Quintanilla equation on purpose, for pedagogical reasons, because its characteristic equation has two fairly simple roots — unlike the characteristic equation for the Fibonacci sequence.)

From these two roots, we can write down the general solution for the linear recurrence relation:

Q_n = \alpha_1 \times 2^n + \alpha_2 \times (-1)^n,

where \alpha_1 and \alpha_2 are constants to be determined. To find these constants, we plug in n =0:

Q_0 = \alpha_1 \times 2^0 + \alpha_2 \times (-1)^0.

To find these constants, we plug in n =0:

Q_0 = \alpha_1 \times 2^0 + \alpha_2 \times (-1)^0.

We then plug in n =1:

Q_1 = \alpha_1 \times 2^1 + \alpha_2 \times (-1)^1.

Using the initial conditions gives

1 = \alpha_1 + \alpha_2

1 = 2 \alpha_1 - \alpha_2

This is a system of two equations in two unknowns, which can then be solved using any standard technique at the student’s disposal. Students should quickly find that \alpha_1 = 2/3 and \alpha_2 = 1/3, so that

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

which is the final answer.

Although this is a long procedure, the key steps are actually first taught in Algebra I: solving a quadratic equation and solving a system of two linear equations in two unknowns. So here’s my one-liner to describe this procedure:

This is just an algebra problem on steroids.

Yes, it’s only high school algebra, but used in a creative way that isn’t ordinarily taught when students first learn algebra.

I’ll use this “on steroids” line in any class when a simple technique is used in an unusual — and usually laborious — way to solve a new problem at the post-secondary level.



2 thoughts on “My Favorite One-Liners: Part 28

Leave a Reply

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

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