skip to content

Why does the running total C(2,2) + C(3,2) + ... + C(n,2) collapse to the single value C(n+1, 3)?

level: seniorimportance: nice to knowfreq 20%

answer

  1. the terms sit on one diagonal
  2. group by a feature each object has once
  3. condition on the most senior member
  4. the rest come from strictly below
  5. the answer shifts both indices by one

basics

~20 s

Both sides count the 3-member panels formable from n+1 engineers ranked by seniority. Grouping those panels by their most senior member, a panel topped by rank m has its other two chosen from the m-1 below, and summing over m gives exactly that running total.

solid answer

~50 s

Rank n + 1 engineers 1 through n + 1 and count the 3-member panels they can form. Directly, that is C(n+1, 3). Now group the panels by a **distinguished member**: the highest-ranked engineer on each panel. Every panel has exactly one such member, so the grouping is a partition. If the top member has rank m, the other two are chosen from the m - 1 engineers ranked below, giving `C(m-1, 2)` panels in that group. Let m run from 3 to n + 1 and the groups total C(2,2) + C(3,2) + ... + C(n,2). Same collection, two tallies, so the sum equals C(n+1, 3). The general statement is the **hockey-stick identity**: summing a fixed column of the triangle from its first nonzero entry down to row n gives the entry one row further down and one column to the right. The index shift by one is the part people get wrong - the answer is C(n+1, 3), not C(n, 3).

code

pseudocode · 8 lines
pseudocode
// N engineers, ranked 1..N by seniority, all ranks distinct
panels = 0

for m = 3 to N:                       // m = rank of the panel's most senior member
    panels = panels + C(m - 1, 2)     // the other two come from the m - 1 ranked below

// panels now equals C(N, 3)
// with N = n + 1 the loop adds C(2,2) + C(3,2) + ... + C(n,2)

go deeper

for a junior

Notice only that a run of binomial coefficients down one diagonal has a single-value total, and that the total sits one row lower. Checking a small case is enough at this stage.

for a middle

Reproduce the counting argument: rank the roster, group panels by their most senior member, choose the rest from below. Be able to justify both index shifts rather than memorising the formula's shape.

for a senior

Show that you use the underlying move - condition on a distinguished element that every object has exactly once - when a cumulative count resists direct attack, and that you sanity-check the index shift on a small case before quoting a bound.

for a principal

Know when a closed form is worth the effort at all. Collapsing a running total matters when it must be evaluated repeatedly or reasoned about as n grows; for a one-off count, the sum you already have is the cheaper answer.

## What the sum looks like in the triangle Write the binomial coefficients out as a triangle and the terms C(2,2), C(3,2), ..., C(n,2) sit on one **diagonal**: same lower index, increasing upper index. The identity says that diagonal's running total is a single entry, the one at C(n+1, 3) - one row further down, one step across. The picture of a straight run of cells plus the single cell where the total lands is where the name **hockey-stick identity** comes from. ## The distinguished-member argument Double counting does the work, and the trick is choosing what to condition on. Take n + 1 engineers ranked 1 through n + 1 by seniority, all ranks distinct. Count the 3-member panels. - **Direct tally**: choose any 3 of the n + 1 engineers, giving C(n+1, 3) panels. - **Grouped tally**: group each panel under its **most senior member**. That member is unique per panel because ranks are distinct, so every panel is in exactly one group and no panel is missed. - If the top member has rank m, the remaining two members must come from the m - 1 engineers ranked below them, which can be done in `C(m-1, 2)` ways. - m cannot be 1 or 2, because a panel needs two more people below the top; so m runs from 3 to n + 1. Summing the groups gives C(2,2) + C(3,2) + ... + C(n,2), and the two tallies are of one collection, so they are equal. | top member's rank m | others chosen from | panels in the group | |---|---|---| | 3 | 2 engineers below | C(2,2) = 1 | | 4 | 3 engineers below | C(3,2) = 3 | | 5 | 4 engineers below | C(4,2) = 6 | | 6 | 5 engineers below | C(5,2) = 10 | | **total for 6 engineers** | | **20 = C(6,3)** | The table is the worked case n = 5: 1 + 3 + 6 + 10 = 20, and C(6, 3) = 20, which is C(n+1, 3) as claimed. ## The general form and the index bookkeeping In general, the sum of C(i, r) for i running from r up to n equals C(n+1, r+1). Two special cases are worth recognising on sight: 1. **r = 1** gives 1 + 2 + ... + n = C(n+1, 2), the familiar triangular total n(n+1)/2. 2. **r = 2** is the case above, turning a sum of pair-counts into a single triple-count. The upper index of the answer is **n + 1**, not n, and the lower index is **r + 1**, not r. Both shifts come straight from the argument: the roster being panelled has n + 1 members, and the distinguished member is a third person on top of the r chosen below. ## Why the low terms can be ignored Starting the sum at i = 0 instead of i = r changes nothing, because C(i, r) is 0 whenever i < r - there is no way to choose r people from fewer than r. So the identity is insensitive to where you start below r, which is convenient when the sum arrives from some other calculation with a sloppy lower limit. ## Reading it as a technique The reusable idea is **condition on a distinguished element**. When a collection is awkward to count as a whole, find a feature that every member has exactly once - the largest element, the first failure, the earliest deadline - group by it, and count each group. The grouping is automatically a partition because the feature is unique per member, which is the property that licenses summing the groups. - The distinguished feature must be **unique per object**, or the groups overlap. - The groups need not be equal in size; here they grow quadratically. - The direct tally is the closed form; the grouped tally is the sum you were handed. - Verifying a small case is a sanity check on the index shift, not a substitute for the argument. ## Common failures The most frequent error is stating the answer as C(n, 3) - one row short - which a single small case immediately refutes. The next is imagining the terms cancel in pairs, as in a telescoping sum; nothing cancels here, the terms are all positive and each counts a real group of panels. The third is grouping panels by **any** member rather than by the **top** one, which counts each panel three times instead of once and inflates the total.

  • What is the general form of this identity?
    Summing C(i, r) for i from r to n gives C(n+1, r+1) - the hockey-stick identity. The argument is the same one generalised: count the (r+1)-member panels drawable from n + 1 ranked engineers, grouped by the panel's highest rank m, with the remaining r chosen from the m - 1 below. Both indices of the answer rise by one, which is the step people most often drop.
  • What does the case r = 1 give, and does it match something familiar?
    It gives 1 + 2 + ... + n = C(n+1, 2), which is n(n+1)/2 - the ordinary triangular total. The panel reading is that you are counting pairs from n + 1 ranked engineers by conditioning on the more senior member of each pair: if that member has rank m, the partner is any one of the m - 1 below.
  • Why does it not matter whether the sum starts at i = 0 or at i = r?
    Because C(i, r) is 0 for every i below r: you cannot choose r people out of fewer than r. The extra leading terms contribute nothing, so a sum handed to you with a lower limit of 0 has the same value as the same sum starting at r, and the closed form is unchanged.

saying these in an interview costs you the question

  • Says the total is C(n,3), dropping the shift by one row
  • Claims the terms cancel in pairs like a telescoping series
  • Groups panels by any member rather than the most senior one
  • Believes a growing sequence of terms can have no closed form
  • Assumes the sum must begin at index 0 to be valid