Recurrence Relations - Main Theorem

The fundamental theorem for linear homogeneous recurrence relations with constant coefficients provides a complete characterization of solutions based on the characteristic equation.

DefinitionGeneral Solution Theorem

Consider the linear homogeneous recurrence relation: $a_n = c_1a_{n-1} + c_2a_{n-2} + \cdots + c_ka_{n-k}$

with characteristic equation: $r^k - c_1r^{k-1} - c_2r^{k-2} - \cdots - c_k = 0$

Let $r_1, r_2, \ldots, r_t$ be the distinct roots with multiplicities $m_1, m_2, \ldots, m_t$ respectively (so $m_1 + m_2 + \cdots + m_t = k$ ). Then the general solution is: $a_n = \sum_{i=1}^{t} \left(\sum_{j=0}^{m_i-1} \alpha_{i,j} n^j\right) r_i^n$

where $\alpha_{i,j}$ are constants determined by initial conditions.

Proof:

We prove this in stages:

Step 1: Each term of the form $n^j r^n$ satisfies a recurrence when $r$ is a root of multiplicity $> j$ .

Consider the operator $L$ defined by $L(a_n) = a_n - c_1a_{n-1} - \cdots - c_ka_{n-k}$ .

If $r$ is a root of the characteristic equation, then $L(r^n) = 0$ . This means $r^n$ is a solution to the homogeneous recurrence.

If $r$ is a root of multiplicity $m$ , then not only is $r$ a root, but also the derivative conditions hold: $p(r) = p'(r) = \cdots = p^{(m-1)}(r) = 0$ where $p(x)$ is the characteristic polynomial.

By properties of difference operators, if $p(r) = 0$ with multiplicity $m$ , then $L(n^j r^n) = 0$ for all $j = 0, 1, \ldots, m-1$ .

Step 2: The solutions form a vector space.

If $a_n$ and $b_n$ are solutions to the homogeneous recurrence, then so is any linear combination $\alpha a_n + \beta b_n$ : $L(\alpha a_n + \beta b_n) = \alpha L(a_n) + \beta L(b_n) = \alpha \cdot 0 + \beta \cdot 0 = 0$

Step 3: The solutions $\{n^j r_i^n\}$ are linearly independent.

We need to show that if: $\sum_{i=1}^{t} \sum_{j=0}^{m_i-1} \alpha_{i,j} n^j r_i^n = 0$

for all $n$ , then all $\alpha_{i,j} = 0$ .

This follows from the fact that exponential polynomials $n^j r^n$ with distinct bases $r$ are linearly independent as functions. This can be proven using Wronskian determinants or by induction on the number of distinct roots.

Step 4: Dimension counting.

The recurrence is of order $k$ , so the solution space has dimension $k$ (determined by $k$ initial conditions).

We have constructed exactly $k = m_1 + m_2 + \cdots + m_t$ linearly independent solutions.

Therefore, these solutions span the entire solution space. $\square$

ExampleApplication with Repeated Roots

Consider $a_n = 4a_{n-1} - 4a_{n-2}$ with $a_0 = 1$ and $a_1 = 3$ .

Characteristic equation: $r^2 - 4r + 4 = 0$ , which factors as $(r-2)^2 = 0$ .

This gives a repeated root $r = 2$ with multiplicity 2.

General solution: $a_n = (\alpha_1 + \alpha_2 n) \cdot 2^n$

Using initial conditions:

$a_0 = 1$ : $\alpha_1 = 1$
$a_1 = 3$ : $(\alpha_1 + \alpha_2) \cdot 2 = 3$ , so $2 + 2\alpha_2 = 3$ , giving $\alpha_2 = 1/2$

Therefore: $a_n = (1 + n/2) \cdot 2^n = 2^n + n \cdot 2^{n-1} = 2^{n-1}(2 + n)$

Remark

This theorem is the discrete analog of the theory of linear differential equations with constant coefficients. The characteristic equation plays the same role in both theories, and the solutions have the same form (exponentials and polynomial-exponential products). This parallel extends to non-homogeneous equations, where the method of undetermined coefficients works identically in both contexts. The connection runs deeper through generating functions, which transform recurrences into differential equations for the generating function.