Recurrence Relations - Key Properties

Solving recurrence relations requires understanding how the characteristic equation's roots determine the solution form. Different types of roots lead to different solution structures, and these patterns are fundamental to the theory.

DefinitionSolution for Distinct Real Roots

If the characteristic equation $r^k - c_1r^{k-1} - \cdots - c_k = 0$ has $k$ distinct real roots $r_1, r_2, \ldots, r_k$ , then the general solution to the recurrence relation is: $a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + \cdots + \alpha_k r_k^n$

where $\alpha_1, \alpha_2, \ldots, \alpha_k$ are constants determined by initial conditions.

This is analogous to solving linear differential equations: the characteristic equation gives us the exponential basis functions, and initial conditions determine the coefficients.

ExampleSolving a Second-Order Recurrence

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

The characteristic equation is $r^2 = 5r - 6$ , or $r^2 - 5r + 6 = 0$ .

Factoring: $(r-2)(r-3) = 0$ , giving roots $r_1 = 2$ and $r_2 = 3$ .

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

Using initial conditions:

$a_0 = 1$ : $\alpha_1 + \alpha_2 = 1$
$a_1 = 4$ : $2\alpha_1 + 3\alpha_2 = 4$

Solving: $\alpha_1 = -1$ and $\alpha_2 = 2$ .

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

DefinitionSolution for Repeated Roots

If the characteristic equation has a root $r$ with multiplicity $m$ , then the corresponding part of the general solution is: $(\alpha_1 + \alpha_2 n + \alpha_3 n^2 + \cdots + \alpha_m n^{m-1}) r^n$

where $\alpha_1, \ldots, \alpha_m$ are constants.

This phenomenon mirrors the behavior in differential equations where repeated roots introduce polynomial factors.

ExampleFibonacci Closed Form

The Fibonacci recurrence $F_n = F_{n-1} + F_{n-2}$ has characteristic equation $r^2 = r + 1$ , or $r^2 - r - 1 = 0$ .

Using the quadratic formula: $r = \frac{1 \pm \sqrt{5}}{2}$ .

Let $\phi = \frac{1 + \sqrt{5}}{2}$ (the golden ratio) and $\hat{\phi} = \frac{1 - \sqrt{5}}{2}$ .

General solution: $F_n = \alpha_1 \phi^n + \alpha_2 \hat{\phi}^n$

Using $F_0 = 0$ and $F_1 = 1$ : $F_n = \frac{1}{\sqrt{5}}\left(\phi^n - \hat{\phi}^n\right) = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$

This is Binet's formula.

DefinitionMethod of Undetermined Coefficients

For non-homogeneous recurrences $a_n = c_1a_{n-1} + \cdots + c_ka_{n-k} + f(n)$ , we find a particular solution $a_n^{(p)}$ by guessing a form based on $f(n)$ :

If $f(n) = d$ (constant), try $a_n^{(p)} = C$
If $f(n) = d \cdot n^k$ , try $a_n^{(p)} = C_0 + C_1n + \cdots + C_kn^k$
If $f(n) = d \cdot s^n$ , try $a_n^{(p)} = C \cdot s^n$

If the guessed form solves the homogeneous part, multiply by $n$ .

Remark

The theory of recurrence relations has deep connections to generating functions. The generating function $G(x) = \sum_{n=0}^{\infty} a_n x^n$ transforms a recurrence relation into a functional equation, which can often be solved to give closed forms. For instance, the Fibonacci generating function is $G(x) = \frac{x}{1-x-x^2}$ , and expanding this as a power series recovers Binet's formula. This connection between discrete recurrences and analytic functions is a powerful bridge in combinatorics.

These solution methods provide systematic approaches to solving a wide class of recurrence relations.