Solving Coin Toss Problem If a coin is tossed 3 times,there are possible 8 outcomes.
HHH HHT HTH HTT THH THT TTH TTT
In the above experiment we see 1 sequnce has 3 consecutive H, 3 sequence has 2 consecutive H and 7 sequence has at least single H.
Suppose a coin is tossed n times.How many sequence we will get which contains a consequnce of H of length at least k?.How to solve this problem using recursive relation?

Let $x^n(i,j)$ be the number of sequences of length $n$ with exactly $i$ as the length of the longest sequence of H's and ending in exactly $j$ H's. Then $x^n(i,j)=0$ if $i<j$ or $i\gt n$ or $j\gt n.$ We can fill in the table for $x^2(i,j)$ row $i,$ column $j:$
$$
\begin{array}{c|ccc}
 & 0 & 1 & 2 \\
\hline
0 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 \\
2 & 0 & 0 & 1 \\
\end{array}
$$
We can compute the array for $x^{n+1}$ from $x^n:$
We add an H or T to the (right) end of each sequence of length $n.$ Suppose we start with state $(i,j)$. If we add a T then the new value of $j$ will be $0$ no matter what the sequence was. The value of $i$ is unchanged. So the new state is $(i,0).$
If, instead, an H is added to the end, then $j$ increases by $1$ but $i$ will stay the same or increase by $1.$ We have $3$ cases: 
If $i=j$ then state $(i,i)$ becomes $(i+1,i+1).$
If $i>j$ then $(i,j)$ becomes $(i,j+1).$ 
And $i<j$ is not possible. 
Then the recursive equations are:
$x^{n+1}(i,0)=\sum_{j} x^n(i,j)$ 
$x^{n+1}(i,j)=x^n(i,j-1),$ for $i>j\ge 1.$
$x^{n+1}(j,j)=x^n(j-1,j-1)+x^n(j,j-1),\text { for }j\ge 1.  $
and $0$ otherwise.
For example, computing the table for $n=3,4$ and then $n=5:$
$$
\begin{array}{c|cccccc}
 & 0 & 1 & 2 & 3 & 4 & 5  \\
\hline
0 & 1 & 0 & 0 & 0 & 0 & 0 \\
1 & 7 & 5 & 0 & 0 & 0 & 0 \\
2 & 5 & 2 & 4 & 0 & 0 & 0 \\
3 & 2 & 1 & 0 & 2 & 0 & 0 \\
4 & 1 & 0 & 0 & 0 & 1 & 0 \\
5 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{array}
$$
Then compute the sum in each row. That gives the number with exactly $i$ as the largest number of consecutive H:  $1,12,11,5,2,1.$
If you want the number with $\ge i$ consecutive H's for $i=0,1,2,3,4,5$ :
$32,31,19,8,3,1.$
