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: 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.
A: Let be $a(n)$ a geometric progression, or $a(n)=q^n$
So,
$a(n)=2a(n-1)+2a(n-2)$ becomes
$q^n=2q^{n-1}+2q^{n-2}$
so $q=0$ or
$q^2=2q+2$
So, $q_1=\frac{2+\sqrt{12}}{2}=1+\sqrt{3}$ or $q_2=\frac{2-\sqrt{12}}{2}=1-\sqrt{3}$.
and
$a(n)=bq_1^n+cq_2^n$
$a(0)=1$, $b+c=1$
$a(1)=2$
A: 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
$$
