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:

`$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k} + f(n)$`

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:

`$a_n = 3a_{n-1} + n^2$`

With initial condition:

`$a_0 = 1$`

Here *f(n) = n ^{2}*.

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:

`$a_{n}^{(h)} = \alpha 3^n$`

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 *a _{n}* is proportional to

*n*so:

^{2}`$a_n = An^2$`

However, before we proceed, we have to account for all powers of *n* less than two. Therefore our equation becomes:

`$a_n = An^2 + Bn + C$`

To find the coefficients *A*, *B*, and *C*, we plug in the equation for *a _{n}* into the recurrence relation. We get:

`$An^2 + Bn + C = 3(A(n-1)^2 + B(n-1) + C) + n^2$`

We can expand to get this:

`$An^2 + Bn + C = 3A(n^2 - 2n + 1) + 3B(n-1) + 3C + n^2$`

`$An^2 + Bn + C = 3An^2 - 6An + 3A + 3Bn - 3B + 3C + n^2$`

Grouping terms together:

`$An^2 + Bn + C = (3A+1)n^2 + (-6A+3B)n + (3A - 3B + 3C)$`

`$0 = (2A+1)n^2 + (-6A+2B)n + (3A - 3B + 2C)$`

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:

`$2A + 1 = 0$`

`$-6A+2B = 0$`

`$3A - 3B + 2C = 0$`

We can solve this system of equations to get:

`$A = -\frac{1}{2}$`

`$B = -\frac{3}{2}$`

`$C = -\frac{3}{2}$`

We now have what is called the *particular solution*, *a _{n}^{(p)}*:

`$a_{n}^{(p)} = -\frac{1}{2} n^2 - \frac{3}{2} n - \frac{3}{2}$`

The closed-form solution is the sum of the homogeneous solution and the particular solution:

`$a_n = a_{n}^{(h)} + a_{n}^{(p)}$`

`$a_n = \alpha 3^n - \frac{1}{2} n^2 - \frac{3}{2} n - \frac{3}{2}$`

Plugging in the initial condition (*a _{0} = 1*) we get:

`$1 = \alpha - \frac{3}{2}$`

`$\alpha = \frac{5}{2}$`

The final closed-form solution is:

`$a_n =\frac{5}{2}3^n - \frac{1}{2} n^2 - \frac{3}{2} n - \frac{3}{2}$`

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 *a _{n}^{(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 *r ^{n}* 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

**1.**

Derive the homogeneous solution for the following recurrence relation:

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

Check the hint for the answer and hit **Run** when you’re ready to move on to the next checkpoint.

**2.**

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.

**3.**

Given the initial condition of *a _{0} = 2* find the closed-form solution and implement it in the Python function

`closed_form()`

.