[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.

Advertisements
This entry was posted in Random and tagged . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s