Proof. The below proof of the multinomial theorem uses the binomial theorem and induction on $k$ . In addition, we shall use multi-index notation.

First, for $k=1$ , both sides equal $x_1^n$ . For the induction step, suppose the multinomial theorem holds for $k$ . Then the binomial theorem and the induction assumption yield \begin{eqnarray*} (x_1+\cdots + x_k\,+\,x_{k+1})^n &=& \sum_{l=0}^n {n \choose l} (x_1+\cdots + x_k)^l x_{k+1}^{n-l}\\ &=& \sum_{l=0}^n {n \choose l} l! \sum_{|i|=l} \frac{x^i}{i!} x_{k+1}^{n-l}\\ &=& n! \sum_{l=0}^n \sum_{|i|=l} \frac{x^i x_{k+1}^{n-l}}{i! (n-l)!} \\ \end{eqnarray*}where $x=(x_1,\ldots, x_k)$ and $i$ is a multi-index in $I^k_+$ . To complete the proof, we need to show that the sets \begin{eqnarray*} A&=&\{ (i_1,\ldots,i_k, n-l)\in I^{k+1}_+ \mid l=0,\ldots, n,\, |(i_1,\ldots, i_k)|=l \}, \\ B&=&\{j \in I^{k+1}_+ \mid |j|=n \} \end{eqnarray*}are equal. The inclusion $A \subset B$ is clear since $$ |(i_1,\ldots,i_k, n-l)| = l + n-l = n.$$ For $B \subset A$ , suppose $j=(j_1,\ldots, j_{k+1}) \in I^{k+1}_+$ , and $|j|=n$ . Let $l=|(j_1,\ldots, j_k)|$ . Then $l=n-j_{k+1}$ , so $j_{k+1} = n-l$ for some $l=0,\ldots, n$ . It follows that that $A=B$ .

Let us define $y=(x_1,\cdots, x_{k+1})$ and let $j=(j_1,\ldots, j_{k+1})$ be a multi-index in $I_+^{k+1}$ . Then \begin{eqnarray*} (x_1+\cdots + x_{k+1})^n &=& n! \sum_{|j|=n} \frac{x^{(j_1,\ldots, j_k)} x_{k+1}^{j_{k+1}}}{(j_1,\ldots, j_k)! j_{k+1}!} \\ &=& n! \sum_{|j|=n} \frac{y^j}{j!}. \end{eqnarray*}This completes the proof.