Calculus – Sequences and series – A generating function for the Fibonacci numbers

Earlier we have seen that the sequence of Fibonacci numbers \(1,1,2,3,5,8,13,21,34,55,89,\ldots\) is defined by \(F_{n+2}=F_n+F_{n+1}\) for \(n=1,2,3,\ldots\) with \(F_1=F_2=1\).

For computational reasons we use \(F_{n+2}=F_n+F_{n+1}\) for \(n=0,1,2,\ldots\) with \(F_0=0\) and \(F_1=1\) instead.

Now we consider the generating function \(G(x)=\displaystyle\sum_{n=1}^{\infty}F_nx^n=\sum_{n=0}^{\infty}F_nx^n\), then we have

\[x^2G(x)=\sum_{n=0}^{\infty}F_nx^{n+2}=\sum_{n=0}^{\infty}F_{n+2}x^{n+2}-\sum_{n=0}^{\infty}F_{n+1}x^{n+2} =\sum_{n=1}^{\infty}F_nx^n-F_1x-x\sum_{n=1}^{\infty}F_nx^n=G(x)-x-xG(x).\]

This implies that

\[(1-x-x^2)G(x)=x\quad\Longrightarrow\quad G(x)=\frac{x}{1-x-x^2}.\]

In order to find the radius of convergence we apply the ratio test: for \(x\neq0\) let \(a_n=F_nx^n\), then we have:

\[\lim\limits_{n\to\infty}\left|\frac{a_{n+1}}{a_n}\right|=\lim\limits_{n\to\infty}\left|\frac{F_{n+1}x^{n+1}}{F_nx^n}\right| =\lim\limits_{n\to\infty}\frac{F_{n+1}}{F_n}|x|=\varphi|x|,\]

where \(\displaystyle\lim\limits_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi=\frac{1+\sqrt{5}}{2}\approx1.618\) denotes the golden ratio.

Now the ratio test implies that the generating series is absolutely convergent if \(|x| < \displaystyle\frac{1}{\varphi}=\varphi-1\approx0.618\).

For instance, this implies that \(\displaystyle\sum_{n=1}^{\infty}\frac{F_n}{2^n}=G(\tfrac{1}{2})=\frac{\frac{1}{2}}{1-\frac{1}{2}-\frac{1}{4}}=2\).

Differentiation leads to

\[\sum_{n=1}^{\infty}nF_nx^{n-1}=G'(x)=\frac{1-x-x^2+x+2x^2}{(1-x-x^2)^2}=\frac{1+x^2}{(1-x-x^2)^2}.\]

For instance, this implies that \(\displaystyle\sum_{n=1}^{\infty}\frac{nF_n}{2^n}=\tfrac{1}{2}G'(\tfrac{1}{2})=\frac{1+\frac{1}{4}}{2\left(1-\frac{1}{2}-\frac{1}{4}\right)^2}=10\).

Differentiating once more we obtain

\begin{align*} \sum_{n=2}^{\infty}n(n-1)F_nx^{n-2}=G''(x)&=\frac{2x(1-x-x^2)^2-2(1-x-x^2)(-1-2x)(1+x^2)}{(1-x-x^2)^4}\\[2.5mm] &=\frac{2(x-x^2-x^3+1+x^2+2x+2x^3)}{(1-x-x^2)^3}=\frac{2(1+3x+x^3)}{(1-x-x^2)^3}. \end{align*}

For instance, this implies that \(\displaystyle\sum_{n=2}^{\infty}\frac{n(n-1)F_n}{2^n}=\tfrac{1}{4}G''(\tfrac{1}{2})=\frac{2\left(1+\frac{3}{2}+\frac{1}{8}\right)}{4\left(1-\frac{1}{2}-\frac{1}{4}\right)^3}=84\).

Finally, let's try to solve \(G(x)=1\) with \(\displaystyle|x|<\frac{1}{\varphi}=\varphi-1\approx0.618\):

\[\frac{x}{1-x-x^2}=1\quad\Longleftrightarrow\quad x=1-x-x^2\quad\Longleftrightarrow\quad(x+1)^2=2\quad\Longleftrightarrow\quad x=-1\pm\sqrt{2}.\]

Since \(\sqrt{2}-1\approx0.414\) this leads to the remarkable result that \(\displaystyle\sum_{n=1}^{\infty}\left(\sqrt{2}-1\right)^nF_n=1\).

---

Last modified on March 15, 2021