Solving non-homogeneous recurrence relationships with exponents

Question

Find all solutions of the recurrence relation $a_n = 2a_{n-1} + 2n^2$.

I am having trouble with coming up with a guess for $2n^2$. Would it just be $an^2 + bn + c$?

I feel like there's an easier way based on ways to solve other recurrances.

Answer 1

If you're familiar with the $Z$-transform you can find a systematic way to solve these kind of relations. Otherwise, a guess of the form

$$ a_n = \alpha + \beta n + \gamma n^2 + \delta 2^{n} $$

The actual solution is

$$ a_n = \left(\frac{a_1}{2} + 11\right) 2^n - 2 n^2 - 8 n -12 $$

Answer 2

This is a linear recurrence of the first order. Try dividing by $2^n$:

$$ \frac{a_n}{2^n} - \frac{a_{n - 1}}{2^{n - 1}} = \frac{n^2}{2^{n - 1}} $$

You see that you can sum over $n$, the left hand side nicely telescopes:

$$ \sum_{2 \le k \le n} \left(\frac{a_k}{2^k} - \frac{a_{k - 1}}{2^{k - 1}}\right) = \sum_{2 \le k \le n} \frac{k^2}{2^{k - 1}} \\ \frac{a_n}{2^n} - \frac{a_1}{2} = \sum_{0 \le k \le n} \frac{k^2}{2^{k - 1}} - 1\\ a_n = a_1 \cdot 2^{n - 1} - 2^n + 2^{n + 1} \sum_{0 \le k \le n} \frac{k^2}{2^k} $$

For the later sum, note that:

$$ \sum_{0 \le k \le n} z^k = \frac{z^{n + 1} - 1}{z - 1} \\ z \frac{d}{d z} \sum_{0 \le k \le n} z^k = \sum_{0 \le k \le n} k z^k \\ $$

Apply the above twice, and then substitute $z = 1/2$ to get:

$$ \sum_{0 \le k \le n} \frac{k^2}{2^k} = \frac{3 \cdot 2^{n + 1} - n^2 - 4 n - 6}{2^n} $$

This above gives:

$$ a_n = \left(\frac{a_1}{2} + 11\right) \cdot 2^n - 2 n^2 - 8 n - 12 $$