## Linear recurrence relations with constant coefficients

u0 = C0

u1 = C1

un+2 + a1un+1 + a2un = 0

Characteristic polynomial (auxiliary polynomial): t2 + a1t + a2 = 0. The roots for this polynomial will be called α and β.

If α ≠ β:

un = Aαn + Bβn (n >= 0)

If α = β:

un = (Cn + D)αn (n >= 0)

### Example 1

u0 = 0

u1 = 1

un+2 - 5un+1 + 6un = 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: un = A3n + B2n.

To solve it we will use the values from u0 and u1:

u0 = A30 + B20 = 0 ⇒ A + B = 0.

u1 = A31 + B21 = 1 ⇒ 3A + 2B = 1.

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

### Example 2

u0 = -2

u1 = 1

un+2 - 2un+1 + un = 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: un = (Cn + D) · 1n = Cn + D.

To solve it, we will use the values from u0 and u1:

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

u1 = (C·1 + D) = 1 ⇒ C + D = 1 ⇒ C = 3.

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