Why does Pascal's rule C(n,k) = C(n-1,k-1) + C(n-1,k) hold combinatorially?
answer
- pick one element and stare at it
- every selection either has it or lacks it
- two cases that can never overlap
- count each case over the remaining n-1
- disjoint alternatives add, they do not multiply
basics
~20 sFix one element and split every selection by whether it is chosen: those including it pick k-1 more from the remaining n-1, those excluding it pick all k from those n-1. The cases are disjoint and exhaustive, so the counts add.
solid answer
~40 sSingle out one particular element — say the first entrant on a list. Every k-member selection either contains that element or it does not, never both, and there is no third possibility. If it contains the element, the rest of the selection is `k-1` items chosen from the other `n-1`, which is `C(n-1,k-1)` ways. If it excludes the element, all `k` items come from the other `n-1`, which is `C(n-1,k)` ways. Because the two cases are disjoint and together cover everything, the total is their sum. That is Pascal's rule. The identity is the include/exclude split that underlies a whole family of counting recurrences, and it gives a way to compute coefficients with additions only — no factorials, no division, no exact-divisibility argument needed.
go deeper
Recall the identity and its base cases C(n,0) = C(n,n) = 1, and be able to extend a couple of rows of coefficients by adding the two entries above each new one. That mechanical fluency is the expectation here.
Give the include/exclude argument out loud: fix one element, count the selections that contain it and those that omit it, state that the cases are disjoint and exhaustive, then add. Algebra is a check, not the answer.
Show when the additive table earns its O(n*k) cost over an O(k) multiplicative loop — many reused coefficients, no division available, or arithmetic performed under a modulus — and how you would bound its memory.
Recognise the shape rather than the formula. Splitting a count on one binary decision into disjoint cases is the same move behind many recurrences a team writes, and naming it explicitly makes those derivations reviewable instead of folkloric.
## What the identity says `C(n,k)` is the number of ways to choose an unordered k-member selection from n distinct items. Pascal's rule states `C(n,k) = C(n-1,k-1) + C(n-1,k)` for `0 < k < n`, with base cases `C(n,0) = C(n,n) = 1`. ## The proof an interviewer wants to hear Do not reach for algebra first. Reach for a **case split on one element**. Single out one specific item — call it the marked item. Now sort all `C(n,k)` selections into two piles: - **The marked item is in the selection.** Then the selection is fully determined by its other `k-1` members, all drawn from the `n-1` unmarked items. There are `C(n-1,k-1)` such selections. - **The marked item is not in the selection.** Then all `k` members come from the `n-1` unmarked items. There are `C(n-1,k)` such selections. Two facts make the sum legitimate, and both must be said out loud: 1. **Disjoint.** No selection is in both piles — an item is either present or absent, never both. So nothing is double-counted. 2. **Exhaustive.** Every selection lands in some pile. So nothing is missed. When cases are disjoint and exhaustive you *add* their counts. That is the whole argument. It is a bijection between the set of all k-selections and the disjoint union of two smaller selection sets, and it is worth being able to state in three sentences. ## Why addition and not multiplication This is the most common confusion. You multiply counts when you are making *independent choices in sequence* — pick a first-place entrant, then a second-place one. You add counts when you are choosing between *mutually exclusive alternatives* — the marked item is in, or it is out. Pascal's rule is the second shape, so the terms add. ## The algebraic check The algebra confirms the identity but does not explain it. Expand both right-hand terms: `C(n-1,k-1) = (n-1)! / ((k-1)! (n-k)!)` and `C(n-1,k) = (n-1)! / (k! (n-1-k)!)` Factor out `(n-1)! / (k! (n-k)!)`. The first term contributes a factor of `k`, the second a factor of `(n-k)`, and `k + (n-k) = n`. So the sum is `n! / (k! (n-k)!) = C(n,k)`. Correct, but it verifies rather than illuminates — which is why the case-split version is the one to lead with. ## The edges Adopt the convention that `C(m,j) = 0` whenever `j < 0` or `j > m`. Then the rule holds everywhere without special cases: - At `k = 0`: the include-branch `C(n-1,-1)` is 0 and the exclude-branch `C(n-1,0)` is 1, total 1 — correct, there is exactly one empty selection. - At `k = n`: the exclude-branch `C(n-1,n)` is 0 and the include-branch `C(n-1,n-1)` is 1, total 1 — correct, there is exactly one way to take everything. Without that convention you must hand-code the boundaries of every row, which is where off-by-one bugs in coefficient tables come from. ## Building coefficients from it Repeated application gives a purely additive way to produce coefficients. Each entry of a row is the sum of the two entries above it: | n \ k | 0 | 1 | 2 | 3 | 4 | |---|---|---|---|---|---| | **0** | 1 | | | | | | **1** | 1 | 1 | | | | | **2** | 1 | 2 | 1 | | | | **3** | 1 | 3 | 3 | 1 | | | **4** | 1 | 4 | 6 | 4 | 1 | The engineering appeal is what the method *avoids*: no factorials, no division, therefore no reasoning about whether an intermediate quotient is exact, and it composes cleanly with arithmetic under a modulus. The cost is `O(n*k)` additions and `O(n*k)` memory for a full table — or `O(n)` memory if you keep only the previous row. Against the `O(k)` time and `O(1)` memory of a running multiply-and-divide loop for a single coefficient, the table only pays for itself when many coefficients get reused, when division is off the table, or when everything is modular. ## The transferable shape Recognising Pascal's rule as *split the count on one binary decision* matters more than the identity itself. The same move — fix an element, condition on whether it participates, count the disjoint cases, add — is how a large family of counting recurrences is derived. Being able to name the move makes those derivations something a reviewer can check, instead of a formula someone remembered.
- What does building a full table of coefficients this way cost you?A table of all `C(n,k)` up to some N costs `O(N^2)` additions and `O(N^2)` memory, or `O(N)` memory if you keep only the previous row. That is far worse than the `O(k)` running-product loop for a single coefficient, but it wins when many coefficients are reused, when division must be avoided, or when the whole computation runs under a modulus.
- Why does the rule still hold at k = 0 and k = n?By adopting the convention `C(m,j) = 0` for `j < 0` or `j > m`. At `k = 0` the include-branch `C(n-1,-1)` is zero and the exclude-branch `C(n-1,0)` is one, giving one. At `k = n` the exclude-branch `C(n-1,n)` is zero and the include-branch is one. Without that convention you have to special-case both ends of every row.
- How would you argue the identity algebraically instead?Write both terms as `(n-1)!/((k-1)!(n-k)!)` and `(n-1)!/(k!(n-1-k)!)`, then factor out `(n-1)!/(k!(n-k)!)`. The first contributes `k`, the second contributes `n-k`, and `k + (n-k) = n`, giving `n!/(k!(n-k)!)`. It confirms the identity but explains nothing; lead with the include/exclude split instead.
saying these in an interview costs you the question
- Claims the two cases overlap and must be corrected
- Multiplies the two terms instead of adding them
- Cannot name the element the split is about
- Treats it as a memorised table rather than a count
- Ignores the zero convention and mis-handles row ends