11
$\begingroup$

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 ..?.)

  • 1
    See also [this question](http://math.stackexchange.com/questions/31085/for-which-number-does-multiplying-it-by-99-add-a-1-to-each-end-of-its-decimal-re).2012-01-26

2 Answers 2

18

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.

10

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.