# I need some help finding my mistake for solving a second order recurrence relation

I have the recurrence relation: $$a_n = a_{n-1} + 2a_{n-2} ; a_0 = 2, a_1=1$$ This is what I did: $$let \ \ g(x) = \sum a_n x^n \ \ then; \\ g(x) -a_0 -a_1x = \sum_{n=2}^\infty a_nx^n \\ \implies g(x) -2 -x = \sum_{n=2}^\infty (a_{n-1} + 2a_{n-2})x^n \\ \implies g(x)-2-x= \sum_{n=2}^\infty a_{n-1}x^n + 2\sum_{n=2}^\infty a_{n-2}x^n \\ \implies g(x)-2-x= x(g(x)-1) + 2x^2g(x)\\ \implies g(x)(1-x-2x^2) = 2\\ \implies g(x) = \frac{2}{1-x-2x^2}; \ \frac{2}{1-x-2x^2}= \frac{2}{3(1+x)} + \frac{4}{3(1-2x)} \\ \implies \frac{2}{3}\sum_{n=0}^\infty (-1)^nx^n + \frac{4}{3}\sum_{n=0}^\infty (2x)^n \\$$ Giving $$a_n = \frac{2}{3}(-1)^n + \frac{4}{3}(2^n) \implies a_n = \frac{2}{3}((-1)^n + 2^{n+1})$$

But when I typed in the original recurrence relation into Wolfram Alpha and into matlab I would get the recurrence relation of: $$a_n = (-1)^n + 2^n$$ And I cannot find my mistake to get this recurrence relation. Any help would be appreciated.

• $\implies g(x)-2-x= x(g(x)-2) + 2x^2g(x)$ , $a_0 = 2$, not $1$ – WW1 Mar 25 '17 at 18:28

@WW1 says it all. You mistook $2$ for $1$ in what is supposed to be
$g(x)−2−x=x(g(x)−2)+2x^2g(x)$
$g(x)=(2-x)/(1-x-2x^2)=(1-2x+1+x)/(1-x-2x^2)$
$g(x)=1/(1+x)+1/(1-2x)$
which you will see, gives the right answer when we work out the Taylor series and read off the coefficients for each power of $x$.