# multinomial theorem (proof)

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

 $\displaystyle(x_{1}+\cdots+x_{k}\,+\,x_{k+1})^{n}$ $\displaystyle=$ $\displaystyle\sum_{l=0}^{n}{n\choose l}(x_{1}+\cdots+x_{k})^{l}x_{k+1}^{n-l}$ $\displaystyle=$ $\displaystyle\sum_{l=0}^{n}{n\choose l}l!\sum_{|i|=l}\frac{x^{i}}{i!}x_{k+1}^{% n-l}$ $\displaystyle=$ $\displaystyle n!\sum_{l=0}^{n}\sum_{|i|=l}\frac{x^{i}x_{k+1}^{n-l}}{i!(n-l)!}$

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

 $\displaystyle A$ $\displaystyle=$ $\displaystyle\{(i_{1},\ldots,i_{k},n-l)\in I^{k+1}_{+}\mid l=0,\ldots,n,\,|(i_% {1},\ldots,i_{k})|=l\},$ $\displaystyle B$ $\displaystyle=$ $\displaystyle\{j\in I^{k+1}_{+}\mid|j|=n\}$

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

 $\displaystyle(x_{1}+\cdots+x_{k+1})^{n}$ $\displaystyle=$ $\displaystyle 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}!}$ $\displaystyle=$ $\displaystyle n!\sum_{|j|=n}\frac{y^{j}}{j!}.$

This completes the proof. $\Box$

Title multinomial theorem (proof) MultinomialTheoremproof 2013-03-22 13:41:55 2013-03-22 13:41:55 Koro (127) Koro (127) 4 Koro (127) Proof msc 05A10