# 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

For the first recurrence, define $A(z) = \sum_{n \ge 0} a_n z^n$, write so there aren't subtractions in indices: $$a_{n + 2} = 3 a_{n + 1} - 2 a_n + (n + 2)^2 \cdot 2^{n + 2}$$ If you multiply by $z^n$, sum over $n \ge 0$, you need sums like: \begin{align} \sum_{n \ge 0} a_{n + k} z^n &= \frac{A(z) - a_0 - a_1 z - \ldots - a_{k - 1} z^{k - 1}}{z^k} \\ \sum_{n \ge 0} n \cdot 2^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - 2 z} \end{align} The result is: $$\frac{A(z) - a_0 - a_1 z}{z^2} = 3 \frac{A(z) - a_0}{z} - 2 A(z) + \frac{16 -56 z + 144 z^2 - 128 z^3}{(A1 - 2 z)^3}$$ Splitting the result as partial fractions: $$A(z) = \frac{18 - a_0 + a_1}{1 - 2 z} + \frac{4}{(1 - 2 z)^2} - \frac{10}{(1 - 2 z)^3} + \frac{4}{(1 - 2 z)^4} - \frac{24 - 2 a_0 + a_1}{1 - z} + 8$$ The coefficients can now be read off by the generalized binomial theorem for negative integer powers: $$(1 + u)^{-m} = \sum_{k \ge 0} \binom{-m}{k} u^k = \sum_{k \ge 0} \binom{k + m - 1}{m - 1} (-1)^k u^k$$

-

For the first question, the techniques that Wilf's "generatingfunctionology" present in the second chapter make the solving of such routine.

-