Recurrences

Linear recurrence relations with constant coefficients

u₀ = C₀

u₁ = C₁

u_n+2 + a₁u_n+1 + a₂u_n = 0

Characteristic polynomial (auxiliary polynomial): t² + a₁t + a₂ = 0. The roots for this polynomial will be called α and β.

If α ≠ β:

u_n = Aαⁿ + Bβⁿ (n >= 0)

If α = β:

u_n = (Cn + D)αⁿ (n >= 0)

Example 1

u₀ = 0

u₁ = 1

u_n+2 - 5u_n+1 + 6u_n = 0

Our characteristic polynomial is: t² - 5t + 6 = 0. When we solve this equation we get two roots: 3 and 2. So let’s say that α = 3 and β = 2. We can then write our recurrence as: u_n = A3ⁿ + B2ⁿ.

To solve it we will use the values from u₀ and u₁:

u₀ = A3⁰ + B2⁰ = 0 ⇒ A + B = 0.

u₁ = A3¹ + B2¹ = 1 ⇒ 3A + 2B = 1.

If we solve the system we get that A = 1 and B = -1. So the explicit formula is: u_n = 3ⁿ - 2ⁿ.

Example 2

u₀ = -2

u₁ = 1

u_n+2 - 2u_n+1 + u_n = 0

Our characteristic polynomial is: t² - 2t + 1 = 0. When we solve this equation we get a single root: 1. So in this case α = 1. We can then write our recurrence as: u_n = (Cn + D) · 1ⁿ = Cn + D.

To solve it, we will use the values from u₀ and u₁:

u₀ = (C·0 + D) = -2 ⇒ D = -2.

u₁ = (C·1 + D) = 1 ⇒ C + D = 1 ⇒ C = 3.

So the explicit formula is: u_n = (3n - 2).