multinomial theorem (proof)

Proof. The below proof of the multinomial theorem usesthe 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

${(x_1+\mathrm{\cdots }+x_k+x_{k+1})}^n$$=$${\displaystyle \sum _{l=0}^n}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{l}}\right){(x_1+\mathrm{\cdots }+x_k)}^l{x}_{k+1}^{n-l}$

$=$${\displaystyle \sum _{l=0}^n}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{l}}\right)l!{\displaystyle \sum _{|i|=l}}{\displaystyle \frac{x^i}{i!}}{x}_{k+1}^{n-l}$

$=$$n!{\displaystyle \sum _{l=0}^n}{\displaystyle \sum _{|i|=l}}{\displaystyle \frac{x^i{x}_{k+1}^{n-l}}{i!(n-l)!}}$

where $x=(x_1,\mathrm{\dots },x_k)$ and $i$ is a multi-index in $I_{+}^k$. To complete the proof, we need to show thatthe sets

$A$$=$$\mathrm{\{}(i_1,\mathrm{\dots },i_k,n-l)\in I_{+}^{k+1}\mid l=0,\mathrm{\dots },n,|(i_1,\mathrm{\dots },i_k)|=l\},$

$B$$=$$\mathrm{\{}j\in I_{+}^{k+1}\mid |j|=n\}$

are equal.The inclusion $A\subset B$ is clear since

$$|(i_1,\mathrm{\dots },i_k,n-l)|=l+n-l=n.$$

For $B\subset A$, suppose $j=(j_1,\mathrm{\dots },j_{k+1})\in I_{+}^{k+1}$,and $|j|=n$. Let $l=|(j_1,\mathrm{\dots },j_k)|$. Then $l=n-j_{k+1}$,so $j_{k+1}=n-l$ for some $l=0,\mathrm{\dots },n$.It follows that that $A=B$.

Let us define $y=(x_1,\mathrm{\cdots },x_{k+1})$ and let$j=(j_1,\mathrm{\dots },j_{k+1})$ be a multi-index in $I_{+}^{k+1}$.Then

${(x_1+\mathrm{\cdots }+x_{k+1})}^n$$=$$n!{\displaystyle \sum _{|j|=n}}{\displaystyle \frac{x^{(j_1,\mathrm{\dots },j_k)}{x}_{k+1}^{j_{k+1}}}{(j_1,\mathrm{\dots },j_k)!j_{k+1}!}}$

$=$$n!{\displaystyle \sum _{|j|=n}}{\displaystyle \frac{y^j}{j!}}.$

This completes the proof. $\mathrm{\square }$