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.

We are familiar with the nifty fact that given the Fibonacci series $F_n = 0, 1, 1, 2, 3, 5, 8,\dots$ then $0.0112358\dots\approx 1/89$. In fact,

$$\sum_{n=0}^{\infty}\frac{F_n}{10^n} = \frac{10}{89}$$

Prove that, more generally, for $p > 1$,

$$\sum_{n=0}^{\infty}\frac{F_n}{p^n} = \frac{p}{p^2-p-1}$$

(The above simply was the case $p = 10$.)

share|improve this question
2  
Here is a proof for $p=10$: geom.uiuc.edu/~rminer/1over89/1over89proof.html It should not be hard to generalize it for any $p$. –  Listing Dec 5 '11 at 10:44
1  
Here's another ulcar.uml.edu/~iag/CS/Fibonacci.html –  David Mitra Dec 5 '11 at 10:55

3 Answers 3

up vote 13 down vote accepted

You can use Binet's formula, $$F_n=\frac{\phi^n-(-\phi)^{-n}}{\sqrt 5}$$ along with the usual geometric series formula to prove your claim:

$$\begin{align*}\sum_{n=0}^{\infty}\frac{F_n}{p^n}&=\frac1{\sqrt 5}\left(\frac1{1-\phi/p}-\frac1{1+(p\phi)^{-1}}\right)\\&=\frac{p(\phi^2+1)/(\sqrt 5)}{(p-\phi)(p\phi +1)}\\&=\frac{p\phi}{\phi p^2-(\phi^2-1)p-\phi}\\&=\frac{p\phi}{\phi p^2-\phi p-\phi}\\&=\frac{p}{p^2-p-1}\end{align*}$$

share|improve this answer
5  
I don't think Binet's formula is needed. Just use the definition $F_{n+1}=F_n + F_{n-1}$. See en.wikipedia.org/wiki/Fibonacci_number#Power_series –  lhf Dec 5 '11 at 10:53
3  
I agree that this is mosquito-nuking here, but it was the first proof that came to mind... –  J. M. Dec 5 '11 at 11:06
1  
This can be used to obtain the partial sum as well. –  Mike Spivey Dec 5 '11 at 19:05

Let $f(z) = \sum\limits_{n=0}^\infty F_nz^n$

Then $$\begin{align}zf(z) + z^2f(z) &= \sum_{n=1}^\infty {F_{n-1}z^n} + \sum_{n=2}^\infty F_{n-2}z^n\\ &=F_0z + \sum_{n=2}^\infty (F_{n-2}+F_{n-1})z^n \\&=F_0z + (f(z)-F_0 - F_1z) \end{align}$$

Using $F_0=0, F_1=1$, we can solve for $f(z)$:

$$f(z)=\frac{z}{1-z-z^2}$$

Now substitute $z=\dfrac{1}p$.

[Note, this doesn't prove that the series converges, only that, if the series converges, it converges to this value. It might require a little more effort to prove that it converges for $z=\dfrac{1}{p}$.]

share|improve this answer

I'll copy here an answer, which I posted before at AoPS. However the solution from wikipedia article (see the link in lhf's comment to J.M.'s answer) seems to be much more elegant. Basically these matrix proofs often can be rewritten to proofs using generating functions.


We denote by $F_i$ the i-th Fibonacci number.

Using the formula $$\sum_{i=0}^n F_i k^i = \frac{(k-1)k^{n+1}F_{n+1}-k^{n+2}F_{n+2}+k}{1-k-k^2} \qquad (*)$$ you get for $k<\frac{1-\sqrt{5}}{2}$ using Binet formula mentioned by mavropnevma that $$\sum_{i=0}^\infty F_i k^i = \lim_{n\to\infty} \frac{(k-1)k^{n+1}F_{n+1}-k^{n+2}F_{n+2}+k}{1-k-k^2} = \frac k{1-k-k^2}.$$ In your case $k=1/10$ and this limit is equal to 10/89.

The above formula (*) can be derived by induction.

Inductive step:

$\frac{(k-1)k^{n+1}F_{n+1}-k^{n+2}F_{n+2}+k}{1-k-k^2}+k^{n+1}F_{n+1}= \frac{-k^{n+3}F_{n+1}-k^{n+2}F_{n+2}+k}{1-k-k^2}=$ $\frac{-k^{n+3}(F_{n+3}-F_{n+2})-k^{n+2}F_{n+2}+k}{1-k-k^2}= \frac{(k-1)k^{n+2}F_{n+2}-k^{n+3}F_{n+3}+k}{1-k-k^2}$

However, my method (which lead me to "discovering" the formula, by which I mean that I did not know the value of the sum in advance) was using matrix method.

For $A=\begin{pmatrix} 0 & 1\\ 1 & 1 \end{pmatrix}$ we have $A^n= \begin{pmatrix} F_{n-1} & F_n\\ F_n & F_{n+1} \end{pmatrix} $.

From $$\sum_{k=0}^n (Ak)^i = (A^{n+1}k^{n+1}-I)(Ak-I)^{-1}$$ using $(Ak-I)^{-1}=\begin{pmatrix}-1&k\\k&k-1\end{pmatrix}^{-1}= \frac1{1-k-k^2}\begin{pmatrix} k-1& -k \\ -k & -1 \end{pmatrix}$ and $A^{n+1}k^{n+1}-I=\begin{pmatrix} k^{n+1}F_n-1 & k^{n+1}F_{n+1}\\ k^{n+1}F_{n+1} & k^{n+1}F_{n+2}-1 \end{pmatrix}$ by matrix multiplication we get the desired result.

EDIT: I have noticed that this sum is mentioned in wikipedia's article on Fibonacci numbers They refer to this page - a proof (using matrices) is provided there.

share|improve this answer
    
+1 for the partial sum alone. –  Mike Spivey Dec 5 '11 at 16:52

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.