Proof of Binomial Identities

Throughout, $\binom{n}{k}=C(n,k)$ for the map $C$ of Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (i) (The Binomial Coefficient (i)), so that in $\mathbb{N}_{0}$

$$\binom{n}{0}=1,\qquad\binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1}\quad\text{(Pascal's rule)},$$

and $\binom{n}{k}=0$ for $k>n$ (Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (ii)); in particular $\binom{0}{k+1}=0$, as $0<k+1$ (The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor (iv)). Sums and products in $\mathbb{N}_{0}$ are rearranged by associativity and commutativity, with $0$ and $1$ as neutral elements, $0$ as an absorbing factor, and distributivity (Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (iii), Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (iv), Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (i), Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (ii), Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (v), Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (vi), Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (iii), Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (i), Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (iv)). The addition of $\mathbb{N}_{0}$ is associative and commutative with neutral element $0$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (vi)), so the rules of Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals apply to sums in $\mathbb{N}_{0}$; the last term of an interval sum is split off by Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (vii), and a sum over $\{0,\dots,0\}=\{0\}$ is its single term (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (i)). Natural numbers read in $\mathbb{R}$ keep $0$, $1$, sums, powers and finite sums, and distinct natural numbers stay distinct (The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (i), The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (ii), The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (v), The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (vi), Reading Natural Numbers in ℝ: Injectivity, Order and Pascal's Rule (i)).

Step 0: two rules for sums in $\mathbb{N}_{0}$. Let $p\in\mathbb{N}_{0}$.

(a) Splitting off the first term. For a map $a:\{0,\dots,p+1\}\to\mathbb{N}_{0}$,

$$\sum_{j=0}^{p+1}a_{j}=a_{0}+\sum_{j=0}^{p}a_{j+1}.$$

Indeed, $\{0,\dots,p+1\}$ is the disjoint union of $\{0\}$ and $\{1,\dots,p+1\}$, so the sum is $a_{0}+\sum_{j=1}^{p+1}a_{j}$ (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (ii), Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (i)), and $\sum_{j=1}^{p+1}a_{j}=\sum_{j=0}^{p}a_{j+1}$ by the index shift Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (viii).

(b) Sums against the row $n=0$. For every map $a:\{0,\dots,p\}\to\mathbb{N}_{0}$,

$$\sum_{j=0}^{p}\binom{0}{j}a_{j}=a_{0}.$$

We use induction on $p$. For $p=0$ the sum is $\binom{0}{0}a_{0}=a_{0}$. If the rule holds for $p$, then for $a:\{0,\dots,p+1\}\to\mathbb{N}_{0}$, splitting off the last term,

$$\sum_{j=0}^{p+1}\binom{0}{j}a_{j}=\sum_{j=0}^{p}\binom{0}{j}a_{j}+\binom{0}{p+1}a_{p+1}=a_{0}+0\cdot a_{p+1}=a_{0}.$$

Step 1: the row sum ((i)). We compute in $\mathbb{R}$. Since $2=1+1$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (vii)), the binomial theorem (The Binomial Theorem in a Commutative Ring (i)) with $x=y=1$, together with $1^{i}=1$ (Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality (ii)), gives

$$2^{n}=(1+1)^{n}=\sum_{j=0}^{n}\binom{n}{j}\,1^{j}\,1^{n-j}=\sum_{j=0}^{n}\binom{n}{j}.$$

Both sides are natural numbers, so the identity holds in $\mathbb{N}_{0}$ as well.

Step 2: the alternating row sum ((ii)). In $\mathbb{R}$, the binomial theorem with $x=-1$, $y=1$ and exponent $n+1$ gives

$$\sum_{j=0}^{n+1}(-1)^{j}\binom{n+1}{j}=\sum_{j=0}^{n+1}\binom{n+1}{j}(-1)^{j}\,1^{(n+1)-j}=(-1+1)^{n+1}=0^{n+1}=0,$$

using $1^{i}=1$ and $0^{i}=0$ for $i\ge1$ in $\mathbb{R}$ (Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality (ii)), with $n+1\ge1$.

Step 3: absorption ((iii)). This step uses only the factorial formula. If $k>n$, then $k+1>n+1$ (Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (vi)), so $\binom{n}{k}=0=\binom{n+1}{k+1}$ and both sides are $0$ (Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (i)).

Let $k\le n$; then $k+1\le n+1$ (Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (vi)), and $(n+1)-(k+1)=n-k$, since $(k+1)+(n-k)=(k+(n-k))+1=n+1$ (The Difference of Two Natural Numbers with Zero (i)). The factorial formula (Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (v)) for $(n,k)$ and for $(n+1,k+1)$, with $(k+1)!=(k+1)\,k!$ and $(n+1)!=(n+1)\,n!$ (The Factorial: Recursion, Positivity and Bounds by Powers (i)), gives

$$k!\,(n-k)!\cdot(k+1)\binom{n+1}{k+1}=(k+1)!\,\big((n+1)-(k+1)\big)!\binom{n+1}{k+1}=(n+1)!,$$ $$k!\,(n-k)!\cdot(n+1)\binom{n}{k}=(n+1)\cdot n!=(n+1)!.$$

Cancelling the nonzero factor $k!\,(n-k)!$ (The Factorial: Recursion, Positivity and Bounds by Powers (ii), Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (vii), Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (ix)) gives $(k+1)\binom{n+1}{k+1}=(n+1)\binom{n}{k}$.

Step 4: Vandermonde's identity ((iv)). Fix $n$. We prove by induction on $m$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (viii)) that the identity holds for every $k\in\mathbb{N}_{0}$. Recall that $k-0=k$, since $0+k=k$, and that for $j\le k$

$$(k+1)-(j+1)=k-j,$$

since $(j+1)+(k-j)=(j+(k-j))+1=k+1$ (The Difference of Two Natural Numbers with Zero (i)).

Base $m=0$. By rule (b) of Step 0, with $a_{j}=\binom{n}{k-j}$,

$$\sum_{j=0}^{k}\binom{0}{j}\binom{n}{k-j}=\binom{n}{k-0}=\binom{0+n}{k}.$$

Induction step. Assume the identity for $m$ and every $k$. For $k=0$ both sides for $m+1$ are $1$: the sum is $\binom{m+1}{0}\binom{n}{0}=1=\binom{m+1+n}{0}$. For $k+1$, split off the first term by rule (a), apply Pascal's rule to $\binom{m+1}{j+1}$, and distribute (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (v)); then put the first term back by rule (a), now for $m$, using $\binom{m+1}{0}=1=\binom{m}{0}$:

$$\begin{aligned} \sum_{j=0}^{k+1}\binom{m+1}{j}\binom{n}{(k+1)-j} &=\binom{n}{k+1}+\sum_{j=0}^{k}\binom{m+1}{j+1}\binom{n}{k-j}\\ &=\Big(\binom{n}{k+1}+\sum_{j=0}^{k}\binom{m}{j+1}\binom{n}{k-j}\Big)+\sum_{j=0}^{k}\binom{m}{j}\binom{n}{k-j}\\ &=\sum_{j=0}^{k+1}\binom{m}{j}\binom{n}{(k+1)-j}+\sum_{j=0}^{k}\binom{m}{j}\binom{n}{k-j}. \end{aligned}$$

By the induction hypothesis, for $k+1$ and for $k$, and Pascal's rule, this is

$$\binom{m+n}{k+1}+\binom{m+n}{k}=\binom{m+n+1}{k+1}=\binom{(m+1)+n}{k+1}.$$

Step 5: the hockey-stick identity ((v)). Fix $k$; we use induction on $n$. For $n=0$, the sum is $\binom{0}{k}$, and Pascal's rule gives $\binom{1}{k+1}=\binom{0}{k}+\binom{0}{k+1}=\binom{0}{k}+0=\binom{0}{k}$. If the identity holds for $n$, then splitting off the last term,

$$\sum_{i=0}^{n+1}\binom{i}{k}=\sum_{i=0}^{n}\binom{i}{k}+\binom{n+1}{k}=\binom{n+1}{k+1}+\binom{n+1}{k}=\binom{n+2}{k+1}.$$

Step 6: the shifted hockey-stick identity ((vi)). Fix $k$; we use induction on $n$. For $n=0$, the sum is $\binom{k}{k}=1=\binom{k+1}{k+1}$ (Binomial Coefficients: Existence and Uniqueness by Pascal's Recursion, Vanishing above the Diagonal, Diagonal and First Values, the Factorial Formula and Symmetry (iii)). If the identity holds for $n$, then splitting off the last term and applying Pascal's rule with upper index $n+k+1$,

$$\sum_{s=0}^{n+1}\binom{s+k}{k}=\binom{n+k+1}{k+1}+\binom{n+k+1}{k}=\binom{n+k+2}{k+1}=\binom{(n+1)+k+1}{k+1}.$$

Step 7: the weighted row sum ((vii)). The first term is $0\cdot\binom{n+1}{0}=0$ (Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (i)). Splitting it off by rule (a), where $0+x=x$ (Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (i)), and applying (iii) to each remaining term, $(j+1)\binom{n+1}{j+1}=(n+1)\binom{n}{j}$,

$$\sum_{j=0}^{n+1}j\binom{n+1}{j}=\sum_{j=0}^{n}(j+1)\binom{n+1}{j+1}=\sum_{j=0}^{n}(n+1)\binom{n}{j}=(n+1)\sum_{j=0}^{n}\binom{n}{j}=(n+1)\,2^{n}.$$

The constant factor comes out of the sum because $x\mapsto(n+1)\,x$ maps $0$ to $0$ and sums to sums (Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (i), Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (iv)), so it commutes with finite sums (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (vi)); the last step is (i).