# Find the particular solution of a non-homogeneous recurrence relation

Usually an homogeneous linear recurrence relation of degree $$k$$ with $$k \in\mathbb{Z}$$ of the form

$$u_n = c_1u_{n-1} + c_2u_{n-2} + c_3u_{n-3} + \ldots + c_ku_{n-k}$$

has the characteristic polynomial equation of degree $$k$$ where each $$x$$-variable is raised to the power of the corresponding rank assuming $$n=k$$

$$x^k = c_1x^{k-1} + c_2x^{k-2} + c_3x^{k-3} + \ldots + c_{k-1}x^1 + c_kx^0$$

We know a linear recurrence relation is called non-homogeneous if it is in the form

$$u_n = c_1u_{n-1} + c_2u_{n-2} + c_3u_{n-3} + \ldots + c_ku_{n-k} + f \left(n \right)\quad\text{where}\quad f \left(n \right)\neq 0$$

The solution $$\left(a_n \right)$$ of a non-homogeneous recurrence relation has two parts.

First part is the solution $$\left(a_h \right)$$ of the associated homogeneous recurrence relation (obtained by removing the $$f \left(n \right)$$-part) and the second part is the particular solution $$\left(a_t \right)$$.

The final solution then have this form

$$a_n = a_h + a_t$$

The solution $$\left(a_h \right)$$ is determined by solving the characteristic polynomial equation, but what about the particular solution $$\left(a_t \right)$$?

I am trying to solve the following sequence $$\begin{cases} u_0 &= 1 \\ u_n &= 1.5u_{n-1} + 2n \end{cases}$$

Sketch (for a solution that does everything at once):

Consider

$$u_n=1.5u_{n-1}+2n$$ and $$u_{n-1}=1.5u_{n-2}+2(n-1).$$

Subtracting these from each other gives $$u_n-u_{n-1}=1.5u_{n-1}-1.5u_{n-2}+2$$ or that $$u_n=2.5u_{n-1}-1.5u_{n-2}+2$$

Therefore, $$u_{n-1}=2.5u_{n-2}-1.5u_{n-3}+2.$$

Subtracting these two gives \begin{align*} u_n-u_{n-1}&=(2.5u_{n-1}-1.5u_{n-2}+2)-(2.5u_{n-2}-1.5u_{n-3}+2)\\ &=2.5u_{n-1}-4u_{n-2}+1.5u_{n-3} \end{align*} or that $$u_n=3.5u_{n-1}-4u_{n-2}+1.5u_{n-3}.$$

This last equation can be solved using the standard homogeneous recurrence formula.

The characteristic polynomial is then $$x^3-3.5x^2+4x-1.5=(x-1)^2\left(x-1.5\right).$$ Therefore, the general form for $$u_n$$ is $$u_n=c_1(1)^n+c_2n(1)^n+c_3(1.5)^n=c_1+c_2n+c_3(1.5)^n,$$ where the constants $$c_1$$, $$c_2$$, and $$c_3$$ are to be determined.

Plugging into the first recurrence, we have $$c_1+c_2n+c_3(1.5)^n=1.5(c_1+c_2(n-1)+c_3(1.5)^{n-1})+2n$$ or that $$c_1+c_2n=1.5c_1+1.5c_2n-1.5c_2+2n.$$ Since this equation must be true for any $$n$$, the corresponding coefficients must be equal. In other words, the coefficients without $$n$$'s satisfy $$c_1=1.5c_1-1.5c_2$$ and the coefficients with $$n$$ satisfy $$c_2=1.5c_2+2.$$ In other words, $$c_2=-4$$ and $$c_1=-12$$.

Thus, the solution is of the form $$u_n=-12-4n+c_3(1.5)^n.$$ Finally, using the initial value, $$u_0=1=-12+c_3$$ gives $$c_3=13.$$

Putting this all together, the solution to the recurrence is $$u_n=-12-4n+13(1.5)^n.$$

The homogeneous and particular setup here is a little complicated to express, the $$(1.5)^n$$ would be a solution to the homogeneous (with the initial condition $$u_0=1$$) and $$-12-4n+12(1.5)^n$$ is a solution to the particular with $$u_0=0$$). If you want to use the homogeneous and particular setup, you must be careful about the initial conditions.

• Very nice answer. Thank you. The idea is to get rid of the particular part to get the homogeneous polynomial equation. – eigenslacker Jan 4 at 21:31
• Can the same be applied in a generalized way to arithmetico-geometric sequences such as $u_n=1.5u_{n-1}+1$ with the initial condition $u_0=1$? – eigenslacker Jan 4 at 21:33
• I ask this because some books usually solve for $\alpha=1.5\alpha+1$ and construct an auxiliary sequence $v_n=u_n-\alpha$ – eigenslacker Jan 4 at 21:36
• Sure, it can be used in general (at least when $f(n)$ is a polynomial in $n$). You'll need to change the step where you determine the constants as appropriate. – Michael Burr Jan 4 at 21:36
• Yes, when $f(n)$ is a polynomial, then the characteristic equation that you'll get using this method will be the characteristic equation of the homogeneous system times $(x-1)^{\deg(f)}$. So, it is solving the characteristic polynomial equation of degree $1$ in disguise - this can allow you to skip right to the answer and general form. – Michael Burr Jan 4 at 21:40

Hint:

Obviously the homogeneous solution is of the form $$c\,1.5^n$$. Then we can look for a particular solution with a linear form $$an+b$$.

We have

$$an+b=1.5(a(n-1)+b)+2n$$

and by identification we obtain $$a$$ and $$b$$.

$$-4n-12$$.