What is the basic lemma on composition of probability generating functions? What is the basic lemma on composition of probability generating functions and how is it most clearly proved?
(I'm posting this mainly to see if I can write an answer as clearly and simply as possible, but maybe other people know things about this that I don't and can post answers from their points of view.)
 A: Do you mean this?  Let $S = \sum_{i\le N} Y_i$ where $N, Y_1, Y_2, \ldots$ are independent integer-valued random variables where $N\ge 0$ a.s., and $\mathbb E[z^N] = f(z)$ while $\mathbb E[z^{Y_i}] = g(z)$, then
$$ \mathbb E[z^S] = f(g(z))$$
A: Suppose a random variable $X$ takes values in the set $\{0,1,2,3,\ldots\},$ each finite cardinal number having a probability assigned to it, their sum being $1.$
The ordinary generating function of this sequence of probabilities is
$$
g_X(s) = \sum_{x=0}^\infty \Pr(X=x) s^x = \operatorname E(s^X).
$$
It is routine to see that if $X,Y$ are independent random variables then
\begin{align*}
& g_{X+Y}(s) = \operatorname E(s^{X+Y}) \\[8pt]
= {} & \operatorname E(s^X) \operatorname E(s^Y) & & \text{by independence} \\[8pt]
= {} & g_X(s) g_Y(s).
\end{align*}
(This simplicity of this argument is something that I actually missed in a recent stackexchange posting because my attention at that moment was on other aspects of my topic.)
Lemma: Suppose $X$ is as above and $Y_1,Y_2,Y_3,\ldots$ are identically distributed, also taking values in $\{0,1,2,3,\ldots\}$ and $X, Y_1,Y_2, Y_3,\ldots$ are independent. Let $g_Y$ denote the probability generating function of any of $Y_1,Y_2,Y_3,\ldots\,.$ Let
$$
Z = \sum_{n=1}^X Y_n.
$$
Then $g_Z(s) = g_X(g_Y(s)).$
Proof:
\begin{align}
g_Z(s) & = \operatorname E(s^Z) = \operatorname E(\operatorname E(s^Z \mid X)) \\[8pt]
& = \operatorname E( \operatorname E(s^{Y_1+\cdots+Y_X} \mid X)) \\[8pt]
& = \operatorname E( g_Y(s)^X ) & &\text{(This follows from} \\
& & & \phantom{\text{(}}\text{the “routine'' thing} \\
& & & \phantom{\text{(}}\text{mentioned above.)} \\[8pt]
& = g_X(g_Y(s)).
\end{align}
