1
$\begingroup$

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.

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

@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)$

Checking:

$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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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