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.
On
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$.)
On
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.
On
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$.
On
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.
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}$$