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.

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

share|improve this question
1  
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
1  
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
2  
This seems to be the question André is referring to. @This, usually without stated initial conditions, everyone just takes the default one... –  J. M. Apr 26 '12 at 2:15

2 Answers 2

up vote 10 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer

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.