Number of occurrences of k consecutive 1's in a binary string of length n (containing only 1's and 0's) Say a sequence $\{X_1, X_2,\ldots ,X_n\}$ is given, where $X_p$ is either one or zero ($0 < p < n$). How can I determine the number of strings, which do contain at least one occurrence of consequent $1$'s of length $k$ ($0 < k < n$). 
For example, a string $\{1, 0, 1, 1, 1, 0\}$ is such a string for $n = 6$ and $k = 3$.
Here I have found an answer for arbitrary $n$ and $k = 2$, ($k = 1$ is trivial), but I need a more general answer for any natural number  $k$ smaller than $n$. 

Yet another recurrence-relation based explanation: let $S_n$ be the number of strings of length $n$ which have some run of $k$ consecutive 1s in them, and let $s$ be a string in $S_n$; suppose $s'$ is the string $s$ truncated by one (i.e., with its last character removed). Then either $s'\in S_{n-1}$, or we have that $s'$ ends with a run of exactly $(k-1)$
 1s, with a 0 (or an empty string) before them; the remainder of the string (of length $n-(k+1)$) is then unconstrained except that it can't have any such run in it.  This gives a recurrence of the form $S_n = S_{n-1}+(2^{n-(k+1)}-S_{n-(k+1)})$; the starting conditions are then $S_i=0$ for $i\lt k$, $S_k=1$.  From here you can build a generating function
$\mathcal{S}(x)=\sum_iS_ix^i$, find an equation for the generating function, and proceed from there.
