# Prove the Fibonacci sum $\sum \limits_{n=0}^{\infty}\frac{F_n}{p^n} = \frac{p}{p^2-p-1}$

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

-
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
Here's another ulcar.uml.edu/~iag/CS/Fibonacci.html –  David Mitra Dec 5 '11 at 10:55

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

-
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
I agree that this is mosquito-nuking here, but it was the first proof that came to mind... –  Guess who it is. 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)$:

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

-

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.

-
+1 for the partial sum alone. –  Mike Spivey Dec 5 '11 at 16:52