# Prove that $\sum\limits_{n=0}^{\infty}\frac{F_{n}}{2^{n}}= \sum\limits_{n=0}^{\infty}\frac{1}{2^{n}}$

I came up with this identity in high school, and I can't remember how I proved it :P Does anyone know how I would go about doing this?

$$\sum_{n=0}^{\infty}\frac{F_{n}}{2^{n}}= \sum_{n=0}^{\infty}\frac{1}{2^{n}}$$

-
There is a link to a generalization on this page, at the right. –  André Nicolas Apr 26 '12 at 2:11
Ah, cool. Is there a way to prove this using generating functions? I think that's what I did originally. –  Nick Apr 26 '12 at 2:13
Please give us the initial conditions to the specific Fibonacci sequence you have in mind. I think this statement maybe ambiguous as is. –  ThisIsNotAnId Apr 26 '12 at 2:13
This seems to be the question André is referring to. @This, usually without stated initial conditions, everyone just takes the default one... –  Guess who it is. Apr 26 '12 at 2:15

Just for fun, here is a proof using probability.

Let $N$ be the number of times you toss a fair coin until you get two heads in a row.

Here are some outcomes for small $N$ values:

• $N=2\quad$ HH
• $N=3\quad$ THH
• $N=4\quad$ TTHH, HTHH
• $N=5\quad$ TTTHH, THTHH, HTTHH
• $N=6\quad$ TTTTHH, TTHTHH, THTTHH, HTTTHH, HTHTHH
• etc.

The outcomes of length $n$ are formed in two ways: by sticking a T in front of an outcome of length $n-1$ or sticking HT in front of an outcome of length $n-2$. Thus, the number of outcomes of length $n$ is $F_{n-1}$.

Since the probabilities must add to one, we have $$\sum_{n=2}^\infty {F_{n-1}\over 2^n}=1$$ which is equivalent to the required identity.

-
Whoa, that's crazy! I would have never thought to look at it that way. –  Nick Apr 26 '12 at 5:11

The generating series for the Fibonacci sequence is $$\frac{x}{1-x-x^2}=\sum_{n=0}^\infty F_nx^n.$$Now show that the series converges at $x=\frac12$ (using the ratio test for example) and to conclude that $\sum_{n=0}^\infty \frac{F_n}{2^n}=2$.

-