Proof of The Multinomial Theorem in a Commutative Ring

For $p\in\mathbb{N}$ and $s\in\mathbb{N}_{0}$ write

$$K_{p}(s)=\{k\in\mathbb{N}_{0}^{p}:k_{1}+\dots+k_{p}=s\},$$

so that $K=K_{m}(n)$; for $k\in K_{p}(s)$ we write the multinomial coefficient $\binom{k_{1}+\dots+k_{p}}{k_{1},\dots,k_{p}}$ as $\binom{s}{k_{1},\dots,k_{p}}$. Throughout, $K_{p}(s)$ is finite by Counting Tuples with a Given Sum (i), applied with $p=q+1$ for the $q\in\mathbb{N}_{0}$ given by $1\le p$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (v), Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (vii)); $x_{1}+\dots+x_{p}=\sum_{i=1}^{p}x_{i}$ and $x_{1}^{k_{1}}\cdots x_{p}^{k_{p}}=\prod_{i=1}^{p}x_{i}^{k_{i}}$ are formed in $R$; and for $k\in\mathbb{N}_{0}^{p}$ and $j\in\mathbb{N}_{0}$, $(k_{1},\dots,k_{p},j)$ is the tuple of Finite Sets: Removing an Element, Injective Self-Maps, Infinite Sets, Sets of Permutations, Pairs and Extended Tuples (vi), so that $(k,j)\mapsto(k_{1},\dots,k_{p},j)$ is a bijection from $\mathbb{N}_{0}^{p}\times\mathbb{N}_{0}$ onto $\mathbb{N}_{0}^{p+1}$. We prove the theorem by induction on $m$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (viii)), for all $n\in\mathbb{N}_{0}$ and all $x_{1},\dots,x_{m}\in R$.

Step 1 (one summand). Let $m=1$. Since $[1]=\{1\}$, sums and products over $[1]$ have the single term at $1$ (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (i)): the left side is $x_{1}^{n}$, and $K_{1}(n)$ consists of the $1$-tuples with $k_{1}=n$, of which there is exactly one, the map on $[1]$ with value $n$ (Maps Formed Pointwise: Constant Maps, Pairs of Values, Maps Applied to Values, and Families of Maps (i)). Its multinomial coefficient is $\binom{n}{n}=1$, the only $M\in\mathbb{N}_{0}$ with $M\cdot n!=n!$ (The Multinomial Coefficient (i), Existence and Uniqueness of the Multinomial Coefficients (i), Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (iii)). So the right side is $1\cdot x_{1}^{n}=x_{1}^{n}$, again by Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (i).

Step 2 (binomial expansion). Assume the theorem for $m$, and let $x_{1},\dots,x_{m+1}\in R$ and $n\in\mathbb{N}_{0}$. Put $s=x_{1}+\dots+x_{m}$, so that $x_{1}+\dots+x_{m+1}=s+x_{m+1}$ (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (vii)). By The Binomial Theorem in a Commutative Ring (i) with $x=x_{m+1}$ and $y=s$, and the induction hypothesis applied to $s^{n-j}$ for each $j\in\{0,\dots,n\}$,

$$(x_{1}+\dots+x_{m+1})^{n}=\sum_{j=0}^{n}\binom{n}{j}x_{m+1}^{j}\,s^{n-j}=\sum_{j=0}^{n}\binom{n}{j}x_{m+1}^{j}\sum_{k\in K_{m}(n-j)}\binom{n-j}{k_{1},\dots,k_{m}}x_{1}^{k_{1}}\cdots x_{m}^{k_{m}}.$$

Step 3 (one sum over pairs). For $j\in\{0,\dots,n\}$ and $k\in K_{m}(n-j)$ let

$$u(j,k)=\binom{n}{j}\binom{n-j}{k_{1},\dots,k_{m}}x_{1}^{k_{1}}\cdots x_{m}^{k_{m}}\,x_{m+1}^{j}.$$

Moving the factor $\binom{n}{j}x_{m+1}^{j}$ into the inner sum (Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (i)) and writing the double sum as one sum over the set $T$ of pairs $(j,k)$ with $j\in\{0,\dots,n\}$ and $k\in K_{m}(n-j)$ (Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (vi), over the finite index set $\{0,\dots,n\}$ of Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (vii), for the family $(K_{m}(n-j))_{j\in\{0,\dots,n\}}$), Step 2 becomes

$$(x_{1}+\dots+x_{m+1})^{n}=\sum_{(j,k)\in T}u(j,k).$$

Step 4 (appending the last exponent is a bijection $T\to K_{m+1}(n)$). Let $\Phi(j,k)=(k_{1},\dots,k_{m},j)$. For $(j,k)\in T$ the entries of $\Phi(j,k)$ add up to $(k_{1}+\dots+k_{m})+j=(n-j)+j=n$ (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (vii), The Difference of Two Natural Numbers with Zero (i)), so $\Phi$ maps $T$ into $K_{m+1}(n)$. It is injective because the bijection of Finite Sets: Removing an Element, Injective Self-Maps, Infinite Sets, Sets of Permutations, Pairs and Extended Tuples (vi) is. It is onto $K_{m+1}(n)$: every $k'\in K_{m+1}(n)$ is $(k_{1},\dots,k_{m},j)$ for some $k\in\mathbb{N}_{0}^{m}$ and $j\in\mathbb{N}_{0}$, and then $(k_{1}+\dots+k_{m})+j=n$; hence $j\le n$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (vii) and $k_{1}+\dots+k_{m}=n-j$ by The Difference of Two Natural Numbers with Zero (i), that is, $(j,k)\in T$ and $\Phi(j,k)=k'$.

Step 5 (matching the terms). Let $(j,k)\in T$ and $k'=\Phi(j,k)$, so $k'_{i}=k_{i}$ for $i\in[m]$ and $k'_{m+1}=j$. By Multinomial Coefficients: Binomial Products and Counting (i), with $k_{m+1}=j$, and since $k_{1}+\dots+k_{m}=n-j$ and $k'_{1}+\dots+k'_{m+1}=n$ by Step 4,

$$\binom{n}{k'_{1},\dots,k'_{m+1}}=\binom{n-j}{k_{1},\dots,k_{m}}\binom{n}{j}$$

in $\mathbb{N}_{0}$, and hence in $R$ (The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (iii)). Splitting off the last factor of the monomial (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (vii)),

$$x_{1}^{k'_{1}}\cdots x_{m+1}^{k'_{m+1}}=x_{1}^{k_{1}}\cdots x_{m}^{k_{m}}\,x_{m+1}^{j}.$$

Therefore $u(j,k)=f(\Phi(j,k))$ for $f(k')=\binom{n}{k'_{1},\dots,k'_{m+1}}x_{1}^{k'_{1}}\cdots x_{m+1}^{k'_{m+1}}$ on $K_{m+1}(n)$.

Step 6 (the claim for $m+1$). By Steps 3 to 5 and Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (iii), applied to the addition of $R$ and the bijection $\Phi:T\to K_{m+1}(n)$,

$$(x_{1}+\dots+x_{m+1})^{n}=\sum_{(j,k)\in T}f(\Phi(j,k))=\sum_{k'\in K_{m+1}(n)}\binom{n}{k'_{1},\dots,k'_{m+1}}x_{1}^{k'_{1}}\cdots x_{m+1}^{k'_{m+1}},$$

which is the theorem for $m+1$ and completes the induction.