<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] 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$
</s>