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.

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!

share|improve this question

2 Answers 2

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

share|improve this answer
    
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*} $$

share|improve this answer
    
but is that solution equivalent to what I found? It looks like it's completely different –  stevenmadden 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? –  stevenmadden Apr 17 '13 at 16:52
    
? You there man? haha –  stevenmadden 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

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.