CMSC-27100

Discrete Math

Winter Quarter, 2019

Home Lectures Policies

---

Piazza

Lecture 21: Linear Recurrences

\( \newcommand{\set}[1]{\{#1\}} \newcommand{\comprehension}[2]{\{#1\,\vert\,#2\}} \newcommand{\size}[1]{\left\vert#1\right\vert} \newcommand{\true}{\top} \newcommand{\false}{\bot} \newcommand{\limplies}{\rightarrow} \newcommand{\divides}{\mathbin{\vert}} \newcommand{\mult}{\mathbin{\cdot}} \newcommand{\xor}{\oplus} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\complement}[1]{\overline#1} \newcommand{\powerset}{\mathcal{P}} \newcommand{\ixUnion}{\bigcup} \newcommand{\ixIntersect}{\bigcap} \newcommand{\Div}{\mathrm{div}} \newcommand{\gcd}{\mathrm{gcd}} \newcommand{\divmod}{\mathop{\mathbf{divmod}}} \newcommand{\div}{\mathop{\mathbf{div}}} \newcommand{\mod}{\mathop{\mathbf{mod}}} \newcommand{\ceiling}[1]{\lceil#1\rceil} \newcommand{\floor}[1]{\lfloor#1\rfloor} \DeclareMathOperator{\Pr}{Pr} \DeclareMathOperator{\rng}{rng} \DeclareMathOperator{\E}{E} \DeclareMathOperator{\V}{V} \DeclareMathOperator{\T}{T} \DeclareMathOperator{\O}{O} \newcommand{\abs}[1]{\left\lvert#1\right\rvert} \)

We're back in Rosen today, Chapter 8.2, with some of my own crazy sauce.

The basic, motivating problems are fibonacci-like recurrences, e.g.,

\begin{equation*} f(n) = \begin{cases} 0,&\text{if $n = 0$}\\ 1,&\text{if $n = 1$}\\ 5 f(n-1) - 6 f(n-2),&\text{otherwise}\\ \end{cases} \end{equation*}

We can compute the first few values, and hope for enlightenment:

$n$	$f(n)$
0	0
1	1
2	5
3	19
4	65
5	211
6	665
7	2059
8	6305
9	19171
10	58025

Aside from a sense that $f$ is growing exponentially, at something like the rate $3^n$, I'm not feeling particularly enlightened, are you?

Still, hope springs eternal. Let's guess a solution of the form $f(k) = r^k$. Plugging this into the recurrence gives us

\begin{align*} r^n &= 5 r^{n-1} - 6 r^{n-2}\\ r^n - 5 r^{n-1} + 6 r^{n-2} &= 0\\ r^{n-2}(r^2 - 5r +6) &= 0\\ r^{n-2}(r-2)(r-3) &= 0 \end{align*}

From this, we get roots $r = 0,2,3$, and we can easily verify that $0^n$, $2^n$, and $3^n$ solve the recurrence, although none of these “solutions” satisfies our initial conditions. So now what? Let's make another guess, this time that our final solution will be a linear combination of these functions, i.e., it will have the form $a 2^n + b 3^n$ (note that the $0^n$ term doesn't contribute anything). We can easily verify that functions of this form solve the recurrence, and this leaves us to solve for the initial conditions:

\begin{align*} 2^0 a+ 3^0 b &= 0 \\ 2^1 a + 3^1 b &= 1 \end{align*}

from which we easily derive $a=-1$ and $b=1$, so that $f(n) = 3^n - 2^n$. Nice.

Definition 21.2 A linear homogeneous recurrence of degree $k$ with constant coefficients takes the form

\begin{equation*} f_n = c_1 f_{n-1} + c_2 f_{n-2} + \cdots + c_k f_{n-k} \end{equation*}

where the $c_i$ are all real, and $c_k \not=0$.

Definition 21.3 The characteristic equation for the linear homogeneous recurrence of degree $k$ with constant coefficients above is

\begin{equation*} x^n - c_1 x^{n-1} - c_2 x^{n-2} - \ldots - c_k x^{n-k} = 0 \end{equation*}

Theorem 21.4 Suppose that the characteristic equation for a linear homogeneous recurrence of degree $k$ has distinct real roots $r_1,r_2,\ldots,r_k$. Then the solutions to the recurrence take the form $f_n = a_1 r_1^n + a_2 r_2^n + \cdots + a_k r_k^n$, for real constants $a_1,a_2,\cdots,a_k$.

This allows us to solve most of the linear recurrences we experience in practice.

Of course, Theorem 21.4 doesn't cover all cases. One possibility is that there are repeated roots. These give rise to terms in the answer of the form $n r^n$, $n^2 r^n$, etc., depending on the multiplicity of the repeat.

Example 21.6 Consider the recurrence

\begin{align*} f_n = \begin{cases} 0, &\text{if $n=0$}\\ 1, &\text{if $n=1$}\\ 4 f_{n-1} - 4 f_{n-2}\\ \end{cases} \end{align*}

The characteristic equation is $x^2-4x+4 = 0$, i.e., $(x-2)(x-2) = 0$. So $2$ is the unique, degree $2$ root of the characteristic equation. Thus, the form of the solution is $a 2^n + b n 2^n$. Applying our initial conditions, we have

\begin{align*} a &= 0\\ 2a + 2 b &= 1\\ \end{align*}

whence, $a=0$ and $b=1/2$. So the solution to the recurrence is $f_n = {1\over 2} n 2^n = {n 2^{n-1}}$.

The Nonhomogeneous Case

Sometimes, recurrences come to us in non-homogeneous form, e.g., $f_n = 3 f_{n-1} + 2n$. What then? Let's start by guessing a solution of the form $f_n = an + b$. This seems reasonable, because $f_n - 3 f_{n-1} = 2n$, and differences of polynomials are polynomials. Doing this gives us

\begin{align*} an + b &= 3(a(n-1) + b) + 2n\\ an + b &= 3an - 3a + 3b + 2n\\ (2a+2)n + (2b-3a) &= 0\\ \end{align*}

A polynomial is zero if and only if all of its coefficients are zero, giving rise to a simple linear system

\begin{align*} 2a + 2 &= 0\\ 2b-3a &=0 \end{align*}

whence $a = -1$, $b=-3/2$, and $f_n = -n - 3/2$

The problem is, our initial conditions are $f_0 = 0$. Now what?

An important observation is that if $f$ and $g$ are both solutions to the non-homogeneous equation, then $f-g$ is a solution to the equation that arises from eliminating the non-homogeneous terms, i.e., to the associated homogeneous linear recurrence $f_n = 3 f_{n-1}$, which we can easily solve as $f_n = 3^n$ by a simple application of our earlier technique. Turning this around, we can now consider functions of the form $f_n = a 3^n - n - 3/2$, and they will all solve the recurrence, but the particular choice $a = 3/2$ also solves the boundary condition $f_0 = 0$.

Theorem 21.7 The general form of the solution of an nonhomogeneous linear recurrence consists of a particular solution of that recurrence, plus the general form of the associated homogeneous linear equation.

Some Crazy Sauce

Approaching linear recurrences via the machinery above can be a bit tedious, especially, e.g., if all you want is $f_{1000}$. At that point, it's easier just to program it up (hopefully in a clever way), run it, and move on with your life. But there comes a point where “just programming it up” can become tedious too, or even computationally problematic, say if we want $f_{10^{10}}$. There is another way...

Note that if $f_n$ is a linear combination of $f_{n-1},f_{n-2},\ldots,f_{n-k}$, it's also trivially the case that $f_{n-1}$ through $f_{n-k+1}$ are as well. Thus, we can construct a $k\times k$ matrix $M$ such that

\begin{equation*} \begin{bmatrix} f_{n}\\ f_{n-1}\\ \ldots\\ f_{n-k+1} \end{bmatrix} = M \times \begin{bmatrix} f_{n-1}\\ f_{n-2}\\ \ldots\\ f_{n-k} \end{bmatrix} \end{equation*}

We can rework this, via induction, as

\begin{equation*} \begin{bmatrix} f_{n}\\ f_{n-1}\\ \ldots\\ f_{n-k+1} \end{bmatrix} = M^{n-k+1} \times \begin{bmatrix} f_{k-1}\\ f_{k-2}\\ \ldots\\ f_{0} \end{bmatrix} \end{equation*}

For example, in the special case of the fibonacci numbers, we have

\begin{equation*} \begin{bmatrix} f_{n}\\ f_{n-1}\\ \end{bmatrix} = \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}^{n-1} \times \begin{bmatrix} 1\\ 0 \end{bmatrix} \end{equation*}

The punchline here is that we can do the matrix exponentiation first, using the standard fast exponentiation algorithm:

\begin{align*} a^{2n} &= (a^2)^n\\ a^{2n+1} &= a \mult a^{2n} \end{align*}

If you ever want to know the trillionth fibonacci number, mod 17, this is definitely the way to go.

Thinking like a Professor

In the “real world,” when you're called on to solve a recurrence, you typically end up with bases resembling $31\pm \sqrt{17} \over 11$, and coefficients on the linear terms that are even worse. So how do I come up with nice examples for us to solve, whether in class, as homework, or on exams?

Answer: Think Jeopardy, the TV gameshow where you're give the answer, and have to come up with the appropriate question.

Example 21.9 What natural linear homogeneous recurrence is satisfied by $2 n 3^n - 2^n$?

The first thing we note is that the form of our answer gives rise to a characteristic polynomial whose roots are $2$, $3$, and $3$. So we type (r-2)(r-3)^2 into the evaluation field at WolframAlpha.com, and get the expanded form $r^3 - 8r^2 +21r -18$. This gives us the form of the recurrence. We know we need to specify three data points, so we evaluate our answer at $n=0,1,2$, obtaining $-1,4,32$, and so our problem is:

Alex Trebek would be pleased.

---

© 2016–2019 Stuart A. Kurtz
Last modified: March 13, 2019