Probability problem (throwing a coin n times)

[quasar987]

Let us note $f_n$ the number of ways to throw a coin n times without ever throwing tails two times in a row. Show that $f_n=f_{n-1}+f_{n-2}$.

First of all, if the coin is thrown n times, then the maximum amount of tails that can come out while still respecting the 'no two tails in a row' condition is $\left[ \frac{n+1}{2}\right]$. (For instance, if n=3, the maximum amount of tails that can come out is 2, and $\left[ \frac{3+1}{2}\right]=[2]=2$ as it should. If n=4, the maximum amount is 2 also and $\left[ \frac{4+1}{2}\right]=[2.5]=2$.)

Now, for a given number j of tails that come out, we can arrange the tails and heads in

$$\binom{n-j+1}{j}$$

different ways. To get this result, I said "take the j tails, and j-1 heads and arrange them like so: T H T H ... H T. Now there are no two tails together and there remains n-j-(j-1)=n-2j+1 heads to distribute. The ways to distribute the remaining head can be seen as the number the ways to put n-2j+1 balls into j+1 baskets (there is one basket on each side of each T). This is known to be

$$\binom{(n-2j+1)+(j+1)-1}{(j+1)-1} = \binom{n-j+1}{j}$$

And to account for all the possible numbers of tails that can come out, we sum over all j's:

$$f_n=\sum_{j=0}^{\left[ \frac{n+1}{2}\right]}\binom{n-j+1}{j}$$

The problem is, I've shown that this does not satisfy the recurence relation! So, do you see something wrong with what's above?

Thanks!

 

[StatusX]

You're right when you say you start with a string THTH...THT, of length 2j-1, and then you need to add the remaining n-2j+1 heads. Now you can add any number of heads in any of the j-1 positions between tails or at either end of the string. (Note that the basket on the right side of an interior tail is the same as the one to the left of the next tail, and this may be your problem.) In other words, you need to come up with a sequence of j+1 nonnegative integers that sum to n-2j+1. Do you know how many such sequences there are?

 

[quasar987]

But this is exactly what I did. Is there a problem with my number of baskets? (j+1) or with my "number of such sequences"?

 

[quasar987]

Ah, I found a mistake in my "counter-proof", let me retry.

 

[0rthodontist]

There is a more direct combinatorial proof:
Consider the n-1'th length sequences. If they end in H, then you can add a T or an H to generate an n-length sequence. If they end in T, then you can add an H to generate an n-length sequence. So,
fn = 2*(# of n-1th seq ending in H) + (# of n-1th seq ending in T)
With a little argument you can turn this into
fn = 2f(n-2) + f(n-3)
and you can derive the other recurrence from that.

Edit: actually you can't derive the other recurrence from that, without resorting to the initial conditions. A different way to break it down is:
fn = (# of nth seq ending in H) + (# of nth seq ending in T)
which gives you what you want

 

[quasar987]

More direct is good! I've managed to proove it for n=even and I suspect it will be similar for n=odd, but it was lenghty!

After reading your post 3 times, I still don't see what you're idea is!

One source of confusion for instance is whwn you say

"Consider the n-1'th length sequences. If they end in H, then you can add a T or an H to generate an n-length sequence. If they end in T, then you can add an H to generate an n-length sequence."

What makes you think you have a T or an H left in hand after placing all your T and H. And when in that, did you take care that there be no two T together? Plz explain, it's late here.

 

[0rthodontist]

I'll explain the first one in more detail because it's not quite what you want but it helps for the second one (which is exactly what you want).

What makes you think you have a T or an H left in hand after placing all your T and H. And when in that, did you take care that there be no two T together?

You have as many T's and H's as you want. The way that you ensure that there are no two T together is that:
1. If the n-1th seq (by this I mean, a sequence of H's and T's of length n-1 such that no two T's are adjacent) ends in H, then you can place an T or an H without causing two T's to be placed together
2. If the n-1th seq ends in T, then you can place only an H without causing two T's to be placed together.

Now for the first case, we want to count the number of n-1th seqs that ends in H. If we strip the H off then the remaining n-2th prefix can be any n-2th seq at all, so there are f(n-2) ways to form n-1th seqs ending in H. Then you add back a T or an H, multiplying this number by 2, so this enumeration contributes 2 * f(n-2) to fn

In the second case, if the n-1th seq ends in T, then if you strip the T off, the remaining n-2th seq must end in H. Strip THAT H off and you get an unrestricted n-3th seq. You add back HTH to that and get a nth seq, so this enumeration contributes f(n-3) to fn.

So fn = 2*f(n-2) + f(n-3)

Showing that fn = f(n-1) + f(n-2) is similar, only breaking it down as
fn = (# of nth seq ending in H) + (# of nth seq ending in T)
Think in terms of stripping the last letter off and considering what must remain.