PGF of sum of RVs is a composition of PGFs Let $\\\{X_n\\\}$ be a sequence of i.i.d. random variables whose
values are non-negative integers. Let $N$ be a random variable that is independent of $\\\{X_n\\\}$. $N$'s values are also non-negative integers. Let $S_N = \sum_{i = 1}^N X_i$.
Show that $P_{S_N}(z) = P_N(P_X(z)), z \in [0, 1]$.
$P_{S_N}(z) = \Pi_{i = 1}^N\sum_{x = 0}^{\infty} z^xP(X_i = x)$
$P_N(P_X(z)) = \sum_{x = 0}^{\infty} P_X(z)^x\frac{1}{x!}P_N(x)$
One side has a product of sums; the other is just a sum and I'm stuck. Could I please have some suggestions?
 A: One must remember while solving problems of these kind:
Generating function of a convolution is the product of the generating function.
Formally, if $\{a_j\},~\{b_j\}$ are two sequences with generating functions $\mathsf A(s), ~\mathsf B(s) ,$ then the generating function of $\{a_j\}\ast \{b_j\}$ is $\mathsf A(s)\ast\mathsf B(s). $
Assume the radius of convergence  of both $\mathsf A(s), ~\mathsf B(s)$ is same, say $s_0.$ Then by definition, generating function of the convolution is
$$ \sum_{n =0}^\infty \left(\sum_{k =0}^n a_kb_{n-k}\right) s^n,~~|s| < s_0;$$ interchange the order of summation by Fubini's theorem to get $$ \sum_{k =0}^\infty a_ks^k\sum_{n = k}^\infty b_{n-k}s^{n-k} = \mathsf A(s) \mathsf B(s). $$
From this, one can conclude for two independent non-negative integer valued rvs $X_1, X_2, $ the pgf of $X_1+X_2$ as
$$\mathsf P_{X_1+ X_2}(s) = \mathsf P_{X_1}(s)       
 \mathsf P_{X_2}(s). $$
Now coming to the main problem: let $\langle X_n\rangle_{n \geq 1}$ be iid, non-negative integer valued rvs and let $X_1\sim \{p_k\}.$ Let $N$ be non-negative integer valued with
$ \mathbb P[N = j] = \alpha_j.$ Then
\begin{align}
\mathbb P[S_N = j] &= \sum_{k = 0}^\infty \mathbb P[S_k = j, N = k]\\ &= \sum_{k = 0}^\infty \mathbb P[S_k = j]\mathbb P[N = k]\\ &=\sum_{k = 0}^\infty p_j^{k\ast}\alpha_k, 
\end{align}
$p_j^{k\ast}$ being the $j$ th element of the $k$ th convolution power of $\{p_k\}.$ Therefore
\begin{align}
\mathsf P_{S_N}(s) &= \sum_{j = 0}^\infty\mathbb P[S_N = j]s^j\\ &= \sum_{j = 0}^\infty\left(\sum_{k = 0}^\infty p_j^{k\ast}\alpha_k \right) s^j \\&= \sum_{k =0}^\infty \alpha_k\left( \sum_{j =0}^\infty p_j^{k\ast} s^j\right) \\ &= \sum_{k =0}^\infty \alpha_k\left( \sum_{j =0}^\infty \mathbb P[S_k = j]s^j\right) \\ &= \sum_{k = 0}^\infty \alpha_k(\mathsf P_{X_1}(s)) ^k\\ &= \mathsf P_N(\mathsf P_{X_1}(s)). 
\end{align}

Reference:
Adventures in Stochastic Processes, Sidney I. Resnick, Birkhäuser, 2005.
A: Conditional on $N=n$, using the fact that $X_1,X_2,\dots$ are independent and the definition of the the probability generating function (pgf),
\begin{align}
P_{S_N|N=n}(z)&=E(z^{S_N}|N=n) 
\\&=E(z^{X_1+X_2+\dots+X_n}|N=n)
\\&=Ez^{X_1}Ez^{X_2}\cdots Ez^{X_n} 
\\&=P_X(z)^n.
\end{align}
Hence, using the law of total expectation, and again, the definition of the pgf
\begin{align}
P_{S_N}(z)&=E(z^{S_N})
\\&=EE(z^{S_N}|N)
\\&=EP_X(z)^N
\\&=P_N(P_X(z)). 
\end{align}
