Binomial Coefficient Identities

How many ways can a committee of size kk be chosen from nn people? This single question is encoded by the Combinations symbol (nk)\binom{n}{k}. It turns out to satisfy a startling web of algebraic identities. These identities are provable in two entirely different registers. One way is by manipulating factorials. The other is by counting the same collection of objects in two ways. This second style, the combinatorial proof, is one of the great stylistic inventions of discrete mathematics. It replaces algebra with a story. Often it makes an otherwise mysterious identity feel inevitable. Binomial coefficients are the backbone of counting arguments. They also underpin probability (binomial distributions), algebra (the Binomial Theorem), and computer science. In computer science they appear in analysis of recursive algorithms, error-correcting codes, and probabilistic bounds. The identities collected here — Pascal's rule, the hockey stick identity, and Vandermonde's identity — are not isolated curiosities. They are the load-bearing beams that support Pascal's triangle. They also support binomial-coefficient recurrences used in dynamic programming. And they support the generating-function machinery that later unifies all of enumerative combinatorics. The big picture is this: (nk)\binom{n}{k} is simultaneously an algebraic quantity (n!k!(n−k)!\frac{n!}{k!(n-k)!}) and a counting quantity. As a counting quantity, it is the number of kk-subsets of an nn-set. Every identity about binomial coefficients can in principle be proved algebraically. But the deepest understanding — and often the shortest proof — comes from asking a question. That question is: "what is being counted, and can it be counted a second way?" This dual nature is exactly what makes the subject worth mastering. It should be mastered before moving to generating functions. There, these same identities reappear as coefficient extractions from (1+x)n(1+x)^n. This article develops the three central identities rigorously. It gives complete proofs in both the algebraic and combinatorial styles where illuminating. It works two nontrivial numerical examples. It also shows precisely which hypotheses cannot be dropped, such as integrality and ranges of indices.

Key takeaways
  • (nk)\binom{n}{k} counts kk-element subsets of an nn-element set; by convention (nk)=0\binom{n}{k}=0 when k<0k<0 or k>nk>n.
  • Pascal's rule: (nk)=(n−1k−1)+(n−1k)\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}, proved by conditioning on one distinguished element.
  • Hockey stick identity: ∑i=rn(ir)=(n+1r+1)\sum_{i=r}^{n}\binom{i}{r}=\binom{n+1}{r+1}, proved by repeated telescoping of Pascal's rule.
  • Vandermonde's identity: ∑k=0r(mk)(nr−k)=(m+nr)\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}, proved by splitting a set into two blocks.
  • Combinatorial proofs work by finding a set SS, computing ∣S∣|S| two different ways, and equating the answers.
  • Key idea: every binomial identity is secretly a counting problem told twice — once directly, once by clever bookkeeping.

Where this lives today

Binomial coefficient identities are not museum pieces; they are working tools across mathematics and its applications.

Probability and statistics. The binomial distribution's variance and moment computations rely on sums of the form ∑k(nk)pk(1−p)n−k\sum k\binom{n}{k}p^k(1-p)^{n-k}, which are simplified using Pascal-type recurrences; Vandermonde's identity underlies the hypergeometric distribution, which models sampling without replacement from a population split into two categories (exactly the two-block-splitting story used in the combinatorial proof above).

Computer science. Dynamic programming algorithms that compute (nk)\binom{n}{k} via Pascal's triangle run in O(n2)O(n^2) time using only additions, avoiding factorial overflow — a direct algorithmic use of Pascal's rule. Analysis of algorithms (e.g. counting root-to-leaf paths in certain trees, or the number of monotone lattice paths) uses the hockey stick identity to convert a sum of binomial coefficients into a single closed form, which is essential for exact complexity bounds.

Coding theory and cryptography. Vandermonde-type convolution identities appear in the analysis of Reed–Solomon and other algebraic codes, and binomial sums recur in bounds for the weight distribution of linear codes.

Algebraic combinatorics and beyond. These identities are the first rung of a ladder that leads to Combinations with Repetition (counting multisets, governed by the "stars and bars" variant of (n+k−1k)\binom{n+k-1}{k}) and then to Ordinary Generating Functions, where every identity proved here reappears instantly as a coefficient-matching statement about power series like (1+x)n(1+x)^n — the algebraic proof of Vandermonde's identity given above is in fact the prototype for that entire generating-function technique.

Ask the tutor: How do these binomial identities reappear as coefficient extractions once we introduce generating functions?

DefinitionBinomial Coefficient

Let nn be a nonnegative integer and kk an integer. The binomial coefficient (nk)\binom{n}{k}, read "nn choose kk," is defined by

(nk)={n!k! (n−k)!if 0≤k≤n,0if k<0 or k>n.\binom{n}{k} = \begin{cases} \dfrac{n!}{k!\,(n-k)!} & \text{if } 0 \le k \le n, \\[4pt] 0 & \text{if } k < 0 \text{ or } k > n. \end{cases}

Equivalently, for 0≤k≤n0\le k \le n, (nk)\binom{n}{k} is the number of kk-element subsets of a fixed nn-element set [n]={1,2,…,n}[n] = \{1,2,\dots,n\}. This combinatorial reading extends the algebraic definition consistently, since exactly n!k!(n−k)!\frac{n!}{k!(n-k)!} subsets of size kk exist (a standard consequence of the counting rule for Combinations).

Intuition

Picture Pascal's triangle: row nn lists (n0),(n1),…,(nn)\binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}. Each entry is the sum of the two entries diagonally above it — this is Pascal's rule, and it already suggests that binomial coefficients are governed by a recursive, additive structure rather than a purely multiplicative one. The hockey-stick identity says something visually striking: if you walk down a diagonal of the triangle and stop, the sum of everything you have walked over equals a single entry one step further down and one column to the right — the shape of the summed region literally looks like a hockey stick lying against the triangle. Vandermonde's identity has a different flavor: it says that choosing rr people from a group of mm men and nn women is the same as choosing kk men and r−kr-k women for every possible split kk, then adding up all the ways this split could happen. Algebra alone makes this look like a coincidence of factorials; combinatorics makes it look obvious.

Figure
Pascal's triangle showing the hockey-stick sum along a diagonal, rows n=0..6
Row n: 1 11 121 1331 14641 15101051 1615201561 Diagonal C(1,1)+C(2,1)+C(3,1)+C(4,1)+C(5,1) = 1+2+3+4+5 = 15 = C(6,2) Highlighted terms trace the "stick"; the circled 6 is the hockey-stick tip, C(6,1).

Central results

TheoremPascal's Rule

Let n≥1n \ge 1 and 1≤k≤n−11 \le k \le n-1 be integers. Then

(nk)=(n−1k−1)+(n−1k).\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.
Proof

Algebraic proof (technique: direct manipulation of factorials). By definition,

(n−1k−1)+(n−1k)=(n−1)!(k−1)! (n−k)!+(n−1)!k! (n−1−k)!.\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-1-k)!}.

Put both terms over the common denominator k! (n−k)!k!\,(n-k)!. For the first term multiply numerator and denominator by kk; for the second multiply by (n−k)(n-k):

=k (n−1)!k! (n−k)!+(n−k) (n−1)!k! (n−k)!=(n−1)!(k+(n−k))k! (n−k)!=n (n−1)!k! (n−k)!=n!k! (n−k)!=(nk).= \frac{k\,(n-1)!}{k!\,(n-k)!} + \frac{(n-k)\,(n-1)!}{k!\,(n-k)!} = \frac{(n-1)!\big(k + (n-k)\big)}{k!\,(n-k)!} = \frac{n\,(n-1)!}{k!\,(n-k)!} = \frac{n!}{k!\,(n-k)!} = \binom{n}{k}.

This chain of equalities is valid because 1≤k≤n−11\le k\le n-1 guarantees k−1≥0k-1\ge 0, n−1−k≥0n-1-k\ge 0, and k!,(n−k)!k!, (n-k)! are nonzero, so no division by zero or negative factorial occurs.

Combinatorial proof (technique: bijective/story counting, condition on a distinguished element). Let S={1,2,…,n}S = \{1,2,\dots,n\} and count (nk)\binom{n}{k}, the number of kk-subsets of SS, by conditioning on whether the element nn belongs to the subset.

  • Subsets of size kk that contain nn: choosing such a subset amounts to choosing the remaining k−1k-1 elements from S∖{n}S\setminus\{n\}, a set of size n−1n-1. There are (n−1k−1)\binom{n-1}{k-1} such subsets.
  • Subsets of size kk that do not contain nn: such a subset is a kk-subset of S∖{n}S\setminus\{n\}, a set of size n−1n-1. There are (n−1k)\binom{n-1}{k} such subsets.

Every kk-subset of SS falls into exactly one of these two cases (it either contains nn or it does not — these are mutually exclusive and jointly exhaustive), so by the addition principle the total count is

(nk)=(n−1k−1)+(n−1k).■\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. \qquad \blacksquare
∎
TheoremHockey Stick Identity

Let r≥0r \ge 0 and n≥rn \ge r be integers. Then

∑i=rn(ir)=(n+1r+1).\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}.
Proof

Proof by induction on nn (technique: telescoping via <span class="wiki-link-missing">Pascal&#39;s Rule</span>), for fixed r≥0r\ge 0. Base case n=rn = r: the left side is the single term (rr)=1\binom{r}{r} = 1, and the right side is (r+1r+1)=1\binom{r+1}{r+1} = 1. They agree. Inductive step: Suppose the identity holds for some n≥rn \ge r, i.e.

∑i=rn(ir)=(n+1r+1).\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}.

We show it holds for n+1n+1. Adding the next term to both sides,

∑i=rn+1(ir)=(∑i=rn(ir))+(n+1r)=(n+1r+1)+(n+1r),\sum_{i=r}^{n+1} \binom{i}{r} = \left(\sum_{i=r}^{n} \binom{i}{r}\right) + \binom{n+1}{r} = \binom{n+1}{r+1} + \binom{n+1}{r},

using the inductive hypothesis for the middle equality. Now apply Pascal's Rule with "nn" =n+2= n+2 and "kk" =r+1=r+1 (valid since 1≤r+1≤n+11 \le r+1 \le n+1, as r≥0r \ge 0 and n≥rn \ge r imply n+1≥r+1≥1n+1 \ge r+1 \ge 1):

(n+1r+1)+(n+1r)=(n+2r+1).\binom{n+1}{r+1} + \binom{n+1}{r} = \binom{n+2}{r+1}.

Hence ∑i=rn+1(ir)=((n+1)+1r+1)\sum_{i=r}^{n+1}\binom{i}{r} = \binom{(n+1)+1}{r+1}, which is exactly the claimed identity at n+1n+1. By the principle of mathematical induction, the identity holds for all integers n≥rn \ge r. ■\blacksquare

Combinatorial proof (technique: counting subsets by their maximum element). Fix r≥0r\ge0 and n≥rn \ge r. Count (n+1r+1)\binom{n+1}{r+1}, the number of (r+1)(r+1)-subsets of {1,2,…,n+1}\{1,2,\dots,n+1\}, by conditioning on the largest element mm of the subset. Since the subset has r+1r+1 elements chosen from {1,…,m}\{1,\dots,m\} with mm itself always included, the remaining rr elements are chosen from {1,…,m−1}\{1,\dots,m-1\}; a valid subset requires m−1≥rm-1 \ge r, i.e. m≥r+1m \ge r+1, and mm ranges from r+1r+1 up to n+1n+1. For a fixed value of mm, the number of such subsets is (m−1r)\binom{m-1}{r}. Since every (r+1)(r+1)-subset has a unique largest element, these cases are disjoint and exhaustive, so

(n+1r+1)=∑m=r+1n+1(m−1r).\binom{n+1}{r+1} = \sum_{m=r+1}^{n+1} \binom{m-1}{r}.

Re-indexing with i=m−1i = m-1 (so ii runs from rr to nn) gives

(n+1r+1)=∑i=rn(ir),\binom{n+1}{r+1} = \sum_{i=r}^{n} \binom{i}{r},

which is the claimed identity. ■\blacksquare

∎
TheoremVandermonde's Identity

Let m,nm, n be nonnegative integers and let rr be an integer with 0≤r≤m+n0 \le r \le m+n. Then

∑k=0r(mk)(nr−k)=(m+nr).\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}.

(Terms with k>mk > m or r−k>nr - k > n contribute 00 by the convention in the Binomial Coefficient definition, so the sum is well defined for all kk from 00 to rr.)

Proof

Combinatorial proof (technique: partition the ground set, split the choice). Let AA be a set with ∣A∣=m|A| = m and BB a disjoint set with ∣B∣=n|B| = n, so ∣A∪B∣=m+n|A \cup B| = m+n. The right-hand side (m+nr)\binom{m+n}{r} counts the number of rr-element subsets T⊆A∪BT \subseteq A \cup B. Partition the collection of all such TT according to k:=∣T∩A∣k := |T \cap A|, the number of elements TT takes from AA. Since TT has rr elements total and A,BA, B are disjoint, ∣T∩B∣=r−k|T \cap B| = r - k. The value kk can range over 0≤k≤r0 \le k \le r; note that if k>mk > m then no such TT exists (there are not enough elements in AA), consistent with (mk)=0\binom{m}{k} = 0 for k>mk > m, and similarly if r−k>nr - k > n then (nr−k)=0\binom{n}{r-k}=0. For fixed kk, the number of ways to choose TT with ∣T∩A∣=k|T\cap A| = k and ∣T∩B∣=r−k|T \cap B| = r-k is, by the product rule (choosing the AA-part and the BB-part independently), exactly

(mk)(nr−k).\binom{m}{k}\binom{n}{r-k}.

Since every rr-subset TT of A∪BA \cup B has a well-defined value of k=∣T∩A∣k = |T\cap A| between 00 and rr, and distinct values of kk give disjoint families of subsets, the addition principle yields

(m+nr)=∑k=0r(mk)(nr−k).■\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}. \qquad \blacksquare

Algebraic proof (technique: coefficient extraction from the <a class="wiki-link" href="/wiki/ndli-isc-11-mathematics-binomial-theorem" data-track="wiki_article.body.wiki_link">Binomial Theorem</a>). By the Binomial Theorem, for an indeterminate xx,

(1+x)m+n=(1+x)m(1+x)n=(∑i=0m(mi)xi)(∑j=0n(nj)xj).(1+x)^{m+n} = (1+x)^m (1+x)^n = \left(\sum_{i=0}^m \binom{m}{i} x^i\right)\left(\sum_{j=0}^n \binom{n}{j} x^j\right).

Expanding the product on the right and collecting the coefficient of xrx^r: a term xrx^r arises from every pair (i,j)(i,j) with i+j=ri+j = r, 0≤i≤m0\le i \le m, 0≤j≤n0 \le j \le n; writing i=ki = k and j=r−kj = r-k, the coefficient of xrx^r on the right is

∑k=0r(mk)(nr−k).\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}.

On the left, the Binomial Theorem applied directly to (1+x)m+n(1+x)^{m+n} gives the coefficient of xrx^r as (m+nr)\binom{m+n}{r}. Since (1+x)m+n(1+x)^{m+n} equals the product (1+x)m(1+x)n(1+x)^m(1+x)^n as formal polynomials, the coefficients of xrx^r on both sides must be equal, giving

(m+nr)=∑k=0r(mk)(nr−k).■\binom{m+n}{r} = \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}. \qquad \blacksquare
∎
CorollarySum of squares of binomial coefficients

For every nonnegative integer nn,

∑k=0n(nk)2=(2nn).\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}.

Justification. Apply Vandermonde's Identity with m=nm=n, r=nr=n, and use (nn−k)=(nk)\binom{n}{n-k} = \binom{n}{k} (a direct consequence of the definition, since n!(n−k)!k!=n!k!(n−k)!\frac{n!}{(n-k)!k!} = \frac{n!}{k!(n-k)!}):

(2nn)=∑k=0n(nk)(nn−k)=∑k=0n(nk)(nk)=∑k=0n(nk)2.■\binom{2n}{n} = \sum_{k=0}^{n}\binom{n}{k}\binom{n}{n-k} = \sum_{k=0}^n \binom{n}{k}\binom{n}{k} = \sum_{k=0}^n \binom{n}{k}^2. \qquad \blacksquare

Worked examples

Example 1 — Hockey stick with asymmetric parameters. Compute ∑i=39(i3)\displaystyle\sum_{i=3}^{9} \binom{i}{3} two ways and confirm the identity ∑i=rn(ir)=(n+1r+1)\sum_{i=r}^n \binom{i}{r} = \binom{n+1}{r+1} with r=3r=3, n=9n=9. Direct computation. List the terms:

(33)=1, (43)=4, (53)=10, (63)=20, (73)=35, (83)=56, (93)=84.\binom{3}{3}=1,\ \binom{4}{3}=4,\ \binom{5}{3}=10,\ \binom{6}{3}=20,\ \binom{7}{3}=35,\ \binom{8}{3}=56,\ \binom{9}{3}=84.

Sum: 1+4=51+4=5; 5+10=155+10=15; 15+20=3515+20=35; 35+35=7035+35=70; 70+56=12670+56=126; 126+84=210126+84=210. So ∑i=39(i3)=210\sum_{i=3}^9 \binom{i}{3} = 210. Via the identity. The theorem predicts (n+1r+1)=(104)\binom{n+1}{r+1} = \binom{10}{4}. Compute

(104)=10!4! 6!=10⋅9⋅8⋅74⋅3⋅2⋅1=504024=210.\binom{10}{4} = \frac{10!}{4!\,6!} = \frac{10\cdot 9\cdot 8\cdot 7}{4\cdot3\cdot2\cdot1} = \frac{5040}{24} = 210.

The two computations agree: 210=210210 = 210, confirming the identity in a case where r≠0r\ne 0 and the range is nontrivial (seven terms, not a small symmetric handful).

Example 2 — Vandermonde with unequal, non-symmetric parameters. A university club has m=5m = 5 distinguishable seniors and n=8n = 8 distinguishable juniors. A trip committee of r=4r = 4 students is to be chosen from the combined pool of 13 students. Verify Vandermonde's identity by computing both sides. Right-hand side.

(m+nr)=(134)=13⋅12⋅11⋅104⋅3⋅2⋅1=1716024=715.\binom{m+n}{r} = \binom{13}{4} = \frac{13\cdot12\cdot11\cdot10}{4\cdot3\cdot2\cdot1} = \frac{17160}{24} = 715.

Left-hand side. Split by kk = number of seniors on the committee, k=0,…,4k=0,\dots,4 (note kk cannot exceed m=5m=5, and r−kr-k cannot exceed n=8n=8, so all five terms are nonzero in principle — check each):

  • k=0k=0: (50)(84)=1⋅70=70\binom{5}{0}\binom{8}{4} = 1 \cdot 70 = 70.
  • k=1k=1: (51)(83)=5⋅56=280\binom{5}{1}\binom{8}{3} = 5 \cdot 56 = 280.
  • k=2k=2: (52)(82)=10⋅28=280\binom{5}{2}\binom{8}{2} = 10 \cdot 28 = 280.
  • k=3k=3: (53)(81)=10⋅8=80\binom{5}{3}\binom{8}{1} = 10 \cdot 8 = 80.
  • k=4k=4: (54)(80)=5⋅1=5\binom{5}{4}\binom{8}{0} = 5 \cdot 1 = 5.

Sum: 70+280=35070 + 280 = 350; 350+280=630350+280 = 630; 630+80=710630+80=710; 710+5=715710+5=715. Both sides equal 715715, confirming Vandermonde's identity for genuinely asymmetric m=5≠n=8m=5 \ne n=8, with r=4r=4 strictly between 00 and min⁡(m,n)\min(m,n), and with no term forced to vanish artificially.

CounterexampleWhy the range restriction on indices matters

Pascal's rule as stated requires 1≤k≤n−11 \le k \le n-1. Suppose we carelessly try to apply the algebraic derivation of Pascal's rule at k=0k = 0 using the naive (unconventional) factorial formula (n−1k−1)=(n−1−1)=(n−1)!(−1)! n!\binom{n-1}{k-1} = \binom{n-1}{-1} = \frac{(n-1)!}{(-1)!\,n!}, treating (−1)!(-1)! as if it were an ordinary factorial rather than invoking the combinatorial convention (n−1−1):=0\binom{n-1}{-1} := 0. Take n=5n = 5, k=0k=0. The correct value, using the stated convention, is (4−1)=0\binom{4}{-1} = 0, so Pascal's rule gives

(50)=(4−1)+(40)=0+1=1,\binom{5}{0} = \binom{4}{-1} + \binom{4}{0} = 0 + 1 = 1,

which is correct since (50)=1\binom{5}{0}=1. This works only because the convention (nk)=0\binom{n}{k}=0 for k<0k<0 was built into the definition from the start and applied consistently. If instead one drops that convention and tries to make sense of (−1)!(-1)! literally (say by naively extending the recursion n!=n⋅(n−1)!n! = n\cdot(n-1)! backward, which forces 0!=0⋅(−1)!0! = 0 \cdot (-1)!, an equation with no consistent finite solution for (−1)!(-1)!), the formula (n−1)!(−1)! n!\frac{(n-1)!}{(-1)!\,n!} is simply undefined — division by an undefined or infinite quantity. Without the boundary convention (nk)=0\binom{n}{k}=0 outside 0≤k≤n0\le k\le n, the formula for Pascal's rule breaks down exactly at the edges k=0k=0 and k=nk=n, even though the combinatorial statement (there are no subsets of size −1-1) remains perfectly sensible. This shows the range hypothesis 1≤k≤n−11\le k \le n-1 in the algebraic proof is not a cosmetic restriction: it is exactly what keeps every factorial in sight well-defined, and the convention-based extension to k=0,nk=0,n is a separate, additional fact that must be checked (as done above), not something the algebraic proof automatically hands you.

Scope, edge cases & common traps

SituationWhat happensCorrect handling
k<0k<0 or k>nk>n in (nk)\binom{n}{k}Undefined by raw factorial formulaUse convention (nk)=0\binom{n}{k}=0
Pascal's rule at k=0k=0 or k=nk=nStill true, but not via the factorial algebra directlyVerify separately: (n0)=(n−1−1)+(n−10)=0+1=1\binom{n}{0}=\binom{n-1}{-1}+\binom{n-1}{0}=0+1=1 ✓, and symmetric case at k=nk=n
Vandermonde sum boundsTerms with k>mk>m or r−k>nr-k>n vanish automaticallySafe to write sum from k=0k=0 to rr without extra case-checking, thanks to the convention
Hockey stick with r=0r=0Reduces to ∑i=0n(i0)=n+1=(n+11)\sum_{i=0}^n \binom{i}{0} = n+1 = \binom{n+1}{1}Sanity check: every term is 11
Confusing "combinatorial proof" with "just checking small cases"A few numerical checks is NOT a proofA combinatorial proof needs an explicit set SS, a bijection or partition, and a justification that both sides count ∣S∣|S|

The mathematician behind it

Origins · 1 minBlaise Pascal and how this was discovered
BP
Blaise Pascal
1623–1662 · 17th-century France, mathematics and natural philosophy

Pascal was a French mathematician, physicist, and philosopher whose 1654 correspondence with Pierre de Fermat on games of chance is often cited as a founding moment of probability theory. His Traité du triangle arithmétique (written 1654, published 1665) systematically studied the triangular array of binomial coefficients, proved the additive recurrence now called Pascal's rule, and used the triangle to solve problems in combinatorics, probability, and the emerging binomial theorem, though the triangle itself had been known earlier in Chinese (Jia Xian, Yang Hui) and Persian/Islamic mathematics (al-Karaji, Omar Khayyam).

History
- 1050 (approx.): Chinese mathematician Jia Xian describes a triangular arrangement of binomial coefficients for extracting roots.
- 1303: Yang Hui records and popularizes the triangle in China, crediting Jia Xian's earlier work.
- 1665: Pascal's treatise on the arithmetical triangle is published posthumously, systematizing the additive rule and its applications to probability.
- 1772: Alexandre-Théophile Vandermonde publishes work on combinatorial identities, including the identity that now bears his name (though special cases were known to Chinese mathematician Zhu Shijie by 1303).
- 19th–20th century: Binomial identities become foundational tools in the generating-function and algebraic-combinatorics traditions developed by Cauchy, Cayley, and later systematized by Riordan and Stanley.
Is Pascal's rule the same as the definition of Pascal's triangle?

Not quite — they are closely related but logically distinct. Pascal's triangle is simply the visual arrangement of all values (nk)\binom{n}{k} by row nn and column kk. Pascal's rule is the theorem that each interior entry equals the sum of the two entries above it, i.e. (nk)=(n−1k−1)+(n−1k)\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}. One could in principle define the triangle by writing down every value (nk)\binom{n}{k} directly from the factorial formula, without ever invoking the additive rule; Pascal's rule is the extra fact that makes the triangle constructible by simple addition, without computing any factorials at all, which is why it is the standard method for building the triangle by hand or by algorithm.

Why does the hockey stick identity require summing along a fixed lower index rr?

The identity ∑i=rn(ir)=(n+1r+1)\sum_{i=r}^n \binom{i}{r} = \binom{n+1}{r+1} fixes rr and lets the upper index ii vary; this corresponds to walking straight down a fixed diagonal of Pascal's triangle (the diagonal of "rr-th column" entries). If instead you fixed the upper index and varied the lower index, you would just get the trivial full-row sum ∑k=0n(nk)=2n\sum_{k=0}^n \binom{n}{k} = 2^n, an entirely different (and also true, but unrelated) identity from the Binomial Theorem at x=1x=1. The specific "hockey stick" shape comes precisely from fixing rr and summing over consecutive values of the upper parameter, which is what the inductive/telescoping proof and the "largest element" combinatorial proof both exploit.

Can Vandermonde's identity be generalized to more than two blocks?

Yes. If a set is partitioned into blocks of sizes n1,n2,…,ntn_1, n_2, \dots, n_t with total size n=n1+⋯+ntn=n_1+\cdots+n_t, then choosing an rr-subset can be split according to how many elements come from each block, giving the multi-block Vandermonde convolution

(nr)=∑k1+⋯+kt=r(n1k1)(n2k2)⋯(ntkt).\binom{n}{r} = \sum_{k_1+\cdots+k_t = r} \binom{n_1}{k_1}\binom{n_2}{k_2}\cdots\binom{n_t}{k_t}.

This follows by repeatedly applying the two-block identity proved here, treating the union of the first t−1t-1 blocks as a single set of size n1+⋯+nt−1n_1+\cdots+n_{t-1} and inducting on tt. The two-block case proved in this article is therefore the base case of a much larger family of convolution identities used heavily once generating functions are introduced.

Does Pascal's rule hold for negative nn or for real-valued generalized binomial coefficients?

The rule extends beyond nonnegative integers if one uses the generalized binomial coefficient (xk)=x(x−1)⋯(x−k+1)k!\binom{x}{k} = \frac{x(x-1)\cdots(x-k+1)}{k!} for real (or complex) xx and nonnegative integer kk. The identity (xk)=(x−1k−1)+(x−1k)\binom{x}{k} = \binom{x-1}{k-1}+\binom{x-1}{k} can be verified directly from this polynomial-in-xx formula by the same algebraic manipulation used in this article's proof, since the combinatorial (subset-counting) proof no longer applies when xx is not a nonnegative integer. This generalized version underlies the extended Binomial Theorem for arbitrary real exponents, encountered later when generating functions handle expressions like (1+x)−1(1+x)^{-1} or (1+x)1/2(1+x)^{1/2}.

Why do combinatorial proofs matter if the algebraic proofs already work?

Algebraic proofs confirm an identity is true but often obscure why it is true, and they can be fragile — small changes to the identity may require entirely new algebraic manipulation. Combinatorial proofs, by contrast, reveal a structural reason the two sides must agree (they count the same finite set), and this structural insight frequently generalizes immediately to related identities, new special cases, or bijective arguments in adjacent problems, which is why they are prized in enumerative combinatorics as the more explanatory and often more transferable style of proof.

What is the most common computational mistake when applying these identities?

The most frequent error is mismatching indices: writing ∑i=rn(ir)=(nr+1)\sum_{i=r}^{n}\binom{i}{r}=\binom{n}{r+1} (off by one in the upper argument) instead of the correct (n+1r+1)\binom{n+1}{r+1}, or applying Vandermonde's identity with a sum that does not actually run from k=0k=0 to rr. Careful bookkeeping — checking the base case by hand, as done in the worked examples above — is the most reliable safeguard, since a single miscounted index silently produces a self-consistent-looking but wrong formula.

Is there a "hockey stick" identity going in the other summation direction, e.g. fixing the upper index and varying rr?

Summing (nr)\binom{n}{r} over rr from 00 to nn just gives 2n2^n by the Binomial Theorem at x=1x=1, which is a different (and simpler) fact, not a variant of the hockey stick identity. There is, however, a genuine "dual" reading of the hockey stick identity via the symmetry (ir)=(ii−r)\binom{i}{r}=\binom{i}{i-r}, which restates the same sum along an anti-diagonal of the triangle rather than a diagonal; the underlying content and proof technique remain identical, since the symmetry identity is a trivial relabeling built into the factorial formula.

Before this

Where this leads