(adsbygoogle = window.adsbygoogle || []).push({}); Let us note [itex]f_n[/itex] the number of ways to throw a coin n times without ever throwing tails two times in a row. Show that [itex]f_n=f_{n-1}+f_{n-2}[/itex].

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 [itex]\left[ \frac{n+1}{2}\right] [/itex]. (For instance, if n=3, the maximum amount of tails that can come out is 2, and [itex]\left[ \frac{3+1}{2}\right]=[2]=2[/itex] as it should. If n=4, the maximum amount is 2 also and [itex]\left[ \frac{4+1}{2}\right]=[2.5]=2[/itex].)

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

[tex]\binom{n-j+1}{j}[/tex]

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

[tex]\binom{(n-2j+1)+(j+1)-1}{(j+1)-1} = \binom{n-j+1}{j}[/tex]

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

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

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!

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Probability problem (throwing a coin n times)

**Physics Forums | Science Articles, Homework Help, Discussion**