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:
Because the degree of this polynomial is three, we require three independent functions of the form rn.
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:
Would be invalid as the equation would reduce to only having two independent functions:
To remedy this, we simply multiply the roots with multiplicity greater than one by increasing powers of n, starting with n0 = 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:
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:
If we use initial conditions of a0 = 7, a1 = 10, a2 = 62, we obtain the following closed-form solution:
Given the following recurrence relation:
Derive the characteristic equation. Take note of its degree.
Check the hint for the answer and hit Run when you’re ready to move on to the next checkpoint.
Compute the roots,
r_2, of the characteristic equation. Take note of the multiplicity of each root.
Taking into account the multiplicity of each root, compose the final closed-form solution and implement it in the Python function
closed_form(). The boundary conditions are:
- a0 = 4
- a1 = 22
- a2 = 180
- a3 = 1144.
As this will yield a system of equations of four equations and four unknowns, you may use a mathematical tool (such as Wolfram Alpha or MATLAB) to solve the equations for you.