Learn

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:

(r2)2(r+3)=0\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 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:

an=α2n+β2n+γ(3)na_n = \alpha 2^n + \beta 2^n + \gamma (-3)^n

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

an=(α+β)2n+γ(3)na_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 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:

an=α2n+βn2n+γ(3)na_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:

an=an1+8(an2)12(an3)a_n = a_{n-1} + 8(a_{n-2}) - 12(a_{n-3})

If we use initial conditions of a0 = 7, a1 = 10, a2 = 62, we obtain the following closed-form solution:

an=5(2n)+3n(2n)+2(3)na_n = 5(2^n) + 3n(2^n) + 2(-3)^n

Instructions

1.

Given the following recurrence relation:

an=10(an1)24(an2)32(an3)+128(an4)a_n = 10(a_{n-1}) - 24(a_{n-2}) - 32(a_{n-3})+128(a_{n-4})

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.

2.

Compute the roots, r_1 and r_2, of the characteristic equation. Take note of the multiplicity of each root.

3.

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.

Take this course for free

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?