Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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}$ ? –  stevenmadden 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

3 Answers 3

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}

share|improve this answer
    
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.. –  stevenmadden 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 =( –  stevenmadden Apr 17 '13 at 17:52

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

share|improve this answer
    
You sure that's 3 factorial? Lord Soth appears to think it's just 3...? –  stevenmadden 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? –  stevenmadden 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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.