# 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?

-
Your generating function result and computations are correct, as well as the closed form result. What makes you believe it is wrong ? – Sasha Oct 27 '11 at 14:47
@Sasha,Wolfram Alpha says different... – pedja Oct 27 '11 at 15:02
Yes, I tried computing it and got wrong values – Pedro Oct 27 '11 at 15:03
You mean to $1 + n$? Still no luck – Pedro Oct 27 '11 at 15:41
Do you want a way to find this recurrence or find why your computations are wrong? $a(n)=\frac{1}{6} \left(3 \left(1-\sqrt{3}\right)^n-\sqrt{3} \left(1-\sqrt{3}\right)^n+3 \left(1+\sqrt{3}\right)^n+\sqrt{3} \left(1+\sqrt{3}\right)^n\right)$ If you didnt get the correct result post here. – GarouDan Oct 27 '11 at 15:44

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.

-
Ah, thank you. It seems my error was taking $\frac{1}{1 - 2x - 2x^{2}} = \frac{1}{x - a} \frac{1}{x - b}$ – Pedro Oct 27 '11 at 16:12
@Pedro: You may want to take a look at the comments under this answer. – joriki Oct 27 '11 at 16:35

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$

-
Finish after...have to go now... – GarouDan Oct 27 '11 at 15:59

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

-