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} + ... $$