How can I prove The Fibonacci sequence is encoded in the number $1/89$ i.e. $( 1/89 = 0.01 + 0.001 + 0.0002 + 0.00003 + 0.000005 + 0.0000008 + 0.00000013 + 0.000000021 + 0.0000000034 \ldots)$

  • $\begingroup$ Just evaluate the OGF in $z=\frac{1}{10}$. $\endgroup$ – Jack D'Aurizio Dec 23 '14 at 14:00
  • $\begingroup$ @JackD'Aurizio: That question doesn't look like a duplicate of this one. $\endgroup$ – barak manos Dec 23 '14 at 14:05
  • $\begingroup$ @Barak: It isn't one. It can be used to answer this one, but only by someone with suitable background. Someone without that background might well need a bit more explanation. $\endgroup$ – Brian M. Scott Dec 23 '14 at 14:12
  • $\begingroup$ It looks to me that the point is just to compute $$\sum_{n=1}^{+\infty}\frac{F_n}{10^n}.$$ The other question solves a more general problem, but the technique is just the same. $\endgroup$ – Jack D'Aurizio Dec 23 '14 at 14:17

If there were such $x$ ($ = 0.011235\ldots$), then this satisfies the property of Fibonacci sequence: $$\begin{array}{lllllllll} &0.&1&1&2&3&5&\ldots&//\ 10x\\ +&0.&0&1&1&2&3&\ldots&//\ x\\ \hline &0.&1&2&3&5&9&\ldots\\ +&1\\ \hline &1.&1&2&3&5&9&\ldots&//\ 100x \end{array} $$

So by solving for such $x$, $$\begin{align*} 10x + x &= 100x - 1\\ 89x &= 1\\ x &= \frac{1}{89}\end{align*}$$


I like peterwhy’s answer — think of this as an extended comment on it — but it does slide over a potentially tricky point: $x$ isn’t

$$\begin{array}{lll} &0.&0&1&1&2&3&5&\color{brown}8&\color{brown}13&\ldots\;, \end{array}$$

as the picture might suggest, but rather

$$\begin{array}{lll} &0.&0&1&1&2&3&5&\color{brown}9&5&\ldots\;, \end{array}$$

because of carries. We actually have

$$x=\sum_{n\ge 1}\frac{F_{n-1}}{10^n}\;.$$

Now we can carry out peterwhy’s calculation as follows:

$$\begin{align*} 0.01+0.1x+0.01x&=0.01+\sum_{n\ge 1}\frac{F_{n-1}}{10^{n+1}}+\sum_{n\ge 1}\frac{F_{n-1}}{10^{n+2}}\\\\ &=0.01+\sum_{n\ge 2}\frac{F_{n-2}}{10^n}+\sum_{n\ge 3}\frac{F_{n-3}}{10^n}\\\\ &=0.01+\frac{F_0}{10^2}+\sum_{n\ge 3}\frac{F_{n-2}+F_{n-3}}{10^n}\\\\ &=0.01+\sum_{n\ge 3}\frac{F_{n-1}}{10^n}\\\\ &=\sum_{n\ge 1}\frac{F_{n-1}}{10^n}\\\\ &=x\;, \end{align*}$$

so $0.01=0.89x$, and $x=\dfrac1{89}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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