N-th term of generating function of almost fibonacci sequence

Question

I've received this task to find the n-th term of a generating function of the following recursive sequence:

$a_0 = 0 ;$

$a_1 = 1 ; $

$a_{n+2} = a_{n+1} + a_n + 2 $

From the first glance, the Fibonacci sequence is visible, but when calculating it further, I've come to a rather complicated function:

$$ a(x) - xa(x) - x^2a(x) = x + \frac{2x^2}{1-x} $$

And further into the form of a(x):

$$ a(x) = \frac{x^2+x}{(1-x)(1-x-x^2)} $$

From this point, I'm quite lost. From the start, I can see that the n-th term of the sequence can be described as:

$$ [x^n]a(x) = F_n+2 \approx \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}+2$$

My question is, how to calculate it from the a(x) formula. Is there a way to somehow disconnect nth Fibonacci from the other part into something like:

$$ a(x) = \frac{1}{1-x-x^2} + ... $$

Answer 1

Hint:   the recurrence can be written as $a_{n+2}+2=(a_{n+1}+2)+(a_n+2)\,$. Let $\,b_n=a_{n}+2\,$ so that $\,b_{n+2}=b_{n+1}+b_n\,$, and let $\,g(x)=\sum_{n \ge 0} b_nx^n\,$, then:

$$ \begin{align} g(x) &= b_0 + b_1x + \sum_{n \ge 0} b_{n+2}x^{n+2} \\ &= b_0 + b_1x + \sum_{n \ge 0} (b_{n+1}+b_n)x^{n+2} \\ &= b_0 + b_1x + x \big(g(x) - b_0\big) + x^2 g(x) \\[5px] &= 2 + 3x + x \big(g(x) - 2\big) + x^2 g(x) \\ \end{align} $$

Therefore $\,g(x) = \dfrac{x+2}{1-x-x^2}\,$.  Let $\,\varphi=\dfrac{1+\sqrt{5}}{2}\,$, then:

$$ \begin{align} \dfrac{1}{1-x-x^2} &= \frac{1}{(1- \varphi x)(1+x/\varphi)} \\[5px] &= \frac{\varphi}{(1- \varphi x)(\varphi+x)} \\[5px] &= \frac{1}{\varphi^2+1}\left( \frac{\varphi^2}{1-\varphi x} + \frac{1}{1+ x / \varphi}\right) \\[5px] &= \frac{\varphi^2}{\varphi^2+1} \sum_{n \ge 0} \varphi^n x^n + \frac{1}{\varphi^2+1} \sum_{n \ge 0} \frac{(-1)^n}{\varphi^n} x^n \end{align} $$

Substituting back into $\,g(x)\,$ gives the general term for $\,b_n\,$, then $\,a_n=b_n-2\,$ follows.