Getting $k$ consecutive heads If a coin is tossed 3 times, there are 8 possible outcomes:  
$$\text{HHH, HHT, HTH, HTT, THH, THT, TTH, TTT}$$ 
In the above experiment we see 1 sequence has 3 consecutive H, 3 sequences have at least 2 consecutive H and 7 sequences have at least a single H. 
Suppose a coin is tossed $n$ times. How many sequence will we get which contains at least $k$ consecutive heads?
Someone solved this problem using this recursive relation 
$$F(n,k) = 2F(n - 1,k) + 2^{(n-k-1)} - F(n-k-1,k)\,,$$ 
but I can not understand how this formula works. Can anyone explain?
 A: There are two ways to obtain a run of at least $k$ heads in $n$ tosses:


*

*There was already a run of at least $k$ heads in the first $n-1$ tosses.  These possibilities, which by definition number $F(n-1,k)$, can be followed independently by either heads or tails, thereby doubling the quantity to $2F(n-1,k)$ possibilities.

*The last toss created a run of at least $k$ heads.  Evidently, then, the last toss was a head and the last $k-1$ tosses out of the first $n-1$ tosses also were heads, but immediately preceding that sequence was a tail.  Independently of these results, the first $n-k-1$ tosses could have been anything, producing $2^{n-k-1}$ possibilities.
However, some sequences may have been counted in both (1) and (2): these are the ones, if any, where both conditions apply.  Although condition (1) asserts there was a run of least $k$ heads in the first $n-1$ tosses, condition (2) places that sequence within the first $n-k-1$ of the tosses.  Thus, the doubly-counted sequences are those in which a run of $k$ heads had already been observed within the first $n-k-1$ tosses, an amount that numbers $F(n-k-1,k)$.  This quantity must be subtracted from the sum of (1) and (2), yielding the recursion.
This argument makes sense provided $n-k-1 \ge 0$.  To get the recursion started, $F(n,k)=0$ whenever $n\lt k$ and $F(k,k)=1$, both of which are obvious results.
