1
Pascal's rule is a case split
Count the k-subsets of an n-set by whether they contain a fixed element. Those that do, and those that do not, are exactly the two terms.
Lesson · Combinatorics and Counting · Binomial coefficients
Binomial Coefficients and Pascal's Triangle
Pascal's rule builds each entry from the two above it, and the resulting triangle displays symmetry, the row sums, the hockey stick and several other identities — each with a counting proof.
Pascal's rule C(n,k) = C(n−1,k−1) + C(n−1,k)
symmetry C(n,k) = C(n,n−k)
row sum Σ_k C(n,k) = 2ⁿ
hockey stick Σ_{i=k}^{n} C(i,k) = C(n+1,k+1)
Four identities, all provable by counting
Core ideas
What this lesson establishes
Every identity in this lesson has a counting proof that is shorter and more illuminating than the algebra.
2
Row sums are the power set
Summing across a row counts every subset once, which Sets, Relations, and Functions already showed is 2ⁿ.
3
The triangle is a computation, not a picture
Pascal's rule gives every entry from the previous row using only addition, which is how the values are produced without factorials.
The material
The triangle and its identities
Pascal's rule first, then the identities it generates.
Theorem · Pascal's rule
For 1 ≤ k ≤ n−1, C(n,k) = C(n−1,k−1) + C(n−1,k).
Fix an element x of an n-set and count the k-subsets by whether they contain x.
Those containing x are determined by the other k−1 elements, chosen from the remaining n−1: C(n−1, k−1) of them.
Those not containing x are k-subsets of the other n−1 elements: C(n−1, k) of them.
The two classes are disjoint and cover everything, so the sum rule gives the identity.
□
That is a two-line proof of a fact whose algebraic verification requires combining fractions with factorials. The pattern — split on whether a fixed element is included — recurs throughout the course.
n=0 1
n=1 1 1
n=2 1 2 1
n=3 1 3 3 1
n=4 1 4 6 4 1
n=5 1 5 10 10 5 1
n=6 1 6 15 20 15 6 1
Theorem · Row sum
Σ_{k=0}^{n} C(n,k) = 2ⁿ: every row of the triangle sums to a power of two.
Theorem · Alternating row sum
For n ≥ 1, Σ_{k=0}^{n} (−1)^k C(n,k) = 0: a set with at least one element has exactly as many even-sized subsets as odd-sized ones.
Fix an element x. Pairing each subset containing x with the same subset minus x matches every subset with one of the opposite parity, and this pairing is a bijection. So the two counts are equal.
For n = 0 the identity fails: the empty set has one subset, of even size, and there is no x to pair with.
□
Theorem · Hockey stick
Σ_{i=k}^{n} C(i,k) = C(n+1, k+1).
Count the (k+1)-subsets of {1, …, n+1} by their largest element. If the largest is i+1, the remaining k elements come from {1, …, i}, giving C(i, k) such subsets. Summing over i from k to n counts every (k+1)-subset exactly once.
□
Classifying by the largest element is the other reusable device in this lesson. It turns a sum into a single count and is the standard way to prove identities whose left side is a sum.
Theorem · Vandermonde's identity
C(m+n, r) = Σ_{k=0}^{r} C(m, k) C(n, r−k).
Split m + n objects into a group of m and a group of n. An r-subset takes k from the first group and r−k from the second, for some k. Summing over k counts every r-subset exactly once.
□
Interactive
Pascal's triangle
Identities highlighted and checked
Method
Proving a binomial identity by counting
Find a set both sides count.
1
Decide what the right-hand side counts
C(n+1, k+1) counts (k+1)-subsets of an (n+1)-set. Naming the objects is the first move.
2
Find a classification giving the left-hand side
By whether a fixed element is in; by the largest element; by how many come from each of two groups.
3
Check the classes are disjoint and exhaustive
Every object in exactly one class. This is where a counting proof goes wrong if it goes wrong.
4
State the conclusion
One set, two counts, therefore two equal expressions. That sentence is the proof's ending.
Binomial coefficients
Score 0 / 0Choose the answer you can justify.
Prove Σ_k k·C(n,k) = n·2ⁿ⁻¹
Count committees with a designated chair, two ways.
Objects: pairs (committee, chair) where the chair is a committee member,
from a pool of n people. Committees may be any size ≥ 1.
COUNT 1 — choose the committee first:
a committee of size k can be chosen C(n,k) ways,
and its chair k ways. Total Σ_k k·C(n,k).
COUNT 2 — choose the chair first:
n ways to pick the chair, then each of the other n−1 people
independently in or out: 2ⁿ⁻¹. Total n·2ⁿ⁻¹.
Same set, two counts ⟹ Σ_k k·C(n,k) = n·2ⁿ⁻¹. ∎
The algebraic proof of this identity requires differentiating the binomial theorem. The counting proof is four lines and explains the answer: the factor n is the chair and the 2ⁿ⁻¹ is everyone else's independent decision.
Common mistakes
1
Proving identities algebraically by defaultThe counting proof is usually shorter and always more informative. Algebra confirms; counting explains.
2
Applying Pascal's rule at the edgesC(n,0) and C(n,n) have only one parent, and the rule as stated needs 1 ≤ k ≤ n−1. The edge entries are 1 by definition.
3
Forgetting the n = 0 exception in the alternating sumThe bijection needs an element to add or remove. With none, the sum is 1.
Check your understanding
✓
Finish when you can prove an identity by counting one set twice.
Prove C(2n, 2) = 2·C(n, 2) + n² by counting the pairs drawn from 2n objects split into two halves of n: classify a pair by how many of its members come from the first half. Say why the three classes are disjoint and exhaustive, and check the identity at n = 3, where the left side is 15.
Note: Pascal's triangle mod 2 reproduces the Sierpiński triangle, because C(n,k) is odd exactly when the binary digits of k are a subset of those of n — Lucas's theorem, read modulo 2. Number Theory and Cryptography's modular arithmetic is what makes that statement precise.