# Can someone check the solution to this recurrence relation?

Here's the recurrence relation: $a_n = 4a_{n−1} − 3a_{n−2} + 2^n + n + 3$ with $a_0 = 1$ and $a_1 = 4$

Here's the solution:Write: $$a_{n + 2} = 4 a_{n + 1} - 3 a_n + 2^n + n + 3 \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{1}{1 - 2 z} + \frac{z}{(1 - z)^2} + 3 \frac{1}{1 - z}$$ This gives: \begin{align*} A(z) &= \frac{1 - 4 z + 9 z^2 - 12 z^3 + 5 z^4} {1 - 8 z + 24 z^2 - 34 z^3 + 23 z^4 - 6 z^5} \\ &= \frac{23}{8} \cdot \frac{1}{1 - 3 z} - \frac{1}{1 - 2 z} + \frac{3}{8} \cdot \frac{1}{1 - z} - \frac{3}{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: $$a_n = \frac{23}{8} \cdot 3^n - 2^n + \frac{3}{8} - \frac{3}{4} \cdot \binom{n + 1}{1} - \frac{1}{2} \cdot \binom{n + 2}{2} = \frac{23}{8} \cdot 3^n - 2^n + \frac{3}{8} - \frac{1}{6} (n^3 + 6 n^2 + 5 n)$$

The problem is that when I check this with Wolfram, it 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 if this was an error or what..thanks!

-
With integrations, you can check for correctness of a proposed answer by differentiating. With recurrences, you can do it by substituting. – André Nicolas Apr 17 '13 at 17:29
How can I check when I only have two values though? I can't check for $a_{n-2}$ ? – tekman22 Apr 17 '13 at 17:31
If $a_k$, for general $k$, is given by a certain formula, you can use that formula to find $a_{n-2}$, $a_{n-1}$, $a_n$. Another way: Calculate what your formula predicts for $a_2$, $a_3$. Calculate what the recurrence gives. If there is a mismatch, you know there is a mistake. If the answers match, with a little luck the formula is correct. – André Nicolas Apr 17 '13 at 17:34

You substituted $n+2$ instead of $n$ in your first step, but forgot to change the powers of $2$, etc. In other words, you should have \begin{align} a_{n + 2} = 4 a_{n + 1} - 3 a_n + 2^{n+2} + (n+2) + 3 \quad a_0 = 1, a_1 = 4 \end{align} instead of \begin{align} a_{n + 2} = 4 a_{n + 1} - 3 a_n + 2^n + n + 3 \quad a_0 = 1, a_1 = 4 \end{align}

-
Damnit. Is there any way you can show me how to correct the rest of it after that minor mistake? Thanks Lord Soth for helping me out.. – tekman22 Apr 17 '13 at 17:34
Well, you may need to recalculate your steps unfortunately. You would have \begin{align} \frac{A(z) - a_0 - a_1 z}{z^2} = 4 \frac{A(z) - a_0}{z} - 3 A(z) + \frac{\color{red}{4}}{1 - 2 z} + \frac{z}{(1 - z)^2} + \color{red}{5} \frac{1}{1 - z}, \end{align} – Lord Soth Apr 17 '13 at 17:46
The changes are in red. I guess you can take it from here using the same ideas. – Lord Soth Apr 17 '13 at 17:46
UNfortunately it was after that initial step that I had trouble recalculating =( – tekman22 Apr 17 '13 at 17:52

But $a_{n+2}=4a_{n+1}−3a_n+2^{n+2}+(n+2)+3\,$!

-
You sure that's 3 factorial? Lord Soth appears to think it's just 3...? – tekman22 Apr 17 '13 at 17:35
@jtm22: No, 3 and ! ending the sentence. – Przemysław Scherwentke Apr 17 '13 at 17:40
Haha thanks. Any way you could help me correct the problem? – tekman22 Apr 17 '13 at 17:43

After the correction others have pointed out in your first line, you do the same z-transform/generating function stuff you did before, the only difference is now your two forcing terms are shifted by two. \begin{align} a_{n + 2} = 4 a_{n + 1} - 3 a_n + 2^{n+2} + (n+2) + 3 \quad a_0 = 1, a_1 = 4 \end{align}

You really only need to figure the generating functions for the following term $$\sum_{n=0}^{\infty} 2^{n+2} z^n = 2^2\sum_{n=0}^{\infty} 2^{n} z^n = \frac{4}{1-2z}$$ What's left is $n+2+3=n+5$, so your last term turns into a $5$ in the denominator, while the second to last stays the same. This gives you

$$\frac{A(z) - a_0 - a_1 z}{z^2} = 4 \frac{A(z) - a_0}{z} - 3 A(z) + \frac{4}{1-2z} + \frac{z}{(1 - z)^2}+ \frac{5}{1 - z}$$

At this point, you should be able to finish of the problem the same way as before: solve for $A(z)$, expand by partial fractions, then inverse transform. It seems that you need help with this step? I didn't do this by hand but used Mathematica quickly:

$$A(z) = \frac{-12 z^4+24 z^3-14 z^2+4 z-1}{(z-1)^3 (2 z-1) (3 z-1)}$$ $$= -\frac{7}{4 (z-1)^2}+\frac{1}{2 (z-1)^3}+\frac{4}{2 z-1}-\frac{39}{8 (3 z-1)}-\frac{19}{8 (z-1)}$$

This is in the same form as your second to last step, just with different coefficients. Match them up in the function forms of $z$ and you have your final answer.

-
That was my problem..going from that the A(z) = step to the "expanding geometric series" step into the solution.. – tekman22 Apr 17 '13 at 18:29
Yeah I'm just confused on how to get from that last step to the $a_n$ solution – tekman22 Apr 17 '13 at 18:41