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².

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:

$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₀ = 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ⁿ 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.