Lesson 9

For example, \[\mathcal{F}(x)=\frac{x}{1-x-x^2}\ .\] Finding the roots of the denominator, we rewrite: \[\mathcal{F}(x)=\frac{x}{(1-\alpha_1x)(1-\alpha_2x)}, \text{ where }\alpha_{1,2}=\frac{1 \pm \sqrt 5}{2}\ .\] In the equality \[\frac{x}{(1-\alpha_1x)(1-\alpha_2x)}=\frac{c_1}{1-\alpha_1x}+\frac{c_2}{1-\alpha_2x}\] we can substitute a pair of values for \(x\) to get two linear equations for \(c_{1}\) and \(c_{2}\). Alternatively, we can bring to a common denominator and substitute \(x=1/\alpha_{1}\) and \(x=1/\alpha_{2}\). Either way, we find \(c_{1}=\frac{1}{\sqrt 5}\) and \(c_{2}=-\frac{1}{\sqrt 5}\). We conclude that \[\mathcal{F}(x)=\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\left(\frac{1}{1-\alpha_1x}-\frac{1}{1-\alpha_2x}\right)\ .\] Expanding each of the two simplest fractions into a series, we get: \[[x^{n}]\mathcal{F}(x)=\frac{1}{\sqrt 5}(\alpha_{1}^{n}-\alpha_{2}^{n})= \frac{1}{\sqrt 5}\left(\left(\frac{1+\sqrt 5}{2}\right)^{n}-\left(\frac{1-\sqrt 5}{2}\right)^{n}\right) \ .\]

from sympy import apart, sqrt
from sympy.abc import x

print(apart(x / (1 - x - x * x), extension=sqrt(5)))

(-5 + sqrt(5))/(5*(2*x - sqrt(5) + 1)) -
(sqrt(5) + 5)/(5*(2*x + 1 + sqrt(5)))

The rational function \(\mathcal{F}(x)=\frac{x}{1-x-x^2}\) was not chosen arbitrarily: it is the generating function of Fibonacci numbers. Why it turned out to be this way will be discussed in the next section.