The ordinary generating function for words whose longest run has length $\le k$ Consider words on the alphabet $X=\{a,b\}$.
a)  I have to show that the Ordinary Generating function (OGF) for words on $\{a,b\}$ whose longest run has length $\leqslant k$ (at most $k$) is:
$$
 W_{\leqslant k}(z)= \frac{1-z^{k+1}}{1-2z+z^{k+1}}= \frac{1+z+\dots+z^k}{1-z-\dots-z^k } 
$$
I know that I have to use the definition of the set of words:
$$ W(z)= \frac{1}{1-2z} 
$$
where $2$ is the cardinality of the alphabet, i.e. the number of letters.
I need to know how to use this information to find the ordinary generating function.
b) How likely is that a word of length $250$ contains a run of length $7$ or more?
 A: The OGF for words on $\{a,b\}$ with $n \ge 1$ runs total, each run of length between $1$ and $k$, is
$$
   2(z + z^2 + \dots + z^k)^n
$$
where the $2$ corresponds to choosing $a$ or $b$ to start with, and each factor of $(z + z^2 + \dots + z^k)$ corresponds to choosing the length of one of the runs.
Therefore the OGF without a condition on $n$ (including the word of length $0$) is
$$
    1 + \sum_{n \ge 1} 2(z + z^2 + \dots + z^k)^n = 1 + \frac{2(z + z^2 + \dots + z^k)}{1 - (z + z^2 + \dots + z^k)} = \frac{1 + z + z^2 + \dots + z^k}{1 - z - z^2 - \dots - z^k}.
$$
A: Let $s_n$ be the number of such words, with $s_0=1$ for the empty word.
By conditioning on the starting position $j$ of the first violation, we find for $n\ge 1$ that
$$s_n 
= 2^n-2^{n-k}[n \ge k+1]-\sum_{j=2}^{n-k} s_{j-1} 2^{n-j-k}. \tag1
$$
Now let $S(z)=\sum_{n \ge 0} s_n z^n$ be the OGF for $s_n$.  Then $(1)$ implies that
\begin{align}
S(z) - s_0  
&= \sum_{n\ge 1} \left(2^n-2^{n-k}[n \ge k+1]-\sum_{j=2}^{n-k} s_{j-1} 2^{n-j-k}\right) z^n \\
&= \sum_{n\ge 1} (2z)^n - 2^{-k} \sum_{n\ge k+1} (2z)^n - \sum_{j\ge 2} s_{j-1} 2^{-j-k} \sum_{n\ge j+k}  (2z)^n \\
&= \frac{2z}{1-2z} - \frac{2^{-k}(2z)^{k+1}}{1-2z} - \sum_{j\ge 2} s_{j-1} 2^{-j-k} \frac{(2z)^{j+k}}{1-2z} \\
&= \frac{2z}{1-2z} - \frac{2z^{k+1}}{1-2z} - \frac{z^{k+1}}{1-2z} (S(z)-s_0), \\
\end{align}
so
$$S(z) = 1 + \frac{\frac{2z-2z^{k+1}}{1-2z}}{1+\frac{z^{k+1}}{1-2z}}
= \frac{1-z^{k+1}}{1-2z+z^{k+1}}.$$
