Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$$

How do we prove that, more generally, for $p > 1$ then,

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

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

share|cite|improve this question
Here is a proof for $p=10$: It should not be hard to generalize it for any $p$. – Listing Dec 5 '11 at 10:44
Here's another – David Mitra Dec 5 '11 at 10:55
up vote 16 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|cite|improve this answer
I don't think Binet's formula is needed. Just use the definition $F_{n+1}=F_n + F_{n-1}$. See – lhf Dec 5 '11 at 10:53
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
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)$:


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|cite|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|cite|improve this answer
+1 for the partial sum alone. – Mike Spivey Dec 5 '11 at 16:52

Your Answer


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.