Help solving recursive relations

Question

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$

How would you solve this recursive relation? I have the homogenous solution, but am having issues with the in-homogenous one.

Answer 1

For the $n^2$ part you have $An^2+Bn+C$ for a specific solution - equate coefficients.

For the $5^n$ part you need to look at $Dn^{r}5^n$ where $r$ is the multiplicity of $5$ as a root of $x^2-x-20=0$ - here you already have $5^n$ in your solution of the homogeneous part.

Answer 2

You can use generating functions. Define $X(z) = \sum_{n \ge 0} x_n z^n$, multiply your recurrence by $z^n$ and sum over $n \ge 0$ to get after recognizing some sums: $$ \frac{X(z) - x_0 - x_1 z}{z^2} = \frac{X(z) - x_0}{z} + 20 X(z) + \sum_{n \ge 0} n^2 z^n + \sum_{n \ge 0} 5^n z^n $$ For the troublesome sums remaining: \begin{align} \sum_{n \ge 0} n^2 z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \left(z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \right) \\ &= \frac{z + z^2}{(1 - z)^3} \\ \sum_{n \ge 0} 5^n z^n &= \frac{1}{1 - 5 z} \end{align} Plug all this in, solve for $X(z)$ as partial fractions: \begin{align} X(z) &= \frac{z^2 - 2 z^3 - z^4 - 6 z^5} {1 - 9 z + 6 z^2 + 126 z^3 - 339 z^4 + 315 z^5 - 100 z^6} \\ &= \frac{1}{45} \cdot \frac{1}{(1 - 5 z)^2} - \frac{313}{12960} \cdot \frac{1}{1 - 5 z} + \frac{98}{10125} \cdot \frac{1}{1 + 4 z} - \frac{1}{10} \cdot \frac{1}{(1 - z)^3} + \frac{29}{200} \cdot \frac{1}{(1 - z)^2} - \frac{211}{4000} \cdot \frac{1}{1 - z} \end{align} You want the coefficient of $z^n$ in this, which can be computed term-by-term by using the generatlized binomial theorem, for $m \in \mathbb{N}$ it gives: $$ (1 + u)^{-m} = \sum_{k \ge 0} \binom{-m}{k} u^k = \sum_{k \ge 0} (-1)^k \binom{k + m - 1}{m - 1} u^k $$ Also note that the binomial coefficients are just $m - 1$ degree polynomials in $k$.