Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
The keyword here is "generating function." I might add a more detailed response later. –  Qiaochu Yuan Jan 26 '12 at 19:01
    
@QiaochuYuan: Sorry, didn't see your comment. Please feel free to add your answer. –  Aryabhata Jan 26 '12 at 19:07
1  
See also this question. –  Peter Phipps Jan 26 '12 at 20:32
add comment

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.