Coin tossing problem

I saw aproblem posed at Lubos Motl's blog that started me thinking about this question: how likely is a run of h heads or more in k tosses of a fair coin?

I came up with a recurrence relation. Let P(h, k) = n(h, k) / 2^k be the probability, where n(h, k) is the number of sequences of length k containing a run of h or more heads.

If h > k then n(h, k) = 0. Otherwise we have two possibilities for a sequence containing h or more heads in a row:

• an initial run of h heads, followed by k-h "don't care" tosses or
  
• a prefix of length j < k-h-1 not containing a run of h heads, followed by a tail, followed by h heads, followed by k-j-h-1 "don't care" tosses.
  

Assuming now that h <= k, we have

n(h, k) = 2^(k-h) + sum (j in 0..k-h-1) (2^(k-j-h-1).nbar(h, j))

where nbar(h, j) = 2^j - n(h, j) is the number of sequences of length j that do not contain a run of h or more heads. This gives

n(h, k)
= 2^(k-h) + sum (j in 0..k-h-1) (2^(k-j-h-1).2^j - 2^(k-j-h-1).n(h, j))
= 2^(k-h) + (k-h).2^(k-h-1) - sum (j in 0..k-h-1) (2^(k-j-h-1).n(h, j))

Let's try this out. Consider the case h = 2.

• k = 2 sequences are {HH};
  n(2, 2) = 2^0 = 1.
  
• k = 3 sequences are {HH*, THH};
  n(2, 3) = 2^1 + 2^0 - 2^0.n(2, 0) = 3.
  
• k = 4 sequences are {HH**, THH*, *THH};
  n(2, 4) = 2^2 + 2.2^1 - 2^1.n(2, 0) - 2^0.n(2, 1) = 8.
  
• k = 5 sequences are {HH***, THH**, *THH*, T*THH, HTTHH}.
  n(2, 5) = 2^3 + 3.2^2 - 2^2.n(2, 0) - 2^1.n(2, 1) - 2^0.n(2, 2) = 19.
  
• ...