Linear Recurrence Relations with Constant Coefficients

Definition

A linear recurrence relation with constant coefficients is an equation that defines each term of a sequence as a linear combination of earlier terms, where the coefficients are constants and do not depend on the term index.

In general, a recurrence of order $k$ has the form:

$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + f(n)$$

where:

• $a_n$ is the $n$-th term of the sequence,
• $c_1, c_2, \dots, c_k$ are constants,
• $f(n)$ is an additional term depending on $n$ (if $f(n)=0$, the recurrence is called homogeneous),
• initial conditions such as $a_0, a_1, \dots, a_{k-1}$ are required to determine a unique sequence.

If $f(n)=0$, then the recurrence is:

$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$$

This is called a homogeneous linear recurrence relation with constant coefficients.

Main Content

1. First Concept: Order of a Recurrence and Initial Conditions

Order of the recurrence

• The order is the number of previous terms needed to compute the next term.
• For example, in $$a_n = 3a_{n-1} - 2a_{n-2},$$ the order is 2 because two previous terms are required.

Role of initial conditions

• A recurrence relation alone does not usually determine a unique sequence.
• Initial values are necessary. For the recurrence above, values like $a_0$ and $a_1$ must be given.
• Example: $$a_n = a_{n-1} + a_{n-2}, \quad a_0=0,\ a_1=1$$ generates the Fibonacci sequence: $$0, 1, 1, 2, 3, 5, 8, \dots$$

A useful way to think about recurrence relations is that they build a sequence step by step from earlier values.

Example of a simple recurrence: $$a_n = 2a_{n-1}, \quad a_0=3$$ This gives: $$3, 6, 12, 24, 48, \dots$$ Here each term doubles the previous one.

2. Second Concept: Homogeneous Linear Recurrence Relations

Definition of homogeneous recurrence

• A recurrence is homogeneous when there is no extra term $f(n)$ outside the linear combination of previous terms.
• General form: $$a_n = c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}$$

Characteristic equation method

• To solve homogeneous linear recurrences, we assume a solution of the form: $$a_n = r^n$$

• Substituting this into the recurrence gives the characteristic equation.

• For example, for $$a_n = 3a_{n-1} - 2a_{n-2},$$ assume $a_n=r^n$. Then: $$r^n = 3r^{n-1} - 2r^{n-2}$$ dividing by $r^{n-2}$ (for $r\neq 0$): $$r^2 = 3r - 2$$ so the characteristic equation is: $$r^2 - 3r + 2 = 0$$ which factors as: $$(r-1)(r-2)=0$$ hence roots are $r=1$ and $r=2$.

General solution for distinct roots

• If the characteristic equation has distinct roots $r_1, r_2, \dots, r_k$, the solution is: $$a_n = A_1r_1^n + A_2r_2^n + \cdots + A_kr_k^n$$

• The constants $A_1, A_2, \dots, A_k$ are determined from initial conditions.

For the example above: $$a_n = A(1)^n + B(2)^n = A + B2^n$$ Using initial conditions, one can solve for $A$ and $B$.

3. Third Concept: Non-Homogeneous Recurrence Relations and Solution Techniques

Non-homogeneous recurrence

• If the recurrence includes an extra term $f(n)$, it is non-homogeneous: $$a_n = c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}+f(n)$$

• The extra term may be a constant, polynomial, exponential, or other structured function.

General strategy: complementary + particular solution

• The solution is typically written as: $$a_n = a_n^{(h)} + a_n^{(p)}$$ where:

  • $a_n^{(h)}$ is the solution to the homogeneous part,
  • $a_n^{(p)}$ is one particular solution of the full recurrence.

Example

• Consider: $$a_n = 2a_{n-1} + 3,\quad a_0=1$$

• Homogeneous part: $$a_n = 2a_{n-1}$$ gives: $$a_n^{(h)} = C2^n$$

• For a particular solution, since the extra term is constant, try $a_n^{(p)} = K$.

• Substitute: $$K = 2K + 3$$ so: $$-K = 3 \Rightarrow K = -3$$

• General solution: $$a_n = C2^n - 3$$

• Using $a_0=1$: $$1 = C - 3 \Rightarrow C=4$$

• Final answer: $$a_n = 4\cdot 2^n - 3$$

For non-homogeneous recurrences, the form of the particular solution depends on the shape of $f(n)$. If $f(n)$ resembles a term already in the homogeneous solution, the trial form must be adjusted by multiplying by $n$ or a higher power of $n$.

Working / Process

1. Write the recurrence in standard form

• Move all terms involving previous sequence values to one side.
• Identify whether the recurrence is homogeneous or non-homogeneous.
• Determine its order and list the given initial conditions.

2. Form the characteristic equation

• Assume a solution of the form $a_n=r^n$.
• Substitute into the recurrence.
• Simplify to obtain a polynomial equation in $r$, called the characteristic equation.

3. Solve for the sequence

• Find the roots of the characteristic equation.
• Write the general homogeneous solution using the roots.
• If the recurrence is non-homogeneous, find a particular solution and add it to the homogeneous solution.
• Use initial conditions to determine the constants.
• Check the result by substituting a few terms back into the original recurrence.

Example workflow for: $$a_n = 5a_{n-1} - 6a_{n-2},\quad a_0=2,\ a_1=5$$

• Characteristic equation: $$r^2 - 5r + 6=0$$

• Factor: $$(r-2)(r-3)=0$$

• General solution: $$a_n = A2^n + B3^n$$

• Use initial conditions: $$a_0 = A+B = 2$$ $$a_1 = 2A+3B = 5$$

• Solve: $$A=1,\quad B=1$$

• Final formula: $$a_n = 2^n + 3^n$$

Advantages / Applications

Modeling counting problems

• Many combinatorial structures naturally lead to recurrence relations.
• Examples include tilings, paths in graphs, parenthesizations, and arrangement problems.

Closed-form formulas

• Recurrences can often be converted into explicit formulas.
• This makes it easier to compute terms far into the sequence without repeatedly using earlier values.

Computer science and algorithm analysis

• Recursive algorithms such as divide-and-conquer methods often produce recurrence relations.
• Solving them helps determine time complexity and performance behavior.

Summary

• Linear recurrence relations with constant coefficients define each term using fixed multiples of earlier terms.
• The characteristic equation is the main tool for solving homogeneous recurrences.
• Non-homogeneous recurrences are handled by combining homogeneous and particular solutions.
• Important terms to remember: recurrence relation, order, homogeneous, non-homogeneous, characteristic equation, initial conditions, general solution.