0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.