Guessing particular solution for a recurrence relation with multiple quasi-polynomials on the right side

Question

I'm trying to solve this recurrence: $$a_{n+2}+2a_{n+1}-3a_{n}=n+n(-3)^{n-1},\ a_0=0, a_1=1$$

However, the algorithm in my textbook doesn't seem to mention this case with multiple quasi-polynomials on the right side. How should I gues the particular solution?

Answer 1

Use linearity. The solution will be of the form $a_n = A(n) + B(n) + C(n)$ where $a_n = A(n)$ is a solution of the recurrence with right-hand-side $n$, $a_n = B(n)$ is a solution of the recurrence with right-hand-side $n (-3)^{n-1}$, and $a_n = C(n)$ is a solution of the homogeneous recurrence (i.e. with right-hand-side $0$).

Answer 2

For the record, generating functions solve this type of problems in uniform way. Define $A(z) = \sum_{n \ge 0} a_n z^n$; take your recurrence, multiply by $z^n$ and add over $n \ge 0$:

$\begin{align} \sum_{n \ge 0} a_{n + 2} z^n + 2 \sum_{n \ge 0} a_{n + 1} z^n - 3 \sum_{n \ge 0} a_n z^n &= \sum_{n \ge 0} n z^n + \sum_{n \ge 0} (-1)^n n 3^n z^n \end{align}$

You know that for $\lvert \alpha z \rvert < 1$:

$\begin{align} \sum_{n \ge 0} \alpha^n z^n &= \frac{1}{1 - \alpha z} \\ \sum_{n \ge 0} n \alpha^n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - \alpha z} \\ &= \frac{\alpha z}{(1 - \alpha z)^2} \end{align}$

Thus recognizing the above sums:

$\begin{align} \frac{A(z) - a_0 - a_1 a}{z^2} + 2 \frac{A(z) - a_0}{z} - 3 A(z) &= \frac{z}{(1 - z)^2} - \frac{3 z}{(1 + 3 z)^2} \end{align}$

Using the initial values and solving for $A(z)$:

$\begin{align} A(z) &= \frac{z + 4 z^2 - 4 z^3 + 15 z^4}{(1 - z)^3 (1 + 3 z)^3} \\ &= \frac{1}{4} \cdot \frac{1}{(1 - z)^3} - \frac{9}{16} \cdot \frac{1}{(1 - z)^2} + \frac{17}{32} \cdot \frac{1}{1 - z} \\ &\qquad + \frac{1}{12} \cdot \frac{1}{(1 + 3 z)^3} - \frac{11}{48} \cdot \frac{1}{(1 + 3 z)^2} - \frac{7}{96} \cdot \frac{1}{1 + 3 z} \end{align}$

Remember the generalized binomial theorem's special cases:

$\begin{align} (1 - \alpha z)^{-m} &= \sum_{k \ge 0} (-1)^k \binom{-m}{k} z^k \\ &= \sum_{k \ge 0} \binom{k + m - 1}{m - 1} z^k \end{align}$

Note that $\binom{k + m - 1}{m - 1}$ is a polynomial of degree $m - 1$ in $k$. You can read off the coefficients:

$\begin{align} a_n &= \frac{1}{4} \binom{n + 3 - 1}{3 - 1} - \frac{9}{16} \binom{n + 2 - 1}{2 - 1} + \frac{17}{32} \binom{n + 1 - 1}{1 - 1} + \frac{1}{12} \binom{n + 3 - 1}{3 - 1} \cdot (-3)^n - \frac{11}{48} \binom{n + 2 - 1}{2 - 1} \cdot (-3)^n - \frac{7}{96} \binom{n + 1 - 1}{1 - 1} \cdot (-3)^n \\ &= \frac{(4 n^2 - 10 n - 21) \cdot (-3)^n + (12 n^2 - 18 n + 1602)}{96} \end{align}$

I thank my tame CAS, maxima for doing the routine algebra. Any transcription errors are mine alone.