I want to find formula for n-th element of recursively entered sequence using generating functions. It goes like this $$a_{1} = 0, a_{2} = 1, a_{n+2} = a_{n+1} + a_{n} + 2$$
I rewrite this into generating functions like this:
$$a(x) = x(a(x)) + x^{2}(a(x)) + \frac{2}{1-x}-x-2$$
Then I end up with
$$ a(x) = -\frac{x}{-x^{2}-x+1}$$
I want to split this to partial fractions, but roots of denominator are $$x_{1} = \frac{1+\sqrt{5}}{2}, x_{2} = \frac{1-\sqrt{5}}{2}$$
Problem is I cannot split it and if I could I cannnot say what sequence is generated by generating functions like $$ \frac{A}{x + \frac{1+\sqrt{5}}{2}}, \frac{B}{x + \frac{1-\sqrt{5}}{2}} $$
I'd appriciate any help. Thanks in advance.
As it almost always happens, the problem is in being very precise with the indexes. Start with $$f(x)=\sum\limits_{n=1}a_nx^{n-1}=a_1+a_2x+\sum\limits_{n=3}a_nx^{n-1}=\\ x+\sum\limits_{n=3}(a_{n-1}+a_{n-2}+2)x^{n-1}= x+\sum\limits_{n=3}a_{n-1}x^{n-1}+\sum\limits_{n=3}a_{n-2}x^{n-1}+2\sum\limits_{n=3}x^{n-1}=\\ x+\sum\limits_{n=2}a_{n}x^{n}+\sum\limits_{n=1}a_{n}x^{n+1}+2\sum\limits_{n=2}x^{n}=\\ x+x\sum\limits_{n=2}a_{n}x^{n-1}+x^2\sum\limits_{n=1}a_{n}x^{n-1}+2\sum\limits_{n=2}x^{n}=\\ x+x(f(x)-0)+x^2f(x)+2\left(\frac{1}{1-x}-x-1\right)$$
leading to $$f(x)(1-x-x^2)=x+\frac{2x^2}{1-x}=\frac{x+x^2}{1-x}$$ or $$\color{red}{f(x)=\frac{x+x^2}{(1-x)(1-x-x^2)}}=-\frac{x+x^2}{(1-x)\left(x+\frac{1+\sqrt{5}}{2}\right)\left(x+\frac{1-\sqrt{5}}{2}\right)}=...$$ let's note by $\varphi=\frac{1+\sqrt{5}}{2}$ and $\psi=\frac{1-\sqrt{5}}{2}$ $$...=-\frac{1}{\sqrt{5}(1+\psi)(x+\psi)} + \frac{1}{\sqrt{5}(1+\varphi)(x+\varphi)} - \frac{2}{(1+\psi)(1+\varphi)(1-x)}=\\ -\frac{1}{\sqrt{5}\psi(1+\psi)\left(1+\frac{x}{\psi}\right)} + \frac{1}{\sqrt{5}\varphi(1+\varphi)\left(1+\frac{x}{\varphi}\right)} - \frac{2}{(1+\psi)(1+\varphi)(1-x)}=\\ -\frac{1}{\sqrt{5}\psi(1+\psi)}\sum\limits_{n=1}\left(-\frac{x}{\psi}\right)^{n-1}+\frac{1}{\sqrt{5}\varphi(1+\varphi)}\sum\limits_{n=1}\left(-\frac{x}{\varphi}\right)^{n-1}-\frac{2}{(1+\psi)(1+\varphi)}\sum\limits_{n=1}x^{n-1}=\\ \sum\limits_{n=1}\left(-\frac{1}{\sqrt{5}\psi(1+\psi)}\cdot \left(-\frac{1}{\psi}\right)^{n-1} +\frac{1}{\sqrt{5}\varphi(1+\varphi)}\cdot \left(-\frac{1}{\varphi}\right)^{n-1} -\frac{2}{(1+\psi)(1+\varphi)} \right)x^{n-1}$$ thus $$\color{red}{a_n=}-\frac{1}{\sqrt{5}\psi(1+\psi)}\cdot \left(-\frac{1}{\psi}\right)^{n-1} +\frac{1}{\sqrt{5}\varphi(1+\varphi)}\cdot \left(-\frac{1}{\varphi}\right)^{n-1} -\frac{2}{(1+\psi)(1+\varphi)}=\\ \color{red}{\left(1+\frac{2}{\sqrt{5}}\right)\cdot \left(-\frac{1}{\psi}\right)^{n-1} +\left(1-\frac{2}{\sqrt{5}}\right)\cdot \left(-\frac{1}{\varphi}\right)^{n-1} -2}$$ and to confirm $$a_1=\left(1+\frac{2}{\sqrt{5}}\right)\cdot 1 +\left(1-\frac{2}{\sqrt{5}}\right)\cdot 1 -2=0$$ $$a_2=\left(1+\frac{2}{\sqrt{5}}\right)\cdot \left(-\frac{1}{\psi}\right) +\left(1-\frac{2}{\sqrt{5}}\right)\cdot \left(-\frac{1}{\varphi}\right) -2=1$$ $$a_3=3$$