Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Are there any initial conditions? – fidbc Apr 7 '13 at 2:18
There are not actually. – user71354 Apr 7 '13 at 2:25
up vote 1 down vote accepted

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!$.

share|cite|improve this answer
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 $$

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.