Proof of Multinomial Theorem

Write $C(d;n_1,\dots,n_m)=d!/(n_1!\cdots n_m!)$ for $(n_1,\dots,n_m)\in\mathbb{N}_0^m$ with $n_1+\dots+n_m=d$, using the factorial with the convention $0!=1$ stated in the lemma. We argue by induction on $d$ for fixed $m$ and $a_1,\dots,a_m$, writing $s=a_1+\dots+a_m$.

Base case $d=0$. By the convention $x^{0}=1$, the left side is $1$. The only tuple of nonnegative integers summing to $0$ is $(0,\dots,0)$, whose term is $\frac{0!}{0!\cdots0!}\prod_j a_j^{0}=1$. So both sides equal $1$.

Induction step. Assume the identity for some $d\in\mathbb{N}_0$. Then

by distributivity over these finite sums. For fixed $j$ and $n$, we have $a_j\prod_l a_l^{n_l}=\prod_l a_l^{n'_l}$ where $n'=n+e_j$ and $e_j$ is the tuple with $1$ in entry $j$ and $0$ elsewhere. The map $(j,n)\mapsto(j,n+e_j)$ is a bijection from pairs (index $j$, tuple $n$ summing to $d$) to pairs (index $j$, tuple $n'$ summing to $d+1$ with $n'_j\ge1$): its inverse is $(j,n')\mapsto(j,n'-e_j)$. Regrouping the (finite) double sum by the value of $n'$ therefore gives

It remains to evaluate the inner sum. For $n'_j\ge1$, the recursion $n'_j!=n'_j\cdot(n'_j-1)!$ from Factorial of a Natural Number (valid also for $n'_j=1$ by the convention $0!=1$) gives

Since the right-hand expression vanishes when $n'_j=0$, we may sum over all $j$ from $1$ to $m$:

using $n'_1+\dots+n'_m=d+1$ and $(d+1)!=(d+1)\cdot d!$ from Factorial of a Natural Number. Substituting this into the displayed expression for $s^{d+1}$ yields the identity for $d+1$, completing the induction. $\blacksquare$