1. **Problem Statement:** Find the number of runs of 1 of length $m$ in a random binary string of length $n$ using generating functions. 2. **Understanding the problem:** A run of 1s of length $m$ is a consecutive sequence of exactly $m$ ones, bounded by zeros or string ends. 3. **Generating function approach:** Let $x$ mark the length of the string and $y$ mark the number of runs of 1s of length $m$. 4. **Constructing the generating function:** We consider blocks of zeros and runs of ones. - A run of 1s of length exactly $m$ contributes $y x^m$. - Runs of 1s of length different from $m$ do not contribute to $y$. 5. **Generating function for runs of ones:** $$R(x,y) = 1 + x + x^2 + \cdots + x^{m-1} + y x^m + x^{m+1} + x^{m+2} + \cdots = \frac{1 - x^m}{1 - x} + y x^m + \frac{x^{m+1}}{1 - x} - x^m$$ Simplify: $$R(x,y) = \frac{1 - x^m}{1 - x} + y x^m + \frac{x^{m+1}}{1 - x} - x^m = \frac{1 - x^m + x^{m+1}}{1 - x} + (y - 1) x^m$$ 6. **Generating function for zeros:** $$Z(x) = \frac{1}{1 - x}$$ 7. **Full generating function for binary strings:** Binary strings are sequences of alternating zero-blocks and one-runs: $$G(x,y) = \frac{1}{1 - x} \cdot \frac{1}{1 - (R(x,y) - 1) \cdot Z(x)}$$ 8. **Simplify the denominator:** $$(R(x,y) - 1) Z(x) = \left(\frac{1 - x^m + x^{m+1}}{1 - x} + (y - 1) x^m - 1\right) \cdot \frac{1}{1 - x}$$ 9. **Extract coefficient:** The coefficient of $x^n y^k$ in $G(x,y)$ gives the number of binary strings of length $n$ with exactly $k$ runs of 1s of length $m$. 10. **Final answer:** The generating function $G(x,y)$ encodes the count of runs of 1s of length $m$ in binary strings of length $n$. Extracting coefficients from $G(x,y)$ yields the desired counts. This method uses generating functions to count runs of 1s of length $m$ in binary strings of length $n$.