Proof of The Binomial Theorem in a Commutative Ring

Each result cited below is universally quantified over the data in its own statement, and is applied to the data named where it is cited.

Conventions. By The Binomial Coefficient §binomial, $\binom{n}{k}=C(n,k)$, where $C$ is the map of Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry §recursion, which is unique by that clause. Standing as a factor next to elements of $R$, $C(n,k)$ denotes its image $C(n,k)_{R}$ in $R$ by Commutative Rings, Fields and Ordered Fields: Standard Notation §numerals, while exponents such as $n-k$ are differences in $\mathbb{N}_{0}$. The ring laws of Commutative Rings §ring (associativity, commutativity, distributivity, $z+0=z$, $z\cdot1=z$) are used without further mention, as are the laws of arithmetic of $\mathbb{N}_{0}$ of The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §laws. Sums over intervals are as in Commutative Rings, Fields and Ordered Fields: Standard Notation §rings; they are defined also over empty intervals, as $+$ has the neutral element $0$. For $N\in\mathbb{N}_{0}$ and $k\in\{0,\dots,N\}$ put $b_{N}(k)=C(N,k)\,x^{k}y^{N-k}$, which defines a map $k\mapsto b_{N}(k)$ from $\{0,\dots,N\}$ to $R$ by Sets and Maps: Ordinary Notation §maps; the claim for $n$ is $(x+y)^{n}=\sum_{k=0}^{n}b_{n}(k)$.

Preliminary facts. Let $j,k,m,N\in\mathbb{N}_{0}$ and $z\in R$.

(B1) Order. $0\le k$ by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §zero-least; $\le$ is a total order on $\mathbb{N}_{0}$ by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §order, so antisymmetric and transitive by Partial and Total Orders on a Set and the Associated Strict Relation §partial; $k\le N$ implies $k+1\le N+1$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §order, and $N<N+1$ by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §successor, so $k\le N$ also implies $k\le N+1$. Further, $k\neq0$ if and only if $1\le k$: if $k\neq0$, then $k\in\mathbb{N}=\mathbb{N}_{0}\setminus\{0\}$ by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §sets, so $1\le k$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §one; and $1\le0$ is false, since with $0\le1$ it would give $1=0$ by antisymmetry, whereas $1\in\mathbb{N}$.

(B2) Differences. For $m\le N$, $N-m$ is the unique $i\in\mathbb{N}_{0}$ with $m+i=N$, by The Difference of Two Natural Numbers with Zero §difference. Checking $m+i=N$ for the proposed $i$ gives: $0-0=0$; $N-0=N$; and, for $k\le N$, $(N+1)-(k+1)=N-k$, as $(k+1)+(N-k)=(k+(N-k))+1=N+1$, and $(N+1)-k=(N-k)+1$, as $k+((N-k)+1)=(k+(N-k))+1=N+1$.

(B3) Powers. $z^{0}=1$ by Commutative Rings, Fields and Ordered Fields: Standard Notation §rings, and $z^{m}z=z^{m+1}$, since $z^{m+1}=z^{m}z^{1}$ by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §exponents and $z^{1}=z$ by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product.

(B4) Coefficients in $R$. $0_{R}=0$ and $1_{R}=1$ by The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products §constants, and $(m+j)_{R}=m_{R}+j_{R}$ by The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products §sum. By Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry §recursion, $C(N,0)=1$ and $C(N+1,k+1)=C(N,k)+C(N,k+1)$; by Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry §above, $C(N,N+1)=0$, as $N<N+1$. Hence, in $R$, $C(N,0)=1$, $C(N,N+1)=0$ and $C(N+1,k+1)=C(N,k)+C(N,k+1)$.

(B5) Splitting off the first term. For a map $a$ from a set containing $\{0,\dots,N\}$ to $R$,

$$\sum_{k=0}^{N}a_{k}=a_{0}+\sum_{k=1}^{N}a_{k}.$$

Indeed, by Intervals of Natural Numbers §interval and (B1), $\{0,\dots,N\}=\{0\}\cup\{1,\dots,N\}$: an element $k\le N$ is $0$ or satisfies $1\le k$, and conversely $0\le N$, and $1\le k$ implies $0\le k$; and $0\notin\{1,\dots,N\}$ as $1\le0$ is false, so the union is disjoint. These intervals are finite by 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 §naturals, and the sums are those of the restrictions of $a$ by Sums and Products over a Finite Set and over an Interval §intervals and Sums and Products over a Finite Set and over an Interval §subsets, a restriction of a restriction to a smaller set being the restriction to that set by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §restriction and Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §equality. So Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals §disjoint-union and Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals §singleton, for the operation $+$ of $R$, give the formula.

Induction. Let $K$ be the set of $n\in\mathbb{N}_{0}$ with $(x+y)^{n}=\sum_{k=0}^{n}b_{n}(k)$; we show $0\in K$ and $n+1\in K$ for $n\in K$, so that $K=\mathbb{N}_{0}$ by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §induction.

Base. By (B1), $\{0,\dots,0\}=\{0\}$: $0\le k\le0$ forces $k=0$ by antisymmetry. So, by Sums and Products over a Finite Set and over an Interval §intervals and Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals §singleton, and by (B2), (B3) and (B4),

$$\sum_{k=0}^{0}b_{0}(k)=b_{0}(0)=C(0,0)\,x^{0}y^{0-0}=1\cdot1\cdot y^{0}=1=(x+y)^{0}.$$

Step. Let $n\in K$ and $S=\sum_{k=0}^{n}b_{n}(k)$, so $(x+y)^{n}=S$. By (B3),

$$(x+y)^{n+1}=(x+y)^{n}(x+y)=xS+yS.$$

By 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 §distributive, applied over $\{0,\dots,n\}$ with the constants $x$ and $y$, and by (B3) and (B2),

$$xS=\sum_{k=0}^{n}\alpha_{k},\quad \alpha_{k}=C(n,k)\,x^{k+1}y^{n-k};\qquad yS=\sum_{k=0}^{n}c_{k},\quad c_{k}=C(n,k)\,x^{k}y^{(n+1)-k},$$

since $y\cdot y^{n-k}=y^{(n-k)+1}=y^{(n+1)-k}$; here $c_{k}$ is defined for all $k\in\{0,\dots,n+1\}$, and $k\mapsto c_{k}$ is a map from $\{0,\dots,n+1\}$ to $R$ by Sets and Maps: Ordinary Notation §maps.

The sum $yS$. By (B5), $yS=c_{0}+\sum_{k=1}^{n}c_{k}$, and $c_{0}=C(n,0)\,x^{0}y^{(n+1)-0}=y^{n+1}$ by (B4), (B3) and (B2). Let $U=\sum_{k=1}^{n+1}c_{k}$. By Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals §interval-recursion, applied with $m=1\le n+1$, and by (B4) and Rules of Arithmetic in a Commutative Ring: Zero, Signs and Squares, and No Zero Divisors in a Field §zero,

$$U=\sum_{k=1}^{n}c_{k}+c_{n+1}=\sum_{k=1}^{n}c_{k}+0\cdot x^{n+1}y^{(n+1)-(n+1)}=\sum_{k=1}^{n}c_{k}.$$

Hence $yS=y^{n+1}+U$. By Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals §interval-shift, applied with $m=0$, $n$ and $p=1$, as $0+1=1$,

$$U=\sum_{k=0}^{n}c_{k+1}=\sum_{k=0}^{n}\beta_{k},\qquad\beta_{k}=C(n,k+1)\,x^{k+1}y^{n-k},$$

since $(n+1)-(k+1)=n-k$ for $k\le n$ by (B2).

The sum for $n+1$. By (B5) with $N=n+1$, $\sum_{k=0}^{n+1}b_{n+1}(k)=b_{n+1}(0)+\sum_{k=1}^{n+1}b_{n+1}(k)$, and $b_{n+1}(0)=C(n+1,0)\,x^{0}y^{(n+1)-0}=y^{n+1}$ by (B4), (B3) and (B2). By Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals §interval-shift, applied with $m=0$, $n$ and $p=1$, $\sum_{k=1}^{n+1}b_{n+1}(k)=\sum_{k=0}^{n}b_{n+1}(k+1)$. For $k\le n$, by (B2) and (B4),

$$b_{n+1}(k+1)=C(n+1,k+1)\,x^{k+1}y^{(n+1)-(k+1)}=\big(C(n,k)+C(n,k+1)\big)x^{k+1}y^{n-k}=\alpha_{k}+\beta_{k}.$$

By Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals §termwise, for the operation $+$ of $R$ over $\{0,\dots,n\}$, $\sum_{k=0}^{n}(\alpha_{k}+\beta_{k})=\sum_{k=0}^{n}\alpha_{k}+\sum_{k=0}^{n}\beta_{k}=xS+U$. Therefore

$$\sum_{k=0}^{n+1}b_{n+1}(k)=y^{n+1}+(xS+U)=xS+(y^{n+1}+U)=xS+yS=(x+y)^{n+1},$$

so $n+1\in K$. This completes the induction and proves the clause binomial.