Let $a_0=0, a_1=2, a_2=5$. Use generating functions to solve recurrence equation $a_{n+3}= 5a_{n+2} - 7a_{n+1} + 3a_{n} + 2^n$ for $n \geq0$
I came up with $a_n = {(-1)^n + 2^{n+1}}/3$ but I know that is not correct. Thank you for the help.
Asked
Active
Viewed 193 times
1 Answers
1
It may be better for you to detail your steps and find out where you made the error. Key steps you should have are:
Let $\displaystyle f(x) = \sum_{n=0}^{\infty} a_n x^n$. Then we have the recurrence equation as: $$\frac{f(x)-a_0 - a_1 x - a_2 x^2}{x^3} = 5 \frac{f(x)-a_0-a_1x}{x^2}-7\frac{f(x)-a_0}{x}+3f(x) + \sum_{n=0}^{\infty} 2^n x^n $$
On simplification and using the fact that the last term must be $\dfrac1{1-2x}$, you should get.
$$\implies f(x) = \frac{x (11x^2 -9x+2)}{(x-1)^2 (2x-1) (3x-1)} = \frac{3}{2(x-1)}+\frac{2}{(x-1)^2}+\frac{1}{2x-1}-\frac{1}{2(3x-1)}$$
From the partial fraction expansion and binomial theorem, $a_n = -\dfrac32 +2(n+1) - 2^n + \dfrac{3^n}2$.
Macavity
- 46,381