We have the following recurrence relation:
$b_n=2b_{n-1}+b_{n-2}$
and initial conditions $b_0=0, b_1=2$
I use the generating series method to solve as following:
Let
$B(x)=b_0+b_1x+b_2x^2+...+b_nx^n+...$
$-xB(x)=-b_0x-b_1x^2-...-b_{n-1}x^n-...$
$-x^2B(x)=-b_0x^2-b_1x^3+...-b_{n-2}x^n+...$
After cancelling terms I get
$(1-x-x^2)B(x)=b_0+(b_1-2b_0)x$
And using initial conditions and isolating $B(x)$
$B(x)={2x\over (1-x-x^2)}$
When I factorise the quadratic in the denominator I get roots:
$x_1={-1-\sqrt{5}\over 2}$ and $x_2={-1+\sqrt{5}\over 2}$
I'm having trouble completing the question using partial fractions from this point, I would appreciate if someone could help me out
I am required to use the Generating Series method
Shift indices to get:
$$ b_{n + 2} = 2 b_{n + 1} + b_n $$
Define the generating function:
$$ B(z) = \sum_{n \ge 0} b_n z^n $$
Multiply the recurrence by $z^n$, sum over $n \ge 0$ and recognize the resulting sums:
$$ \frac{B(z) - b_0 - b_1 z}{z^2} = 2 \frac{B(z) - b_0}{z} + B(z) $$
As partial fractions:
$\begin{align} B(z) &= \frac{2z}{1 - 2 z - z^2} \\ &= \frac{\sqrt{2}}{2} \cdot \frac{1}{1 - (1 + \sqrt{2}) z} - \frac{\sqrt{2}}{2} \cdot \frac{1}{1 - (1 - \sqrt{2}) z} \end{align}$
This is just two geometric series:
$\begin{align} b_n &= \frac{\sqrt{2}}{2} \left( (1 + \sqrt{2})^n - (1 - \sqrt{2})^n \right) \end{align}$