1. **Problem Statement:** Find the generating function for the number of runs of 1 in binary strings of size $n$. 2. **Understanding the Problem:** A run of 1s is a maximal consecutive sequence of 1s in a binary string. For example, in the string 1101110, there are two runs of 1s: "11" and "111". 3. **Approach:** We want a generating function $G(x,y)$ where the coefficient of $x^n y^k$ counts the number of binary strings of length $n$ with exactly $k$ runs of 1s. 4. **Key Insight:** A binary string can be viewed as alternating runs of 0s and 1s. Runs of 1s are separated by runs of 0s (possibly empty at the start or end). 5. **Constructing the generating function:** - Let $x$ mark the length of the string. - Let $y$ mark the number of runs of 1s. 6. **Generating function for runs of 0s:** $$Z(x) = 1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}$$ 7. **Generating function for runs of 1s:** Each run of 1s has length at least 1: $$R(x,y) = y(x + x^2 + x^3 + \cdots) = y \frac{x}{1-x}$$ 8. **Form of binary strings:** They are sequences of alternating runs of 0s and 1s, starting and ending with runs of 0s or 1s. 9. **Generating function for binary strings with runs of 1s counted:** $$G(x,y) = \frac{1}{1 - Z(x) R(x,y)} Z(x) = \frac{1}{1 - \frac{1}{1-x} \cdot y \frac{x}{1-x}} \cdot \frac{1}{1-x}$$ 10. **Simplify:** $$G(x,y) = \frac{1}{1 - \frac{y x}{(1-x)^2}} \cdot \frac{1}{1-x} = \frac{1}{1-x} \cdot \frac{1}{1 - \frac{y x}{(1-x)^2}} = \frac{1}{1-x - y x/(1-x)} = \frac{1-x}{1 - 2x + x^2 - y x}$$ **Final generating function:** $$\boxed{G(x,y) = \frac{1-x}{1 - 2x + x^2 - y x}}$$ This function generates the number of binary strings of length $n$ with $k$ runs of 1s as the coefficient of $x^n y^k$.