Use generating functions If a coin is flipped 25 times with

Use generating functions. If a coin is flipped 25 times with eight tails occurring, what is the probability that no run of six (or more) consecutive heads occurs?

Solution

Consider eH,eT s.t eH denotes the number of times our coin lands on heads and eT is the number of times our coin lands on tails. We want the number of integer solutions to:

eH+eT=25

where eH?[9,25] and eT=8. It follows that our generating function h is

h(x)=(x9+x10+...x25)x8

where we want to find the coefficient of x25.

Now, observe that h can re-written as

h(x)=x17(1+x+...x16)

where we want to find the coefficient of x16 now. Using the formula for finite geometric series, we see that h becomes

h(x)=x17(1?x171?x)

=x17(1?x17)(11?x)

where using the formula for infinite geometric series gives us

x17(1?x17)(1+x+...+xn+...)

Finally, using the formula h(x)=f(x)g(x)=c0+c1x+...+crxr+... where cr=a0br+a1br?1+...arb0, we find

f(x)=(1?x17),g(x)=(1+x+...)

?a0b16=1?1=1

so it follows that the coefficient attached to x16 is 1.