Recipe

Solve a linear homogeneous recurrence

Use when: you have a recurrence where every term is a first-power multiple of some a_{n-k}, with no added constant, plus two initial conditions

Goal: an explicit formula for a_n, built from the characteristic equation's roots and matching both initial conditions

Taught in Linear homogeneous recurrences

1. 1

   Check every term is a plain multiple of some a_{n-k}, first power only, with no products of terms and no added constant or outside function of n.

   Example

   a_n=2a_{n-1}+3a_{n-2} qualifies: both terms are plain multiples of an earlier term, with nothing else added.

   • every term is a first-power multiple of some a_{n-k}, nothing else added — this method applies.
   • an added constant, a product of terms, or a squared term appears — this method doesn't apply as is.

   Why: the characteristic-equation method is built on substituting powers for each term, which only works when every term already has this shape.

2. 2

   Replace a_n, a_{n-1}, a_{n-2} with x^n, x^{n-1}, x^{n-2}, then divide every term by the lowest power to leave an ordinary polynomial in x.

   Example

   a_n=2a_{n-1}+3a_{n-2} becomes x^n=2x^{n-1}+3x^{n-2}; dividing by x^{n-2} leaves x^2=2x+3, i.e. x^2-2x-3=0.

   Why: a solution of the form a_n=r^n satisfies the recurrence exactly when r solves this polynomial equation.

3. 3

   Factor the polynomial if it factors cleanly; otherwise fall back to the quadratic formula.

   Example

   x^2-2x-3=0 factors as (x-3)(x+1)=0, giving roots r_1=3 and r_2=-1.

   • two distinct real roots — continue to the next step with both.
   • a repeated root — this course doesn't cover the extra term a repeated root needs, so recognize it and stop here.

   Why: every root is exactly a growth rate r for which a_n=r^n solves the recurrence on its own.

4. 4

   Combine the two roots as a_n=c_1r_1^n+c_2r_2^n, substitute both initial conditions to get two equations in c_1 and c_2, and solve that system.

   Example

   With a_0=3, a_1=5: c_1+c_2=3 and 3c_1-c_2=5; adding gives 4c_1=8, so c_1=2 and c_2=1.

   Why: any blend of the two root-powers still solves the recurrence, and the initial conditions pin down exactly which blend matches this sequence.

5. 5

   Compute one more term directly from the formula, and separately from the original recurrence, and confirm they match.

   Example

   The formula gives a_2=2(3)^2+1(-1)^2=18+1=19; the recurrence gives a_2=2a_1+3a_0=2(5)+3(3)=19.

   Why: this catches an arithmetic slip in the factoring or the system before it's mistaken for the final answer.