\binom{n}{k} is the single most reused quantity in combinatorics — it's about to appear inside stars-and-bars, the binomial theorem, and every identity Chapter 3 proves. A quick refresher on where its entries come from and what its recurrence means earns its keep immediately.
Read any entry of Pascal's triangle as "how many ways." That makes the recurrence obvious with no algebra needed. To choose a committee of k from n people, pick one person to think about first. Either that person joins the committee, or doesn't. Both cases are easy counts of the remaining n-1 people. They never overlap, so the counts add.
A binomial coefficient \binom{n}{k} counts the number of k-element subsets of an n-element set — the same quantity C(n,k) from Section 2, written in the notation this course uses from here on. Pascal's identity, \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}, comes from a single case split: fix one specific item, and every k-subset either contains it or doesn't. The subsets containing it are in bijection with (k-1)-subsets of the remaining n-1 items; the subsets excluding it are exactly the k-subsets of those same n-1 items. Every entry of Pascal's triangle is built from the two entries above it for exactly this reason, and every row sums to 2^n — the total number of subsets of an n-element set, split by size.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
What is the sum of all entries in row 5 of Pascal's triangle?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Row 5 sums to 2^5 = 32.
Correct answer
Also accepted:
Why
From Discrete Mathematics I — Logic, Proof, and Structure
Pascal's identity C(n,k) = C(n-1,k-1) + C(n-1,k) is proved combinatorially by...
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
This CAN be shown with algebra, but the combinatorial proof splits subsets into two exhaustive, non-overlapping cases instead.
Why
Every size-k subset either contains the fixed element or does not -- exactly the two disjoint cases the identity's two terms count.
Theorem
Pascal's Identity
also known as: the recurrence for binomial coefficients
Recalled from Discrete Mathematics I — Logic, Proof, and Structure · Binomial coefficients and Pascal's triangle — first taught there.
For integers n \geq 1 and 0 \leq k \leq n, \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.
Count the size-k subsets of an n-element set \{1, 2, \ldots, n\} two ways. The left side, \binom{n}{k}, counts them directly. For the right side, split every size-k subset by whether it contains the element n or not — an exhaustive, non-overlapping split. A subset containing n is n together with a size-(k-1) subset of the remaining n-1 elements: \binom{n-1}{k-1} such subsets. A subset not containing n is a size-k subset chosen entirely from those same n-1 elements: \binom{n-1}{k} of those. Every size-k subset falls into exactly one of the two cases, so the two counts add to the original total.
Build any entry from its two parents
Click any entry below row 3 and confirm it equals the sum of the two entries directly above it.
Loading interactive…
Every row sums to a power of 2
Click along row 5 and watch which cells light up, then compare the row sum to 2 raised to the row number.
Loading interactive…
Worked example
Building a triangle entry from its parents
-
1
Without a factorial in sight, find \binom{5}{2} using only the two entries directly above it in Pascal's triangle.
-
2
Row 4 already gives \binom{4}{1}=4 and \binom{4}{2}=6 — the two parents of \binom{5}{2}.
-
3
Apply Pascal's identity: \binom{5}{2} = \binom{4}{1} + \binom{4}{2}.
-
4\boxed{\binom{5}{2} = 4 + 6 = 10}
Loading interactive…
Where this goes next
Polynomial algebra
Every coefficient in an expanded power (a+b)^n is a row of Pascal's triangle read off directly — the binomial theorem this course extends in Chapter 3. A symbolic algebra system expanding (x+2)^{10} by hand would multiply ten binomials together; instead it looks up row 10 of Pascal's triangle once and writes the ten terms straight from those coefficients, turning an expansion into a table lookup.
Check your understanding (counts toward your progress)
A row of Pascal's triangle is claimed to sum to 100. Is that possible?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Row n always sums to 2^n (1, 2, 4, 8, 16, 32, 64, 128, ...) -- 100 is never on that list.
Recall the general formula for what an entire row of Pascal's triangle sums to, in terms of n.
List out several powers of 2 and check whether 100 ever appears among them.
Compute C(8,5) using the symmetry identity, given that C(8,3) = 56.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
C(8,5) = C(8, 8-5) = C(8,3) = 56.
Correct answer
Also accepted:
Why
Apply the symmetry identity C(n,k) = C(n,n-k) to rewrite C(8,5) with a smaller second number.
Using Pascal's identity, if C(6,2) = 15 and C(6,3) = 20, what is C(7,3)?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Pascal's identity: C(7,3) = C(6,2) + C(6,3) = 15 + 20 = 35.
Correct answer
Also accepted:
Why
What does row 5 of Pascal's triangle sum to?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Every row n sums to 2^n; row 5 sums to 2^5 = 32.
Correct answer
Also accepted:
Why
Practice: Pascal's triangle identities, from formula to reasoning (5 problems · doesn’t affect your progress)
What does the entry in row n, position k of Pascal's triangle represent?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
That's a permutation count, P(n,k) -- Pascal's triangle entries are unordered subset counts.
Pascal's triangle entries aren't a plain division -- they're subset counts governed by the combination formula.
That's only half the picture -- Pascal's identity splits C(n,k) into subsets that include OR exclude a fixed element, not just the excluding half alone.
Why
Each entry C(n,k) counts unordered k-element subsets of an n-element set -- the same combination count from Section 2, in Pascal's-triangle notation.
The number of k-element subsets of an n-element set, C(n,k)
Using Pascal's identity, if C(6,2) = 15 and C(6,3) = 20, what is C(7,3)?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Pascal's identity: C(7,3) = C(6,2) + C(6,3) = 15 + 20 = 35.
Correct answer
Also accepted:
Why
What does row 5 of Pascal's triangle sum to?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Every row n sums to 2^n; row 5 sums to 2^5 = 32.
Correct answer
Also accepted:
Why
Given C(9,4) = 126 and C(9,5) = 126, use Pascal's identity to find C(10,5).
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
C(10,5) = C(9,4) + C(9,5) = 126 + 126 = 252.
Correct answer
Also accepted:
Why
Apply Pascal's identity C(n,k) = C(n-1,k-1) + C(n-1,k) with n=10, k=5.
Which pair is guaranteed equal by the symmetry identity, given C(11,4) = 330?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
n-k = 11-4 = 7, not 8 -- check the subtraction before applying the identity.
C(n,k) = C(n,n-k) pairs k with n-k specifically, not with k+1.
C(4,11) isn't how binomial coefficients are ordered here (k > n) -- the identity pairs k with n-k within the same n.
Why
The symmetry identity pairs k with n-k: 11-4=7, so C(11,4)=C(11,7)=330.
Compute n-k first (11-4), then find which choice pairs C(11,4) with that exact value.
C(11,4) and C(11,7)