# Finding Particular Solutions to Non-Homogeneous Recurrence Relations

Could anyone assist me in solving the following recurrence relations?

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

$b_n = -nb_{n-1} + n!$

Specifically, I am not sure how to find the particular solutions to such relations once a homogeneous solution is given?

-
Are there any initial conditions? –  fidbc Apr 7 '13 at 2:18
There are not actually. –  user71354 Apr 7 '13 at 2:25

The last part of this answer tells you how to deal with the first problem.

For the second, we need initial conditions. If $b_0=0$, however, you can do it almost by inspection: taking $b_0=0$ generates the sequence $\langle 0,1!,0,3!,0,5!,\dots\rangle$, and it’s not hard to guess and then show by induction that

$$b_n=\begin{cases}0,&\text{if }n\text{ is even}\\n!,&\text{if }n\text{ is odd}\end{cases}$$

is a solution. In fact, you can extend that idea to get a general solution:

\begin{align*} &b_0=b_0\\ &b_1=-b_0+1!\\ &b_2=2b_0-2!+2!=2!b_0\\ &b_3=-3!b_0+3!\\ &b_4=4!b_0-4!+4!=4!b_0\;, \end{align*}

and you can guess and prove by induction that in general

$$b_n=\begin{cases} n!b_0,&\text{if }n\text{ is even}\\ -n!b_0+n!,&\text{if }n\text{ is odd}\;. \end{cases}$$

Added: It just occurred to me that we could also change the variable. Let $c_n=\frac{b_n}{n!}$; then after division by $n!$ the recurrence $b_n=-nb_{n-1}+n!$ can be written $c_n=-c_{n-1}+1$. This recurrence can easily be solved by any number of techniques, and then it’s just a matter of restoring $b_n$ by multiplying by $n!$.

-
If no initial conditions exist is there a way to improvise? –  user71354 Apr 7 '13 at 2:32
@user71354: Yes, in this case: see the addition that I just made after thinking about it a little more. –  Brian M. Scott Apr 7 '13 at 2:34
Bravo, that pattern eluded me! –  user71354 Apr 7 '13 at 2:38