# Finding this solution to a recurrence relation

So, I know that the recurrence relation $a_n = 4a_{n−1} − 3a_{n−2} + 2^n + n + 3$ with $a_0 = 1$ and $a_1 = 4$ has the solution of $a_n = -4(2^n) - n^2 / 4 - 5n / 2 + 1/8 + (39/8)(3^n)$. I just wanted to know how we arrived at this solution. Thank you!

-

Hint: Set $b_n=a_n+\alpha 2^{n}$ and choose $\alpha$ such that all powers of 2 disappear ($\alpha=4$).

-
This turns the recurrence relation into $b_n = 4b_{n-1} - 3b_{n-2} + n + 3,$ but that still needs solving. – ShreevatsaR Apr 17 '13 at 19:21
@ShreevatsaR: I think this kind of equations is well-known! – Boris Novikov Apr 17 '13 at 19:35

Write: $$a_{n + 2} = 4 a_{n + 1} - 3 a_n + 4 \cdot 2^n + n + 5 \quad a_0 = 1, a_1 = 4$$ Define $A(z) = \sum_{n \ge 0} a_n z^n$. If you multiply the recurrence by $z^n$ and sum over $n \ge 0$ you get: $$\frac{A(z) - a_0 - a_1 z}{z^2} = 4 \frac{A(z) - a_0}{z} - 3 A(z) + \frac{4}{1 - 2 z} + \frac{z}{(1 - z)^2} + 5 \frac{1}{1 - z}$$ This gives: \begin{align*} A(z) &= \frac{1 - 4 z + 14 z^2 - 24 z^3 + 12 z^4} {1 - 8 z + 24 z^2 - 34 z^3 + 23 z^4 - 6 z^5} \\ &= \frac{39}{8} \cdot \frac{1}{1 - 3 z} - 4 \cdot \frac{1}{1 - 2 z} + \frac{19}{8} \cdot \frac{1}{1 - z} - \frac{7}{4} \cdot \frac{1}{(1 - z)^2} - \frac{1}{2} \cdot \frac{1}{(1 - z)^3} \end{align*} Expanding the geometric series, and also: $$(1 - z)^{-k} = \sum_{n \ge 0} (-1)^n \binom{-k}{n} z^n = \sum_{n \ge 0} \binom{n + k - 1}{k - 1} z^n$$ gives: \begin{align*} a_n &= \frac{39}{8} \cdot 3^n - 4 \cdot 2^n + \frac{19}{8} - \frac{7}{4} \cdot \binom{n + 1}{1} - \frac{1}{2} \cdot \binom{n + 2}{2} \\ &= \frac{39}{8} \cdot 3^n - 4 \cdot 2^n - \frac{1}{8} (2 n^2 + 20 n - 1) \end{align*}

-
but is that solution equivalent to what I found? It looks like it's completely different – tekman22 Apr 17 '13 at 16:50
also, the original equation looks to be copied differently - it's $3a_{n-2}$ whereas you wrote $3a_n$. Is this just a typo or was it calculated using that value? – tekman22 Apr 17 '13 at 16:52
? You there man? haha – tekman22 Apr 17 '13 at 17:19
@jtm22, it seems my algebra is messed up today... fixed now. Thanks for the patience. – vonbrand Apr 17 '13 at 20:13