The ordinary generating function for words whose longest run has length $\le k$

Question

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?

Answer 1

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}. $$

Answer 2

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}}.$$