Properties and identities of binomial coefficients

The binomial coefficient $\binom{n}{r}$ is more than a number that appears in an expansion. It is a counting object , the number of $r$-subsets of an $n$-set , and that combinatorial meaning generates a whole catalogue of identities. We collect the most useful ones here. Every identity has both an algebraic proof (manipulating factorials or expansions) and a combinatorial proof (counting the same thing two ways). Whenever possible, learn both , they protect against memory failures.

Definitions

For non-negative integers $0 \le r \le n$, $\binom{n}{r} = \frac{n!}{r!\,(n - r)!}.$ We extend the definition by $\binom{n}{r} = 0$ if $r < 0$ or $r > n$. The shorthand $C_r := \binom{n}{r}$ is common when $n$ is fixed.

Key identities

1. Symmetry. $\binom{n}{r} = \binom{n}{n - r}$.

Algebraically obvious from the formula. Combinatorially: choosing $r$ to include is the same as choosing $n - r$ to exclude.

2. Pascal's rule. $\binom{n}{r} = \binom{n - 1}{r - 1} + \binom{n - 1}{r}$ for $1 \le r \le n - 1$.

Algebra: common denominator. Combinatorics: fix one element. Either include it (then choose $r - 1$ from the rest: $\binom{n-1}{r-1}$ ways) or exclude it (choose $r$ from the rest: $\binom{n-1}{r}$ ways).

3. Absorption. $r \binom{n}{r} = n \binom{n - 1}{r - 1}$.

Both sides count: choose a committee of $r$ from $n$ with a designated leader. LHS: pick the committee, then the leader. RHS: pick the leader first ($n$ ways), then the rest of the committee ($\binom{n-1}{r-1}$ ways).

4. Sum of all coefficients. $\sum_{r=0}^n \binom{n}{r} = 2^n$.

Set $a = b = 1$ in the binomial theorem. Combinatorial: the total number of subsets of an $n$-set is $2^n$, and we partition them by size.

5. Alternating sum. $\sum_{r=0}^n (-1)^r \binom{n}{r} = 0$ for $n \ge 1$.

Set $a = 1, b = -1$ in the binomial theorem. Combinatorial: an $n$-set has equally many even- and odd-sized subsets.

6. Sum of squares. $\sum_{r=0}^n \binom{n}{r}^2 = \binom{2n}{n}$.

Compare the coefficient of $x^n$ on both sides of $(1 + x)^n (1 + x)^n = (1 + x)^{2n}$.

7. Sum of even-indexed = sum of odd-indexed. $\sum_{r \text{ even}} \binom{n}{r} = \sum_{r \text{ odd}} \binom{n}{r} = 2^{n-1}$ for $n \ge 1$.

Add and subtract identities (4) and (5).

8. Vandermonde's identity. $\binom{m + n}{r} = \sum_{k=0}^r \binom{m}{k}\binom{n}{r - k}$.

Choose $r$ from $m + n$ people: split by how many come from the first group.

Worked examples

Example 1. Show $\binom{10}{3} = \binom{10}{7}$.

By symmetry. Numerically: $\binom{10}{3} = 120 = \binom{10}{7}$.

Example 2. Prove $\sum_{r=0}^n r \binom{n}{r} = n \cdot 2^{n-1}$.

Use absorption: $r \binom{n}{r} = n \binom{n-1}{r-1}$. Then $\sum_{r=0}^n r \binom{n}{r} = n \sum_{r=1}^n \binom{n-1}{r-1} = n \sum_{s=0}^{n-1} \binom{n-1}{s} = n \cdot 2^{n-1}. \qed$

Alternatively, differentiate $(1 + x)^n$ at $x = 1$.

Example 3. Show $\sum_{r=0}^n \binom{n}{r}^2 = \binom{2n}{n}$.

Compare coefficients of $x^n$ in $(1 + x)^n (1 + x)^n$ and $(1 + x)^{2n}$. On the left, $\text{coeff of } x^n = \sum_{r=0}^n \binom{n}{r} \binom{n}{n - r} = \sum_{r=0}^n \binom{n}{r}^2,$ by symmetry. On the right, it is $\binom{2n}{n}$.

Example 4. Prove $\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \dots = 2^{n-1}$ for $n \ge 1$.

Add $(1 + 1)^n = \sum \binom{n}{r}$ and $(1 - 1)^n = \sum (-1)^r \binom{n}{r}$. Odd-$r$ terms cancel, even-$r$ terms double: $2 \sum_{r \text{ even}} \binom{n}{r} = 2^n \Rightarrow \sum_{r \text{ even}} \binom{n}{r} = 2^{n-1}.$

Example 5. Find the value of $\binom{50}{4} + \sum_{r=1}^{6} \binom{56 - r}{3}$.

Use Pascal repeatedly: $\binom{50}{4} + \binom{50}{3} = \binom{51}{4}$. Then $\binom{51}{4} + \binom{51}{3} = \binom{52}{4}$, and so on. After applying $\binom{56 - r}{3}$ for $r = 6, 5, \dots, 1$, the sum collapses to $\binom{56}{4}$.

Try it yourself

1. Compute $\binom{12}{5}$.
2. Show $\binom{n}{r} + \binom{n}{r - 1} = \binom{n+1}{r}$ from the factorial definition.
3. Prove $\sum_{r=0}^n (-1)^r r \binom{n}{r} = 0$ for $n \ge 2$.
4. Show $\sum_{r=0}^n \dfrac{\binom{n}{r}}{r + 1} = \dfrac{2^{n+1} - 1}{n + 1}$. (Hint: integrate $(1 + x)^n$ from $0$ to $1$.)
5. Prove that $\sum_{r=0}^n r^2 \binom{n}{r} = n(n+1) 2^{n-2}$.
6. Compute $\binom{20}{0} + \binom{20}{2} + \binom{20}{4} + \dots + \binom{20}{20}$.
7. If $\binom{2n}{3} : \binom{n}{2} = 44 : 3$, find $n$.
8. Prove $\binom{n}{1} - 2\binom{n}{2} + 3\binom{n}{3} - \dots + (-1)^{n-1} n \binom{n}{n} = 0$ for $n \ge 2$.
9. Show that $\binom{n}{r}$ is largest when $r = \lfloor n/2 \rfloor$ or $\lceil n/2 \rceil$.
10. Prove Vandermonde's identity combinatorially.
11. Find $\sum_{r=1}^{n} r \binom{n}{r}^2$. (Answer: $n \binom{2n-1}{n-1}$.)
12. If $C_0, C_1, \dots, C_n$ are coefficients of $(1 + x)^n$, prove $C_0 C_r + C_1 C_{r+1} + \dots + C_{n-r} C_n = \binom{2n}{n-r}$.

Pitfalls / Tricks

• Don't confuse "coefficient of $x^r$" with "the $r$-th term". The former corresponds to $r$ in the formula; the latter is $T_{r+1}$.
• When using Pascal's rule iteratively, the indices must be consecutive , check carefully.
• Many sums of binomial coefficients yield to the trick: evaluate $(1 + x)^n$ at clever values of $x$ (like $1, -1, i$).
• Insight. Every identity here has a combinatorial meaning. If you ever forget the formula, ask: what am I counting?