Fibonacci series

In “Probabilizing Fibonacci Numbers” Persi Diaconis recalls asking Ron Graham to help him make his undergraduate number theory class more fun. Persi asks about the chance a Fibonacci number is even and whether infinitely many Fibonacci numbers are prime. After answering “1/3” and “no one knows” to Persi’s questions, Ron suggests giving the undergrads the following problem:

\( \displaystyle{\sum_{n=1}^\infty \frac{F_n}{10^n} = \frac{10}{89}}\)

While no longer an undergrad, I found the problem fun to solve and wanted to work out the general pattern. Above \(F_n\) is the \(n\)th Fibonacci number. So \(F_0=0,F_1=1\) and \(F_{n} = F_{n-1} + F_{n-2}\) for \(n \ge 2\). Ron’s infinite series can be proved using the recurrence relation for the Fibonacci numbers and the general result is that for any \(c > \varphi = \frac{1+\sqrt{5}}{2} \approx 1.618\)

\(\displaystyle{\sum_{n=1}^\infty \frac{F_n}{c^n} = \frac{c}{c^2-c-1}}.\)

To see why, first note that \(F_n \approx \varphi^n/\sqrt{5}\) so the sum does converge for \(c>\varphi\). Let \(x = \sum_{n=1}^\infty \frac{F_n}{c^n}\) be the value of the sum. If we multiply \(x\) by \(c^2\), then we get

\(\displaystyle{c^2 x = \frac{c^2F_1}{c} + \sum_{n=2}^\infty \frac{F_n}{c^{n-2}} = c + \sum_{n=2}^\infty \frac{F_{n-1}}{c^{n-2}} + \sum_{n=2}^\infty \frac{F_{n-2}}{c^{n-2}} .}\)

But

\(\displaystyle{\sum_{n=2}^\infty \frac{F_{n-2}}{c^{n-2}}=x}\) and \(\displaystyle{\sum_{n=2}^\infty \frac{F_{n-1}}{c^{n-2}}=cx}\).

Together this implies that \(c^2 x = c+cx+x\) and so

\(\displaystyle{\sum_{n=1}^\infty \frac{F_n}{c^n} = x = \frac{c}{c^2-c-1}.}\)

Generating functions

The above calculation is closely related to the generating function of the Fibonacci numbers. The generating function of the Fibonacci numbers is the function \(f(z)\) given by

\(\displaystyle{f(z) = \sum_{n=1}^\infty F_n z^n.}\)

If we let \(z = c^{-1}\), then by Ron’s exercise

\(\displaystyle{f(z) = \frac{c}{c^2-c-1}=\frac{z^{-1}}{z^{-2}-z^{-1}-1} = \frac{z}{1-z-z^2},}\)

for \(z < \varphi^{-1}\). So solving Ron’s exercise is equivalent to finding the generating function of the Fibonacci numbers!

Other sums

In “Probabilizing Fibonacci Numbers”, Ron also suggests getting the undergrads to add up \(\sum_{k=0}^\infty \frac{1}{F_{2^k}}\). I leave this sum for another blog post!