## [Soln] Fibonacci fractions

The sum of $0.1 + 0.01 + 0.002 + 0.0003 + 0.00005 + \dots$, where each term is the $n$-th Fibonacci number, shifted $n$ places to the right (that is, divided by $10^n$) can be represented as $\displaystyle\frac{a}{b}$ where $\gcd(a,b) = 1.$ Find $a + b$.

First, let’s introduce some notation so that we have an easy way of talking about the terms here. Let $F_n$ be the $n$-th Fibonacci number, i.e. $F_1 = F_2 = 1$, and $F_{n+2} = F_{n+1} + F_{n}$. Let the sum we are supposed to evaluate be $S$. Then

$S = \displaystyle\sum_{n = 1}^{\infty} \frac{F_n}{10^n} = \frac{F_1}{10^1} + \frac{F_2}{10^2} + \dots$

(Note: If you are not comfortable with the summation signs, that’s ok! Just do everything in expanded sums with $\dots$ at the end. Summation signs are not that difficult but do take some getting used to; always try to substitute the 1st, 2nd and last value of the series to make sure that you got the summation limits and general term correct.)

A very common technique for evaluating an infinite sum $S$: multiply $S$ by a suitable factor and try to make the “tails” (i.e. the $\dots$ part of the sum) match. Then, substitute $S$ on the right-hand side to get an equation in $S$. Most commonly, we will try to manipulate the sum so that second term takes the place of the first term, and so on.

Easiest to understand this through a worked example. In the problem at hand, we want to manipulate $S$ so that we can make $\displaystyle\frac{F_2}{10^2}$ into $\displaystyle\frac{F_1}{10^1}$. The first thing we do is multiply by 10 so that the denominator matches:

\begin{aligned} S &= \frac{F_1}{10^1} + \frac{F_2}{10^2} + \frac{F_3}{10^3} \dots, \\ 10S &= F_1 + \frac{F_2}{10^1} + \frac{F_3}{10^2} + \frac{F_4}{10^3} + \dots. \end{aligned}

Since $F_2 = F_1$, we have

$10S = 1 + \displaystyle\frac{F_1}{10^1} + \displaystyle\frac{F_3}{ 10^2} + \displaystyle\frac{F_4}{10^3} + \dots.$

To match the rest of the terms, we can use the Fibonacci identity $F_{n+2} = F_{n+1} + F_n$:

\begin{aligned} 10S &= 1 + \frac{F_1}{10^1} + \frac{F_2 + F_1}{10^2} + \frac{F_3 + F_2}{10^3} + \dots \\ &= 1 + \left( \frac{F_1}{10^1} + \frac{F_2}{10^2} + \frac{F_3}{10^3} + \dots \right) + \left( \frac{F_1}{10^2} + \frac{F_2}{10^3} + \dots \right) \\ &= 1 + S + \frac{S}{10}. \end{aligned}

In the last step, we simply used the definition of $S$ to substitute it back into the RHS. (Isn’t it magical?) Hence, we have a linear equation in $S$ each is easy to solve:

\begin{aligned} 10S &= 1 + S + \frac{S}{10}, \\ 100S &= 10 + 10S + S, \\ 89S &= 10, \\ S &= \frac{10}{89}. \end{aligned}

Hence, the answer to the problem is $10 + 89 = 99$. The answer is 99.