Out of all bit strings of length $N$, we need to count how many of them are there in which all the ones are present in a window of length $K$.
For this, my initial thought was:
The starting point of the window can be placed at $(N - K)$ positions. In each window, each bit can either be $1$ or $0$. The number of bit strings would then be $(N - K) * 2^k$.
However, there is over-counting involved in this method.
How do I solve this problem?
On
Let $a(n,k)$ be the number of bit strings of length $n$ having all of their ones in a window of length $k$. Suppose that we increase the length of the string to $n+1$; the only new allowable strings are those that have a $1$ in the $(n+1)$-st position, meaning that the window is the last $k$ bits, and there are exactly $2^{k-1}$ of those. Thus, we have the recurrence
$$a(n+1,k)=a(n,k)+2^{k-1}\;,$$
valid for $k\ge 1$. It’s also clear that $a(n,n)=2^n$ for $n\ge 1$. From these it’s straightforward to derive a closed form for $a(n,k)$; I’ve left it in the spoiler-protected block below in case you’d like to try finishing the argument yourself.
Thus, for $1\le k\le n$ we have $a(n,k)=2^k+(n-k)2^{k-1}=(n-k+2)2^{k-1}$.
There are $N+1$ bit strings of length $N$ having zero or one $1$s.
If such a bit string has $\geq2$ ones it has a first $1$ and a last $1$, and anything in between. Let $r\geq2$ be the length of the window determined by the first and the last $1$. There are $N-r+1$ positions of such a window along the string. The total number $n$ of admissible strings is therefore given by $$n=N+1+\sum_{r=2}^K(N-r+1)2^{r-2}\ .$$ When you compute the sum you'll obtain a result so simple that it makes you think whether there is not an easier solution.