[proofplan] We condition on $N$ to decompose $\mathbb{E}[z^{S_N}]$ as a sum over possible values of $N$. When $N = n$, the sum $S_N = X_1 + \cdots + X_n$ is a fixed-length sum of i.i.d. variables, so by the PGF product rule for independent variables, $\mathbb{E}[z^{S_n}] = (G_X(z))^n$. Summing over $n$ with weights $\mathbb{P}(N = n)$ yields $G_N(G_X(z))$. [/proofplan] [step:Condition on the value of $N$ to decompose $G_{S_N}(z)$] By the [law of total expectation](/theorems/1121), conditioning on $N$, \begin{align*} G_{S_N}(z) = \mathbb{E}[z^{S_N}] = \sum_{n=0}^{\infty} \mathbb{E}[z^{S_N} \mid N = n]\, \mathbb{P}(N = n). \end{align*} When $N = n$, the sum $S_N = X_1 + X_2 + \cdots + X_n$ (with the convention $S_0 = 0$), so \begin{align*} \mathbb{E}[z^{S_N} \mid N = n] = \mathbb{E}[z^{X_1 + \cdots + X_n} \mid N = n]. \end{align*} [guided] Why condition on $N$? The random variable $S_N = X_1 + \cdots + X_N$ involves a random number of summands, which makes direct computation of $\mathbb{E}[z^{S_N}]$ difficult. Conditioning on $N = n$ replaces the random upper limit with a fixed integer, reducing the problem to a sum of a deterministic number of i.i.d. random variables — a situation we already know how to handle via the PGF product rule. By the law of total expectation, \begin{align*} G_{S_N}(z) = \mathbb{E}[z^{S_N}] = \sum_{n=0}^{\infty} \mathbb{E}[z^{S_N} \mid N = n]\, \mathbb{P}(N = n). \end{align*} When $N = n$, we have $S_N = X_1 + X_2 + \cdots + X_n$ (with $S_0 = 0$), so \begin{align*} \mathbb{E}[z^{S_N} \mid N = n] = \mathbb{E}[z^{X_1 + \cdots + X_n} \mid N = n]. \end{align*} [/guided] [/step] [step:Use independence of $N$ from the $X_i$ to factor the conditional expectation] Since $N$ is independent of the sequence $(X_1, X_2, \ldots)$, conditioning on $N = n$ does not affect the joint distribution of $X_1, \ldots, X_n$. Therefore \begin{align*} \mathbb{E}[z^{X_1 + \cdots + X_n} \mid N = n] = \mathbb{E}[z^{X_1 + \cdots + X_n}]. \end{align*} Since $X_1, \ldots, X_n$ are independent (and each has pgf $G_X$), the expectation of the product factors: \begin{align*} \mathbb{E}[z^{X_1 + \cdots + X_n}] = \mathbb{E}[z^{X_1}] \cdot \mathbb{E}[z^{X_2}] \cdots \mathbb{E}[z^{X_n}] = (G_X(z))^n. \end{align*} For $n = 0$, the empty product convention gives $(G_X(z))^0 = 1 = z^0 = z^{S_0}$, consistent with $S_0 = 0$. [guided] The key point is that $N$ is independent of the $X_i$, so conditioning on $N = n$ does not change the distribution of $(X_1, \ldots, X_n)$. This allows us to drop the conditioning: \begin{align*} \mathbb{E}[z^{X_1 + \cdots + X_n} \mid N = n] = \mathbb{E}[z^{X_1 + \cdots + X_n}]. \end{align*} Now we have a fixed-length sum of independent random variables. Writing $z^{X_1 + \cdots + X_n} = z^{X_1} \cdot z^{X_2} \cdots z^{X_n}$ and using the fact that expectations of products of independent random variables factorise, \begin{align*} \mathbb{E}[z^{X_1 + \cdots + X_n}] = \prod_{i=1}^{n} \mathbb{E}[z^{X_i}] = (G_X(z))^n, \end{align*} where the last equality uses the assumption that the $X_i$ are identically distributed with common pgf $G_X$. [/guided] [/step] [step:Sum over $n$ to recognise $G_N$ evaluated at $G_X(z)$] Substituting back into the total expectation, \begin{align*} G_{S_N}(z) = \sum_{n=0}^{\infty} (G_X(z))^n \, \mathbb{P}(N = n). \end{align*} For $z \in [0, 1]$, we have $G_X(z) \in [0, 1]$ (since $G_X$ maps $[0,1]$ to $[0,1]$). Writing $w = G_X(z)$, the right-hand side is \begin{align*} \sum_{n=0}^{\infty} w^n \, \mathbb{P}(N = n) = G_N(w) = G_N(G_X(z)). \end{align*} [/step]