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?

A simpler way to handle such is to write the recurrence as:
$$
a_{n + 2} = 2 (a_{n + 1} + a_n)
$$
multiply by $x^n$, sum over $n \ge 0$. Recognize the sums that result:
$$
\frac{A(x) - a_0 -a_1 z}{z^2}
  = 2 \left( \frac{A(x) - a_0}{x} + A(x) \right)
$$
Plugging in $a_0 = 1$ and $a_1 = 2$, solving for $A(z)$:
$$
A(z) = \frac{1}{1 - 2 z - 2 z^2}
     = \frac{3 + \sqrt{3}}{6} \frac{1}{1 - (1 + \sqrt{3}) x}
         - \frac{3 - \sqrt{3}}{6} \frac{1}{1 - (1 - \sqrt{3}) x}
$$
This is just two geometric series:
$$
a_n = \frac{3 + \sqrt{3}}{6} \cdot (1 + \sqrt{3})^n
        - \frac{3 - \sqrt{3}}{6} \cdot (1 - \sqrt{3})^n
$$
