From Quadratic Equation to Linear Recurrence Sequence: How the Characteristic Equation Works

The Connection Between Roots and Linear Recurrence Sequences

Suppose we have a quadratic equation:

x² – px – q = 0.

How can we derive a recurrence relation from it?

Any second-order linear recurrence sequence is defined by the equation:

Aₙ₊₂ = p Aₙ₊₁ + q Aₙ.

If we assume that the sequence Aₙ has the form:

Aₙ = αⁿ,

where α is some number, then substituting this into the recurrence equation gives:

αⁿ⁺² = p αⁿ⁺¹ + q αⁿ.

Dividing both sides by αⁿ (assuming α ≠ 0):

α² = p α + q.

This is precisely the characteristic equation of the sequence.

A Worked Example of a Linear Recurrence Sequence

Suppose we are given the equation:

x² – 8x + 5 = 0.

Its roots are:

α = 4 + √11, β = 4 – √11.

Since 4 + √11 and 4 – √11 are roots of the characteristic equation, a sequence of the form:

Aₙ = c₁ αⁿ + c₂ βⁿ

satisfies the recurrence relation:

Aₙ₊₂ = 8 Aₙ₊₁ – 5 Aₙ.

Why the Characteristic Equation Works

• If we have two independent solutions αⁿ and βⁿ, then any linear combination c₁ αⁿ + c₂ βⁿ is also a solution.
• Any sequence satisfying a linear recurrence can be expressed in terms of such roots.
• This gives us a closed-form formula for finding any term of the sequence without computing all the preceding ones.

Key Takeaways

To derive a recurrence equation from a quadratic, replace x with Aₙ₊₂ / Aₙ and express Aₙ₊₂ in terms of Aₙ₊₁ and Aₙ.

The roots of the characteristic equation yield exponential solutions, and their linear combination describes the general linear recurrence sequence — a direct and elegant bridge between algebra and the theory of sequences.