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 nth 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!

Leave a comment