<s>[INST] Problem with generating functions and binary recurrences I am considering the following recurrence:
$a_0 = 1$;
$a_1 = 2$
$a_{n} = 2 (a_{n - 1} + a_{n - 2})$
Then I proceeded with the generating function:
$F(x) = \displaystyle\sum_{n = 0}^\infty a_n x^n = 1 + 2x + \displaystyle\sum_{n = 2}^\infty  a_{n} x^{n} = 1 + 2x + \displaystyle\sum_{n = 2}^\infty 2x^n(a_{n - 1} + a_{n - 2})$
$F(x) = 1 + 2x + \displaystyle\sum_{n = 2}^{\infty} 2x^{n} a_{n - 1} + \displaystyle\sum_{n = 2}^{\infty} 2x^{n} a_{n - 2}$
$F(x) = 1 + 2x + (2x \displaystyle\sum_{n = 2}^{\infty} x^{n - 1} a_{n - 1}) + (2x^{2} \displaystyle\sum_{n = 2}^{\infty} x^{n - 2} a_{n - 2})$
$F(x) = 1 + 2x + 2x(F(x) - 1) + 2x^{2}F(x)$
$F(x) = \frac{1}{1 - 2x - 2x^{2}}$ Let a, b be the roots of the quadratic.
$F(x) = \frac{1}{(x - a)(x - b)} = \displaystyle\sum_{n = 0}^{\infty} \frac{x^{n}(b^{-1 - n} - a^{-1 - n})}{\sqrt{3}}$
We should then have $a_{n} = \frac{b^{-1 - n} - a^{-1 - n}}{\sqrt{3}}$, but I know that this is false. Where have I gone wrong?
 [/INST] OK, using the recurrence equation $a_0 = 1$, $a_1=2$, $a_2 = 6$, $a_3 = 16$, $a_4 = 44$ and $a_5=120$. 
Verifying this with the generating function directly:
$$
  \frac{1}{1-2x - 2x^2} \sim \sum_{k=0}^5 (2 x+2 x^2)^k \sim 1+ 2x + 6 x^2 + 16 x^3 + 44 x^4 + 120 x^5 + o(x^5)
$$
Now using roots of the denominator $1-2x-2x^2 = -2( x - a)(x-b)$, where $a= -\frac{1}{2} - \frac{\sqrt{3}}{2}$ and $b= -\frac{1}{2} + \frac{\sqrt{3}}{2}$. Therefore
$$
   \frac{1}{1-2x-2x^2 } = -\frac{1}{2}\frac{1}{x-a}\frac{1}{x-b}=-\frac{1}{2(a-b)} \left( \frac{1}{x-a} - \frac{1}{x-b} \right)
$$
It is readily seen that $-\frac{1}{2(a-b)} = \frac{1}{2 \sqrt{3}}$ we thus get
$$
  \frac{1}{1-2x-2x^2 } = \sum_{n=0}^\infty x^n \frac{1}{2 \sqrt{3}} \left( -a^{-n-1} + b^{-n-1} \right)
$$ 
Now check with WolframAlpha again, and scroll to the alternative forms.
</s>