How to prove the Fibonacci sum $\sum \limits_{n=0}^{\infty}\frac{F_n}{p^n} = \frac{p}{p^2-p-1}$

Solution 1:

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

Solution 2:

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

Solution 3:

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.