Multinomial Theorem

Theorem

Let $x_1, x_2, \ldots, x_k \in F$, where $F$ is a field.

Then:

$\ds \paren {x_1 + x_2 + \cdots + x_m}^n = \sum_{k_1 \mathop + k_2 \mathop + \mathop \cdots \mathop + k_m \mathop = 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 \in \Z_{> 0}$ is a positive integer
$n \in \Z_{\ge 0}$ is a non-negative integer
$\dbinom n {k_1, k_2, \ldots, k_m} = \dfrac {n!} {k_1! \, k_2! \, \cdots k_m!}$ denotes a multinomial coefficient.

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$, and with the understanding that wherever $0^0$ may appear it shall be considered to have a value of $1$.

The multinomial theorem is a generalization of the Binomial Theorem.

Proof

The proof proceeds by induction on $m$.

For each $m \in \N_{\ge 1}$, let $\map P m$ be the proposition:

$\ds \forall n \in \N: \paren {x_1 + x_2 + \cdots + x_m}^n = \sum_{k_1 \mathop + k_2 \mathop + \mathop \cdots \mathop + k_m \mathop = n} \binom n {k_1, k_2, \ldots, k_m} {x_1}^{k_1} {x_2}^{k_2} \cdots {x_m}^{k_m}$

Basis for the Induction

Trivially, for all $n \in \N$:

 $\ds \paren {x_1}^n$ $=$ $\ds \sum_{k_1 \mathop = n} \frac {n!} {k_1!} {x_1}^{k_1}$ $\ds$ $=$ $\ds \frac {n!} {n!} {x_1}^n$ $\ds$ $=$ $\ds {x_1}^n$

and so it is seen that $\map P 1$ holds.

This is the basis for the induction.

Induction Hypothesis

Now it needs to be shown that, if $\map P r$ is true, where $r \ge 1$, then it logically follows that $\map P {r + 1}$ is true.

So this is the induction hypothesis:

$\ds \forall n \in \N: \paren {x_1 + x_2 + \cdots + x_r}^n = \sum_{k_1 \mathop + k_2 \mathop + \mathop \cdots \mathop + k_r \mathop = n} \binom n {k_1, k_2, \ldots, k_r} {x_1}^{k_1} {x_2}^{k_2} \cdots {x_r}^{k_r}$

from which it is to be shown that:

$\ds \forall n \in \N: \paren {x_1 + x_2 + \cdots + x_r + x_{r + 1} }^n = \sum_{k_1 \mathop + k_2 \mathop + \mathop \cdots \mathop + k_r \mathop + k_{r + 1} \mathop = n} \binom n {k_1, k_2, \ldots, k_r, k_{r + 1} } {x_1}^{k_1} {x_2}^{k_2} \cdots {x_r}^{k_r} {x_{r + 1} }^{k_{r + 1} }$

Induction Step

 $\ds$  $\ds \paren {x_1 + x_2 + \cdots + x_r + x_{r + 1} }^n$ $\ds$ $=$ $\ds \paren {\paren {x_1 + x_2 + \cdots + x_r} + x_{r + 1} }^n$ $\ds$ $=$ $\ds \sum_{j \mathop = 0}^n \binom n j {x_{r + 1} }^j \paren {x_1 + x_2 + \cdots + x_r}^{n - j}$ Binomial Theorem $\ds$ $=$ $\ds \sum_{j \mathop = 0}^n \binom n j {x_{r + 1} }^j \sum_{k_1 + k_2 + \cdots + k_r \mathop = n - j} \binom {n - j} {k_1, k_2, \ldots, k_r} {x_1}^{k_1} {x_2}^{k_2} \cdots {x_r}^{k_r}$ Induction Hypothesis $\ds$ $=$ $\ds \sum_{j \mathop = 0}^n \paren {\sum_{k_1 + k_2 + \cdots + k_r \mathop = n - j} \binom n j \binom {n - j} {k_1, k_2, \ldots, k_r} {x_1}^{k_1} {x_2}^{k_2} \cdots {x_r}^{k_r} {x_{r + 1} }^j}$ Summation is Linear $\ds$ $=$ $\ds \sum_{k_{r + 1} \mathop = 0}^n \paren {\sum_{k_1 + k_2 + \cdots + k_r \mathop = n - k_{r + 1} } \binom n {k_{r + 1} } \binom {n - k_{r + 1} } {k_1, k_2, \ldots, k_r} {x_1}^{k_1} {x_2}^{k_2} \cdots {x_r}^{k_r} {x_{r + 1} }^k_{r + 1} }$ renaming index variable $\ds$ $=$ $\ds \sum_{k_1 + k_2 + \cdots + k_r + k_{r + 1} \mathop = n} \binom n {k_{r + 1} } \binom {n - k_{r + 1} } {k_1, k_2, \ldots, k_r} {x_1}^{k_1} {x_2}^{k_2} \cdots {x_r}^{k_r} {x_{r + 1} }^{k_{r + 1} }$ collapsing the double sum

Now:

 $\ds \binom n {k_{r + 1} } \binom {n - k_{r + 1} } {k_1, k_2, \ldots, k_r}$ $=$ $\ds \frac {n!} {k_{r + 1}! \paren {n - k_{r + 1} }!} \frac {\paren {n - k_{r + 1} }!} {k_1! \, k_2! \, \cdots k_r!}$ Definition of Binomial Coefficient and Definition of Multinomial Coefficient $\ds$ $=$ $\ds \dfrac {n!} {k_1! \, k_2! \, \cdots k_r! \, k_{r + 1}!}$ $\ds$ $=$ $\ds \binom n {k_1, k_2, \ldots, k_r, k_{r + 1} }$ Definition of Multinomial Coefficient

So $\map P r \implies \map P {r + 1}$ and the result follows by the Principle of Mathematical Induction.

$\blacksquare$