If a coin is tossed 3 times, there are 8 possible outcomes:
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?
We let $F(n,k)$ denote the number of sequences of $n$ coin tosses with at least $k$ consecutive heads. Now, consider some fixed $n.$ It is possible to get such a sequence if there were at least $k$ consecutive heads in the first $n-1$ tosses of an $n$-toss sequence, and in such a case, it doesn't matter whether the last toss was heads or tails. That's where the $2F(n-1,k)$ term came from. Now, the only other way to achieve such a sequence is if the last $k$ tosses of an $n$-toss sequence were heads, but there were no sequences of at least $k$ heads in the first $n-1$ tosses. (Do you see why?) It follows in particular that tosses $n-k+1$ through $n$ were heads, and toss $n-k$ was tails. (Do you see why?) Only the first $n-k-1$ tosses have any possible flexibility. There are $2^{n-k-1}$ ways to make the first $n-k-1$ tosses. (Do you see why?) Of these, though, $F(n-k-1,k)$ include at least $k$ consecutive heads, which we wish to avoid. That's where the $2^{n-k-1}-F(n-k-1,k)$ term comes in. (Note the difference from what you've typed.) Do you see why there is no overlap between the two situations?