[latexpage]
\nI 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.<\/p>\n
If you are afraid of math, this is your cue to exit. See you at my next post!<\/p>\n
<\/p>\n
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:
\n\\[F_0=0,F_1=1,F_2=1,F_3=2,F_4=3\\ldots\\]
\nWell, with that definition in mind, here’s the result.
\n\\[\\sum_{k=0}^{\\infty}\\frac{F_k}{2^k}=2\\]
\nFirst of all … pretty cool, right? Who knew that series would even converge?* But I like the proof even better.<\/p>\n
*UPDATE: Joon points out that<\/a> since the ratio of successive Fibonacci terms tends to the golden ratio<\/a> \\(\\phi\\) in the limit, then this series must converge by the ratio test (as \\(\\phi\/2 < 1\\))\n\nProof:<\/strong> 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.<\/p>\n Let’s start with Pr(X=2). This is pretty clearly 1\/4 — out of the four possibilities, only one contains consecutive heads.<\/p>\n 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.<\/p>\n 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).<\/p>\n 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.<\/p>\n 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<\/em>. 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?<\/p>\n 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 BONUS HOMEWORK PROBLEM! Show that [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 … Continue reading
\n\\[Pr(X=k)=\\frac{F_{k-1}}{2^k}\\]
\nWell, now we’re done; probabilities must add to one, so we must have
\n\\[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}}\\]
\nNot bad, right?<\/p>\n
\n\\[\\sum_{k=N}^{\\infty}\\frac{F_{k}}{2^{k}}=\\frac{F_{N+2}}{2^{N-1}}\\]
\nfor any N >= 1.<\/p>\n","protected":false},"excerpt":{"rendered":"