Multinomial Theorem

Theorem

$\displaystyle (x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+k_2\ldots+k_m=n} \binom n {k_1, k_2, \ldots, k_m} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m} $

where $m$ is a positive integer and $n$ is non-negative.

The sum is taken for all non-negative integers $k_1, k_2, \ldots, k_m$ such that $k_1 + k_2 + \cdots + k_m = n$.

Also:

$\displaystyle \binom n {k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!k_2!\ldots k_m!}$

The multinomial theorem is the generalization of the binomial theorem.

Proof

Proof by strong mathematical induction:

Base Case (m=1)

Trivial:

$\displaystyle (x_1)^n = \sum_{k_1=n} \frac{n!}{k_1!} x_1^{k_1} = \frac{n!}{n!} x_1^n = x_1^n $

Induction Hypothesis

$\displaystyle \forall m \in \N, m \ge 1: (x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+k_2\ldots+k_m=n} {n \choose k_1, k_2, \ldots, k_m} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}$

Induction Step

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle (x_1 + x_2 + \cdots + x_m + x_{m+1})^n\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle ((x_1 + x_2 + \cdots + x_m) + x_{m+1})^n\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{j=0}^n \binom n {j, n-j} x_{m+1}^j (x_1 + x_2 + \cdots + x_m)^{n-j}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by the binomial theorem
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{j=0}^n \binom n {j, n-j} x_{m+1}^j \sum_{k_1 + k_2 + \cdots + k_m = n-j} \binom {n-j} {k_1, k_2, \ldots, k_m} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by induction hypothesis
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{j=0}^n \sum_{k_1 + k_2 + \cdots + k_m = n-j} \binom n {j, n-j} \binom {n-j} {k_1, k_2, \ldots, k_m} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m} x_{m+1}^j\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{k_1 + k_2 + \cdots + k_m + k_{m+1} = n} \binom n {k_{m+1}, n-k_{m+1} } \binom {n-k_{m+1} } {k_1, k_2, \ldots, k_m} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}x_{m+1}^{k_{m+1} }\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Now,

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \binom n {k_{m+1}, n-k_{m+1} } {n-k_{m+1} \choose k_1, k_2, \ldots, k_m}\)	\(=\)	\(\displaystyle \frac{n!} {k_{m+1}! (n-k_{m+1})!} \frac{(n-k_{m+1})!} {k_1!k_2! \ldots, k_m!}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac{n!}{k_1! k_2! \ldots k_m! k_{m+1}!}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \binom n {k_1, k_2, \ldots, k_m, k_{m+1} }\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Therefore:

$\displaystyle (x_1 + x_2 + \cdots + x_m + x_{m+1})^n = \sum_{k_1 + k_2 + \cdots + k_m + k_{m+1} = n} \binom n {k_1, k_2, \ldots, k_m, k_{m+1}} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m} x_{m+1}^{k_{m+1}}$

$\blacksquare$