Multinomial Theorem

From ProofWiki
Jump to: navigation, search

Theorem

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


Then:

$\displaystyle \left({x_1 + x_2 + \cdots + x_m}\right)^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 $P_m$ be the proposition:

$\displaystyle \forall n \in \N: \left({x_1 + x_2 + \cdots + x_m}\right)^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$:

\(\displaystyle \left({x_1}\right)^n\) \(=\) \(\displaystyle \sum_{k_1 \mathop = n} \frac {n!} {k_1!} {x_1}^{k_1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n!} {n!} {x_1}^n\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle {x_1}^n\) $\quad$ $\quad$

and so it is seen that $P_1$ holds.

This is the basis for the induction.


Induction Hypothesis

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


So this is the induction hypothesis:

$\displaystyle \forall n \in \N: \left({x_1 + x_2 + \cdots + x_r}\right)^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:

$\displaystyle \forall n \in \N: \left({x_1 + x_2 + \cdots + x_r + x_{r + 1} }\right)^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

\(\displaystyle \) \(\) \(\displaystyle \left({x_1 + x_2 + \cdots + x_r + x_{r + 1} }\right)^n\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({\left({x_1 + x_2 + \cdots + x_r}\right) + x_{r + 1} }\right)^n\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{j \mathop = 0}^n \binom n j {x_{r + 1} }^j \left({x_1 + x_2 + \cdots + x_r}\right)^{n - j}\) $\quad$ Binomial Theorem $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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}\) $\quad$ Induction Hypothesis $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{j \mathop = 0}^n \left({\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}\right)\) $\quad$ Summation is Linear $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k_{r + 1} \mathop = 0}^n \left({\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} }\right)\) $\quad$ renaming index variable $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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} }\) $\quad$ collapsing the double sum $\quad$


Now:

\(\displaystyle \binom n {k_{r + 1} } \binom {n - k_{r + 1} } {k_1, k_2, \ldots, k_r}\) \(=\) \(\displaystyle \frac {n!} {k_{r + 1}! \left({n - k_{r + 1} }\right)!} \frac {\left({n - k_{r + 1} }\right)!} {k_1! \, k_2! \, \cdots k_r!}\) $\quad$ Definition of Binomial Coefficient and Definition of Multinomial Coefficient $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {n!} {k_1! \, k_2! \, \cdots k_r! \, k_{r + 1}!}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \binom n {k_1, k_2, \ldots, k_r, k_{r + 1} }\) $\quad$ Definition of Multinomial Coefficient $\quad$


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

$\blacksquare$


Sources