Baltic Way 2011 · Shortlist problem

Combinatorics

Compute the sum

\sum_{n=1}^{\infty} \frac{F_n}{10^{n+1}}

where $F_n$ is the $n$ th Fibonacci number given by $F_1 = F_2 = 1$ and $F_{n+1} = F_n + F_{n-1}$ for all $n \geq 2$ .

When you’re ready

Review material becomes available with the next Daily.

Review

Counting and enumeration

Solution

Let

X = \sum_{n=1}^{\infty} \frac{F_n}{10^{n+1}}

Then

X = \frac{1}{10^2} + \frac{1}{10^3} + \frac{2}{10^4} + \frac{3}{10^5} + \frac{5}{10^6} + \frac{8}{10^7} + \frac{13}{10^8} + \dots

10X = \frac{1}{10} + \frac{1}{10^2} + \frac{2}{10^3} + \frac{3}{10^4} + \frac{5}{10^5} + \frac{8}{10^6} + \frac{13}{10^7} + \dots

and

100X = 1 + \frac{1}{10} + \frac{2}{10^2} + \frac{3}{10^3} + \frac{5}{10^4} + \frac{8}{10^5} + \frac{13}{10^6} + \dots

Then $100X - 10X - X = 1$ (using the basic property of the Fibonacci numbers).

\text{So } X = \frac{1}{89}