[latexpage]
I stumbled across a result yesterday that I thought was really cool. I went to check the googles to find out if it was a very well-known result, but I couldn’t find it proved anywhere, so I thought I’d show it here.

If you are afraid of math, this is your cue to exit. See you at my next post!

You all know the Fibonacci sequence, right? The one where each member is the sum of the two that came before it? It starts out like this:
\[F_0=0,F_1=1,F_2=1,F_3=2,F_4=3\ldots\]
Well, with that definition in mind, here’s the result.
\[\sum_{k=0}^{\infty}\frac{F_k}{2^k}=2\]
First of all … pretty cool, right? Who knew that series would even converge?* But I like the proof even better.

*UPDATE: Joon points out that since the ratio of successive Fibonacci terms tends to the golden ratio \(\phi\) in the limit, then this series must converge by the ratio test (as \(\phi/2 < 1\)) Proof: Consider an experiment in which you flip a coin until you get consecutive heads, at which point you stop. Let X be the random variable denoting the number of flips it takes to get those consecutive heads. Let’s try to find its probability mass function.

Let’s start with Pr(X=2). This is pretty clearly 1/4 — out of the four possibilities, only one contains consecutive heads.

How about Pr(X=3)? Well, we know that the last two will have to be the last two from the X=2 case (i.e. HH). What letters can go in front? Well, only T — if it were H, then we would have gotten to consecutive heads sooner. So there’s only one possibility here — THH. Hence our probability is 1/8.

Pr(X=4)? Again, the last three letters have to be THH. What can go in front? Since our first letter is a T, either letter can go in front. So we can have either HTHH or TTHH. Hence the probability is 2/16, or 1/8 (again).

Okay, okay, last one before we try to find a pattern. Pr(X=5)! The last four flips have to be HTHH or TTHH. What can go in front of the H? Only T. What can go in front of the T? Well, T or H. So there are 3 possibilities here and our probability is 3/32.

All right, you ready? Pr(X=k). Well, we know the denominator will be \(2^k\). So let’s just figure out the numerator — i.e. the total number of possibilities we have. As before, we know how many options there are for the k-1 case (let’s call it M). For each of those options, we can put a tail in front of it, so we have at least M possibilities. But we can also put a head in front of any options that start with a tail. How many of those are there? Well, by the logic just described above (in italics), that would be the total number of options for the k-2 case! Let’s call that number N. Therefore we have M+N possibilities, i.e. the number of options for the k-1 case plus the number of options for the k-2 case! Sound familiar?

We’ve looked at the k=2 and k=3 case and we know that both of those have exactly one possibility. So by induction, the number of possibilities for the k=N case is \(F_{N-1}\), and so
\[Pr(X=k)=\frac{F_{k-1}}{2^k}\]
Well, now we’re done; probabilities must add to one, so we must have
\[2=2*1=2*\sum_{k=2}^{\infty}\frac{F_{k-1}}{2^k} = \sum_{k=2}^{\infty}\frac{F_{k-1}}{2^{k-1}}=\sum_{k=0}^{\infty}\frac{F_{k}}{2^{k}}\]
Not bad, right?

BONUS HOMEWORK PROBLEM! Show that
\[\sum_{k=N}^{\infty}\frac{F_{k}}{2^{k}}=\frac{F_{N+2}}{2^{N-1}}\]
for any N >= 1.