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)
Canonical name	MultinomialTheoremproof
Date of creation	2013-03-22 13:41:55
Last modified on	2013-03-22 13:41:55
Owner	Koro (127)
Last modified by	Koro (127)
Numerical id	4
Author	Koro (127)
Entry type	Proof
Classification	msc 05A10