In the previous exercise, we learned how to obtain the closed-form solution for a recurrence relation whose characteristic equation had real and distinct roots. In this exercise, we will learn how to handle repeated roots. Consider the following characteristic equation:

$\left (r-2  \right )^2\left ( r+3 \right ) = 0$

Because the degree of this polynomial is three, we require three independent functions of the form rⁿ.

Unfortunately, the root r = 2 is repeated twice. We say this root has a multiplicity of two. When solving for the roots of a polynomial equation, online calculators such as Wolfram Alpha will reveal the multiplicity of each root for you. You simply type in: roots: “polynomial equation goes here” and it will return the roots and their multiplicities.

For our previous equation, attempting to write a closed-form solution like this:

$a_n = \alpha 2^n + \beta 2^n + \gamma (-3)^n$

Would be invalid as the equation would reduce to only having two independent functions:

$a_n =\left (\alpha + \beta  \right ) 2^n + \gamma (-3)^n$

To remedy this, we simply multiply the roots with multiplicity greater than one by increasing powers of n, starting with n⁰ = 1. Again, we state this without proof as the proof is complex and merits its own lesson.

For example, for the above equation we would have:

$a_n = \alpha 2^n + \beta n 2^n + \gamma (-3)^n$

As we did before, we plug in our initial conditions to find the coefficients for the closed-form solution.

The previous characteristic equation came from the following linear recurrence relation:

$a_n = a_{n-1} + 8(a_{n-2}) - 12(a_{n-3})$

If we use initial conditions of a₀ = 7, a₁ = 10, a₂ = 62, we obtain the following closed-form solution:

$a_n = 5(2^n) + 3n(2^n) + 2(-3)^n$