# Non-homogeneous recurrence relation

For the recurrence :

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

find the particular solution when F(n) is

a) $2^{n}$

b) $2^{n}(n+1)$

c) $2^{n} + n+1$

Try:

I have just finished homogeneous system and tried to cover non-homogeneous of my own.

I have found the roots of the equation and got as 1 and 2.

For part a): I have found that every relation like this will have a solution of the form

$a_{n} = a_{n}^{h} + a_{n}^{p}$ where the term with h is the solution of the homogeneous relation.

I have found $a_{n}^{h}$ . Can someone help me with the $a_{n}^{p}$ and the other 2 parts.

• For linear recursions with constant coefficients, an inhomogenous part of $r^n$ gives solutions of the form $(an + b)r^n$. Similarily, $nr^n$ gives solutions of the form $(an^2 + bn + c)r^n$. – Arthur Mar 2 '16 at 23:49

## 2 Answers

When $F(n)$ is an expression containing $r^n$ and $r$ is a root of the characteristic equation, a particular solution like $r^n$ will not do as it belongs to the set of homogeneous solutions. Instead, you have to make an ansatz like $nr^n$.

Let's try this for part a). We do $a_n^p = An2^n$, for some constant $A$. Substituting into the recurrence relation, we get $$An2^n = 3A(n-1)2^{n-1}-2A(n-2)2^{n-2}+2^n.$$ Dividing through by $2^{n-2}$, we get $$4An=6An-6A-2An+4A+4$$ which simplifies to $A=2$. Thus $a_n^p = n2^{n+1}$ is a particular solution. The full solution is $a_n = a_n^h+a_n^p$. Just plug in your initial conidtions (if you have any) into this expressions, to get your final solution.

In part b), try the ansatz $a_n^p = (An^2+Bn)2^n$

You should get $A=B=1$.

• I got it what you are trying to say. So, for part c) do I have to divide it into 3 separate terms containing $2^{n}$, n and 1? – max Mar 2 '16 at 23:57
• @max Ok, great! I seem to have forgotten part c). For the term $2^n$ you should be able to take the solution from $a)$. For the $n+1$ term, consider the ansatz $An^2+Bn+C$. – Étienne Bézout Mar 3 '16 at 0:01
• Thank you so much for helping me out. I will be posting the final solution here in a while. Please check it as my book doesn't have any answers :) – max Mar 3 '16 at 0:02
• @max No problem! I saw that I had made a mistake. In part b), it should be $A=B=1$. – Étienne Bézout Mar 3 '16 at 0:19
• @max I'm afraid I have to log out. You can check your answers here if you like: wolframalpha.com/input/…. I have entered part c) as an example. – Étienne Bézout Mar 3 '16 at 0:21

These nonhomogeneous equations are just homogeneous equations in disguise. I'll show you with part (b):

$$a_n = 3~a_{n - 1} - 2~a_{n - 2} + 2^n~(n + 1) \tag{T1}$$

There are 2 nonlinear coefficients, $n~2^n$ and $2^n$, so we need 3 equations to eliminate them:

\begin{align} % a_{n + 2} - 3~a_{n + 1} + 2~a_{n + 0} &= n~2^n + 2^n \\ % a_{n + 3} - 3~a_{n + 2} + 2~a_{n + 1} &= 8~n~2^n + 32~2^n \\ % a_{n + 4} - 3~a_{n + 3} + 2~a_{n + 2} &= 16~n~2^n + 80~2^n % \end{align}

Now eliminate the $2^n$ and $n~2^n$ terms the normal way:

$$a_{n + 4} - 7~a_{n + 3} + 18~a_{n + 2} - 20~a_{n + 1} + 8~a_{n} = 0 \tag{T2}$$

And this is equivalent to your original equation. The characteristic equation of (T1) is

$$P(x) = x^2 - 3~x + 2 = 0$$

and the characteristic equation of (T2) is

$$Q(x) = x^4 - 7~x^3 + 18~x - 20~x + 8 = 0$$

As it turns out with this technique, $P(x)$ is always a factor of $Q(x)$, specifically:

$$Q(x) = (x^2 - 4~x + 4)P(x)$$

which makes finding the roots fairly easy. No guessing needed. You can even use this when $F(n)$ contains other "closed under addition" terms like sine, cosine, arbitrary products of powers and polynomials, and so forth.