---
tag: X7C02HYY94
kind: proof
name: Proof of the multinomial theorem by induction on the number of terms
msc: [05A10]
proves: 0XFC1VQYEK
uses: [0GYGHKX834, 00K0RF9BFY, 0EHWPWGHB2, 033KTKKRV6, 0WFCGVMRRC]
methods: [0ASJVEFA9J]
sources:
  - url: https://proofwiki.org/wiki/Multinomial_Theorem
---

## Proof

We argue by induction on $m \ge 1$. The claim for $m$ is that the formula holds for this $m$, all $x_1, \dots, x_m \in R$ and all $n$. For an integer $c$ and $r \in R$, $c \cdot r$ is the repeated sum.

1. Let $m = 1$. The only tuple $(k_1)$ with $k_1 = n$ is $(n)$, and the [[multinomial coefficient|00K0RF9BFY]] is $\frac{n!}{n!} = 1$. So the right side is $x_1^n$, which is the left side.
2. Suppose the claim holds for $m$. Let $x_1, \dots, x_{m+1} \in R$, and put $s = x_1 + \dots + x_m$.
3. The ring $R$ is [[commutative|0GYGHKX834]]. By the [[binomial theorem|0EHWPWGHB2]], $(s + x_{m+1})^n = \sum_{j=0}^{n} \binom{n}{j} s^j x_{m+1}^{n-j}$.
4. By the induction hypothesis with exponent $j$, $s^j = \sum_{k_1 + \dots + k_m = j} \binom{j}{k_1, \dots, k_m} x_1^{k_1} \cdots x_m^{k_m}$.
5. Substituting and distributing gives $(s + x_{m+1})^n = \sum_{j=0}^{n} \sum_{k_1 + \dots + k_m = j} c \cdot x_1^{k_1} \cdots x_m^{k_m} x_{m+1}^{n-j}$, with $c = \binom{n}{j} \binom{j}{k_1, \dots, k_m}$.
6. By the [[factorial formula|033KTKKRV6]], $\binom{n}{j} = \frac{n!}{j!\,(n-j)!}$. The definition gives $\binom{j}{k_1, \dots, k_m} = \frac{j!}{k_1! \cdots k_m!}$.
7. The factor $j!$ cancels, so $c = \frac{n!}{k_1! \cdots k_m!\,(n-j)!} = \binom{n}{k_1, \dots, k_m, n-j}$.
8. Put $k_{m+1} = n - j$. The pairs $(j, (k_1, \dots, k_m))$ with $0 \le j \le n$ and $k_1 + \dots + k_m = j$ correspond to the $(m+1)$-tuples with $k_1 + \dots + k_{m+1} = n$.
9. The inverse of this correspondence sends $(k_1, \dots, k_{m+1})$ to $j = k_1 + \dots + k_m = n - k_{m+1}$. So each $(m+1)$-tuple appears exactly once.
10. Rewriting the double sum of step 5 with steps 7 to 9 gives $(x_1 + \dots + x_{m+1})^n = \sum_{k_1 + \dots + k_{m+1} = n} \binom{n}{k_1, \dots, k_{m+1}} x_1^{k_1} \cdots x_{m+1}^{k_{m+1}}$.
11. This completes the induction.

## Idea

Group the first $m$ terms into one term $s$ and expand $(s + x_{m+1})^n$ with the binomial theorem.
Each power of $s$ is expanded by the induction hypothesis.
The binomial coefficient times the smaller multinomial coefficient is the larger multinomial coefficient, because the factor $j!$ cancels.