Explanation of the Fibonacci sequence appearing in the result of 1 divided by 89?
What's the explanation of the Fibonacci sequence appearing in the result of 1/89, as demonstrated by http://www.goldennumber.net/Number89.htm and shown below? If you wish, also explain the relation to the number 109 too.
1 / 89 =
0 / (10 ^ 1 ) +
1 / (10 ^ 2 ) +
1 / (10 ^ 3 ) +
2 / (10 ^ 4 ) +
3 / (10 ^ 5 ) +
5 / (10 ^ 6 ) +
8 / (10 ^ 7 ) +
13 / (10 ^ 8 ) +
...
0.011235955... =
0.0 +
0.01 +
0.001 +
0.0002 +
0.00003 +
0.000005 +
0.0000008 +
0.00000013 +
...
(This question was inspired by What is special about the numbers 9801, 998001, 99980001 ..?.)
Fibonacci numbers have the generating function
$$\frac{x}{1-x-x^2} = \sum_{k=0}^{\infty} F_k x^k$$
for $|x| \lt \frac{1}{\varphi}$.
Setting $x=\frac{1}{10}$ gives us the result, I believe.
You can also use the closed form (Binet's formula) and come up with two infinite geometric series which can be easily computed.
Consider the generating function $$f(x) = \sum_{k=0}^{\infty} F_k x^k$$
where $F_k$ are the Fibonacci numbers. The Fibonacci recurrence $F_k = F_{k-1} + F_{k-2}$ gives $$f(x) = x + \sum_{k=2}^{\infty} (F_{k-1} + F_{k-2}) x^k = x + \sum_{k=1}^{\infty} F_k x^{k+1} + \sum_{k=0}^{\infty} F_k x^{k+2} = x + (x + x^2) f(x).$$
It follows that $(1 - x - x^2) f(x) = x$, so $$f(x) = \frac{x}{1 - x - x^2}.$$
Substituting $x = \frac{1}{10}$, we conclude that $$\sum_{k=0}^{\infty} \frac{F_k}{10^k} = \frac{10}{89}.$$
Similarly, substituting $x = - \frac{1}{10}$, we conclude that $$\sum_{k=0}^{\infty} (-1)^k \frac{F_k}{10^k} = - \frac{10}{109}.$$
Generating functions are a very powerful method for understanding many sequences in combinatorics and other areas of mathematics. In this example we can use the generating function to go even further: via partial fraction decomposition we can quickly deduce Binet's formula $$F_k = \frac{\phi^k - \varphi^k}{\phi - \varphi}$$
for the Fibonacci numbers, where $\phi, \varphi$ are the two roots of $x^2 = x + 1$, and this idea generalizes to other sequences defined by a linear recurrence.
A standard reference on generating functions is Wilf's generatingfunctionology.