Until now, we have learned how to handle recurrence relations that are homogenous. In this exercise, we are going to take a look at recurrence relations that come in the form of:
Equations of this form are called inhomogeneous linear recurrence relations because of the f(n) term. Yes, they are still linear relations. Let’s take this equation as an example:
With initial condition:
Here f(n) = n2.
The first step in deriving a closed-form solution is to temporarily ignore the f(n) term, treat the relation as homogeneous, and find its solution. Using techniques from previous exercises, we obtain the following homogeneous solution:
We use superscript h to denote this as the homogenous solution.
We now focus our attention on the f(n) term. Since f(n) is a polynomial of degree two, we can assume that an is proportional to n2 so:
However, before we proceed, we have to account for all powers of n less than two. Therefore our equation becomes:
To find the coefficients A, B, and C, we plug in the equation for an into the recurrence relation. We get:
We can expand to get this:
Grouping terms together:
This equation must be valid for all n. Since A, B, and C are constants, this is only possible if all terms inside the parentheses equal zero.
This yields the following three equations with three unknowns:
We can solve this system of equations to get:
We now have what is called the particular solution, an(p):
The closed-form solution is the sum of the homogeneous solution and the particular solution:
Plugging in the initial condition (a0 = 1) we get:
The final closed-form solution is:
This is the procedure for f(n) being a polynomial. If it were an exponential function or logarithmic, you start by assuming the particular solution is an(p) = Af(n) and continue to solve for the closed-form solution as we did before.
There exists a special case where f(n) is an exponential function of the form rn and its particular solution has a function that also exists in the homogenous solution; in this case, you would multiply by increasing powers of n just as you did for repeated roots to solve for the particular solution.
Instructions
Derive the homogeneous solution for the following recurrence relation:
Check the hint for the answer and hit Run when you’re ready to move on to the next checkpoint.
Derive the particular solution to the previous recurrence relation.
Check the hint for the answer and hit Run when you’re ready to move on to the next checkpoint.
Given the initial condition of a0 = 2 find the closed-form solution and implement it in the Python function closed_form()
.