7.1 Linear recurrence relations with constant coefficients

Linear recurrence relations

Definition and structure

A linear recurrence relation defines each term of a sequence as a linear combination of previous terms, with constant coefficients. The general form is:

$a_k = c_1 a_{k-1} + c_2 a_{k-2} + \cdots + c_d a_{k-d} + f(k)$

where $c_1, c_2, \ldots, c_d$ are constants and $f(k)$ is some function of $k$.

The order of the relation equals the largest gap between indices. If the most distant term you reference is $a_{k-d}$, you have an order-$d$ relation.

Several well-known sequences are defined this way:

• Fibonacci sequence: $F_n = F_{n-1} + F_{n-2}$ (order 2)
• Arithmetic sequences: $a_n = a_{n-1} + d$ (order 1, non-homogeneous when $d \neq 0$)
• Geometric sequences: $a_n = r \cdot a_{n-1}$ (order 1, homogeneous)

These relations appear throughout combinatorics, computer science, and applied math whenever you need to model sequential processes like population growth or financial compounding. The main goal is usually to find a closed-form expression for $a_n$, and the standard tools for doing so are characteristic equations, generating functions, and matrix methods.

Identifying key elements

Initial conditions and coefficients

Initial conditions pin down which specific sequence satisfies the recurrence. The number of initial conditions you need equals the order of the relation. A second-order recurrence like the Fibonacci sequence needs two: $F_0 = 0,\; F_1 = 1$.

Coefficients are the constant multipliers $c_1, c_2, \ldots, c_d$. They can be positive, negative, or zero, and they heavily influence how the sequence behaves:

• $a_n = 2a_{n-1} - a_{n-2}$ with $a_0 = 1, a_1 = 3$ produces the sequence $1, 3, 5, 7, \ldots$ (linear growth, not exponential, since the characteristic equation has a repeated root at $r = 1$)
• $a_n = -a_{n-1}$ produces an alternating sequence that flips sign each step

The non-homogeneous part $f(k)$, when present, is treated separately from the coefficients of previous terms. For example, in $a_n = a_{n-1} + 3$, the constant 3 is the non-homogeneous term, making this an arithmetic sequence with common difference 3.

Getting these elements right matters because they determine both your solution method and the long-term behavior of the sequence.

Generating sequence terms

Calculation process

To compute terms from a recurrence, follow these steps:

1. Write down the recurrence, coefficients, and initial conditions. Example: $a_n = 2a_{n-1} - a_{n-2}$ with $a_0 = 1,\; a_1 = 3$.

2. Compute the next term by substituting the most recent known values.

   • $a_2 = 2a_1 - a_0 = 2(3) - 1 = 5$
   • $a_3 = 2a_2 - a_1 = 2(5) - 3 = 7$
   • $a_4 = 2a_3 - a_2 = 2(7) - 5 = 9$

3. Use the correct number of previous terms for the order. A second-order relation always needs two previous terms; a third-order relation needs three.

4. Watch the starting index. If the sequence begins at $n = 1$ instead of $n = 0$, adjust accordingly so you don't accidentally reference an undefined term.

5. Verify by back-substitution. Plug your computed terms back into the recurrence to confirm they satisfy it. Catching arithmetic errors early saves a lot of pain.

For generating many terms at once, iterative computation (a simple loop in Python or similar) is more efficient than recursion, which can be extremely slow for relations like Fibonacci due to redundant calculations.

Homogeneous vs non-homogeneous relations

Key differences and solution approaches

The distinction between these two types drives your entire solution strategy.

A homogeneous linear recurrence has $f(k) = 0$. Every term is built purely from previous terms with no outside forcing function:

$a_k = c_1 a_{k-1} + c_2 a_{k-2} + \cdots + c_d a_{k-d}$

The Fibonacci recurrence $F_n = F_{n-1} + F_{n-2}$ is homogeneous.

A non-homogeneous linear recurrence has $f(k) \neq 0$. There's an extra term that depends on $k$ (or is a nonzero constant):

$a_k = c_1 a_{k-1} + c_2 a_{k-2} + \cdots + c_d a_{k-d} + f(k)$

For example, $a_n = 2a_{n-1} + 3n$ is non-homogeneous because of the $3n$ term.

Solving homogeneous relations uses the characteristic equation directly. For $a_n = 3a_{n-1} - 2a_{n-2}$, you form:

$r^2 - 3r + 2 = 0 \implies (r-1)(r-2) = 0$

The roots $r = 1$ and $r = 2$ give the general solution $a_n = A \cdot 1^n + B \cdot 2^n$, and you use initial conditions to find $A$ and $B$.

Solving non-homogeneous relations requires two pieces:

1. The homogeneous solution (solve the associated homogeneous recurrence, i.e., set $f(k) = 0$).
2. A particular solution that accounts for $f(k)$, typically found via the method of undetermined coefficients. You guess a form for the particular solution based on the shape of $f(k)$ (polynomial, exponential, etc.), then solve for the unknown constants.

The complete solution is the sum of these two parts.

Long-term behavior also differs. Homogeneous relations tend toward exponential growth, decay, or oscillation depending on the characteristic roots. Non-homogeneous relations can exhibit additional patterns imposed by $f(k)$. For instance, $a_n = a_{n-1} + n$ grows quadratically (the particular solution is a quadratic polynomial in $n$), even though the homogeneous part alone would be constant.