# Prove that the infinite sum $\sum_{n=1}^{\infty} \frac{F_{n}}{ 10 ^ n }$ converges to a rational number

How do you prove that the following infinite sum \begin{align} &0.1 \\+\;&0.01 \\+\;&0.002 \\+\;&0.0003 \\+\;&0.00005 \\+\;&0.000008 \\+\;&0.0000013 \\ \;&\quad\vdots \end{align} converges to a rational number?

Notice that the above sum can be written as

$$\sum_{n=1}^{\infty} \frac{F_{n}}{ 10 ^ n }$$

where $F_{n}$ is a Fibonacci sequence.

We have $F_n=\frac{\varphi^n-\psi^n}{\sqrt5}$. And using a geometric sums we get $$\sum_{n=1}^\infty\frac{F_n}{10^n}=\frac1{\sqrt 5}\sum_{n=1}^\infty\frac{\varphi^n}{10^n}-\frac1{\sqrt 5}\sum_{n=1}^\infty\frac{\psi^n}{10^n}=\frac1{\sqrt5}\frac{\frac\varphi{10}}{1-\frac{\varphi}{10}}-\frac1{\sqrt5}\frac{\frac\psi{10}}{1-\frac{\psi}{10}}=\frac{40}{(19+\sqrt5)(19-\sqrt5)}=\frac{10}{89}$$

What happens if you take the Fibonacci sequence and subtract the sequence shifted by one?

  1 1 2 3 5 8 13 21 34 …
- 0 1 1 2 3 5  8 13 21 …
= 1 0 1 1 2 3  5  8 13 …


You get the sequence shifted by two, except for the first number. Now let's introduce a “decimal point”, even though the numbers are not really digits of the decimal expansion. You may think of this as a formal sum if you prefer doing things the formal way, but a decimal point feels more intuitive to me.

  1.1 2 3 5 8 13 21 34 …
- 0.1 1 2 3 5  8 13 21 …
= 1.0 1 1 2 3  5  8 13 …


The second row is your number $x$. The first row is shifted one digit to the left so it is $10\,x$. The last row is shifted one digit to the right and has one added to it. So it is $1+x/10$. Now you have an equation:

\begin{align*} 10\,x - x &= 1 + x/10 \\ 9\,x &= 1 + x/10 \\ 90\,x &= 10 + x \\ 89\,x &= 10 \\ x &= 10/89 \end{align*}

The choice of where to put the decimal point is pretty arbitrary, you could also have placed it one digit further right and written the equation as $100\,x - 10\,x = 10 + x$, using the fractional part of the third row as your unshifted number.

The above argument works without any need to look up more than the basic definition of the Fibonacci numbers. But it does rely on the convergence of the series. If you don't take that for granted, have a look at the quotient between two consecutive sequence elements.

$$\frac{a_{n+1}}{a_n}=\frac{10^n\,F_{n+1}}{10^{n+1}\,F_n}= \frac1{10}\left(1+\frac{F_{n-1}}{F_n}\right)<\frac{2}{10}<1$$

so by the ratio test the series is absolutely convergent. This justifies that treating the infinite sum like a single number makes sense.

• You might want to justify why this works. We don't need even more people running around and thinking series can be manipulated any which way... Otherwise it's way to easy to "prove" that $1+2+4+8+\cdots = -1$ – Brevan Ellefsen Jan 5 '17 at 14:35
• @BrevanEllefsen: I wanted to keep this simple and intuitive, but you (and those who up-voted your comment) are probably right. I've updated my post, and hope that's along the lines you had in mind. And for future reference, here is the post discussing that $1+2+4+8+\dots=-1$ scenario. Just in case anyone wonders (like I did) what could make someone consider this. – MvG Jan 6 '17 at 10:15

Hint :

Denote the given problem as $x$ and from the recurrence relation $F_{n}=F_{n-1}+F_{n-2}$, we have \begin{align} x&=\sum_{n=1}^{\infty} \frac{F_{n}}{10 ^ n}\\ &=\frac{F_1}{10}+\sum_{n=2}^{\infty} \frac{F_{n}}{10 ^ n}\\ &=\frac{1}{10}+\sum_{n=2}^{\infty} \frac{F_{n-1}+F_{n-2}}{10 ^ n}\\ &=\frac{1}{10}+\frac{1}{10}\sum_{n=2}^{\infty} \frac{F_{n-1}}{10 ^{n-1}}+\frac{1}{10^2}\sum_{n=2}^{\infty} \frac{F_{n-2}}{10 ^{n-2}}\\ &=\frac{1}{10}+\frac{1}{10}\sum_{n-1=1}^{\infty} \frac{F_{n-1}}{10 ^{n-1}}+\frac{1}{10^2}\sum_{n-2=1}^{\infty} \frac{F_{n-2}}{10 ^{n-2}}\\ &=\frac{1}{10}+\frac{1}{10}\sum_{n=1}^{\infty} \frac{F_{n}}{10 ^ n}+\frac{1}{100}\sum_{n=1}^{\infty} \frac{F_{n}}{10 ^ n}\\ x&=\frac{1}{10}+\frac{x}{10}+\frac{x}{100}\\ \end{align} The rest is a piece of cake. In fact, using the same technique, you can generalize the problem into something like this: $$\sum_{n=1}^{\infty} \frac{F_{n}}{y ^ n}=\frac{y}{y^2-y-1}$$ It holds provided $y>\phi$.

• No convergence for $1<y\le\phi$. The RHS clearly negative. – A.Γ. Jan 5 '17 at 11:10
• @A.G. Thanks. Noted – Anastasiya-Romanova 秀 Jan 5 '17 at 11:23
• I like this answer best. I think the convergence condition should be $|y| > \phi$ though. – 6005 Jan 5 '17 at 18:28
• @user21820 Done. I didn't edit it just don't wanna restate what's pointed out in the comment so that the comment is still relevant and useful. Thanks, though :) – Anastasiya-Romanova 秀 Jan 6 '17 at 4:54
• The easiest way to handle that is to edit the post and then reply saying that it's fixed. Then the comments can be removed if desired. Same as I did with my comments. – user21820 Jan 6 '17 at 5:08

The method used by both MvG and Anastasiya-Romanova 秀 assumes without proof that the series converges. If the series does not converge, it still produces a value but that value has no worth.

Thus you first need to show that $\sum_{n=1}^{\infty} \frac{F_n}{10^n}$ converges at all. Of course you can just follow user296113's lead and use Binet's formula, reducing the series to a couple of obviously convergent geometric series.

But if you want to solve the problem using nothing more about the Fibonacci numbers than their basic definition, you can first prove that $F_n < 2^n$ for all $n$: First note that $F_0 = 0 < 1 = 2^0$ and $F_1 = 1 < 2 = 2^1$. Assume that $F_{n-1} < 2^{n-1}$ and $F_{n-2} < 2^{n-2}$. Then $$F_n = F_{n-1} + F_{n-2} < 2^{n-1} + 2^{n-2} = 3\cdot2^{n-2} < 4\cdot 2^{n-2} = 2^n$$ The result follows by induction.

From this we have that $$\sum_{n=1}^{N} \frac{F_n}{10^n} < \sum_{n=1}^{N} \frac{2^n}{10^n} = \sum_{n=1}^{N} \left(\frac{1}{5}\right)^n < \sum_{n=1}^{\infty} \left(\frac{1}{5}\right)^n$$ For all $N$. Since the RHS converges, your series forms an increasing sequence in $N$ that is bounded above, and thus also must converge.

This is in fact equal to $\frac{10}{89}$, and there is a proof on this website- http://www2.math.ou.edu/~dmccullough/teaching/miscellanea/miner.html

(I edited my answer from $\frac{1}{89}$ after gowrath in the comments pointed out that I was off by a factor of $10$.)