Identities and Techniques, Proved

Claim. $\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$ for $1 \le k \le n-1$.

Proof. Count the $k$-subsets of $\{1, 2, \ldots, n\}$, split by whether they contain the element $n$.

If a subset CONTAINS $n$, its remaining $k-1$ elements come from the other $n-1$: $\dbinom{n-1}{k-1}$ such subsets.

If it does NOT contain $n$, all $k$ elements come from the other $n-1$: $\dbinom{n-1}{k}$ such subsets.

Every $k$-subset falls into exactly one case, so the two counts add to the whole. $\blacksquare$

Check. $\dbinom{7}{3} = 35$ and $\dbinom{6}{2} + \dbinom{6}{3} = 15 + 20 = 35$ ✓.

Count the $(r+1)$-element subsets of $\{1, 2, \ldots, n+1\}$. There are $\dbinom{n+1}{r+1}$ of them. That is the right-hand side.

Now count them by their LARGEST element. Every such subset has a largest element $m$, and $m$ must be at least $r+1$ (you need $r$ more elements below it) and at most $n+1$.

For a fixed largest element $m$, the remaining $r$ elements are chosen freely from $\{1, \ldots, m-1\}$, which can be done in $\dbinom{m-1}{r}$ ways.

Sum over the possible largest elements:

$\displaystyle\binom{n+1}{r+1} = \sum_{m=r+1}^{n+1}\binom{m-1}{r} = \sum_{k=r}^{n}\binom{k}{r}$,

substituting $k = m - 1$. Each subset is counted exactly once, because it has exactly one largest element. $\blacksquare$

Rearrange Pascal's Rule $\dbinom{k+1}{r+1} = \dbinom{k}{r} + \dbinom{k}{r+1}$ into

$\displaystyle\binom{k}{r} = \binom{k+1}{r+1} - \binom{k}{r+1}$.

Sum from $k = r$ to $n$. Every term on the right cancels against the next one:

$\displaystyle\sum_{k=r}^{n}\binom{k}{r} = \left[\binom{r+1}{r+1} - \binom{r}{r+1}\right] + \left[\binom{r+2}{r+1} - \binom{r+1}{r+1}\right] + \cdots + \left[\binom{n+1}{r+1} - \binom{n}{r+1}\right]$.

What survives is the last positive term minus the first negative one: $\dbinom{n+1}{r+1} - \dbinom{r}{r+1}$, and $\dbinom{r}{r+1} = 0$ because you cannot choose $r+1$ things from $r$. $\blacksquare$

Two proofs, two uses. The counting proof tells you what the identity MEANS; the telescoping proof is the one that generalises to other sums you can force into the form "next minus this".

Claim. $k^2 = \dbinom{k}{1} + 2\dbinom{k}{2}$ for every integer $k \ge 0$.

Proof. $\dbinom{k}{1} + 2\dbinom{k}{2} = k + 2 \cdot \dfrac{k(k-1)}{2} = k + k(k-1) = k + k^2 - k = k^2$. $\blacksquare$

What it means. Count the ordered pairs $(a, b)$ with $a, b \in \{1, \ldots, k\}$ — there are $k^2$. Split them: the $k$ pairs with $a = b$, and the pairs with $a \ne b$, which come from a 2-element subset in $2$ orders, giving $2\dbinom{k}{2}$. Same set, two counts.

Check at $k = 5$: $\dbinom{5}{1} + 2\dbinom{5}{2} = 5 + 20 = 25 = 5^2$ ✓.

Start from the conversion and sum from $k = 1$ to $n$:

$\displaystyle\sum_{k=1}^{n} k^2 = \sum_{k=1}^{n}\binom{k}{1} + 2\sum_{k=1}^{n}\binom{k}{2}$.

Apply the hockey stick to each piece. The first is $\dbinom{n+1}{2}$; the second is $\dbinom{n+1}{3}$. So

$\displaystyle\sum_{k=1}^{n} k^2 = \binom{n+1}{2} + 2\binom{n+1}{3}$.

That is already a usable answer, and it is the form worth remembering. Expanding it recovers the familiar one:

$\dfrac{(n+1)n}{2} + 2\cdot\dfrac{(n+1)n(n-1)}{6} = \dfrac{n(n+1)}{6}\left[3 + 2(n-1)\right] = \dfrac{n(n+1)(2n+1)}{6}$. $\blacksquare$

Check at $n = 6$: $\dbinom{7}{2} + 2\dbinom{7}{3} = 21 + 70 = 91$, and $1+4+9+16+25+36 = 91$ ✓.

Claim. $\displaystyle\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$.

Proof. A club has $m$ women and $n$ men. Count the committees of size $r$.

First count. Ignore the split: $\dbinom{m+n}{r}$.

Second count. Split by how many women are on it. If exactly $k$ women, choose them in $\dbinom{m}{k}$ ways and the remaining $r-k$ men in $\dbinom{n}{r-k}$ ways. Sum over $k$.

Every committee has one definite number of women, so it is counted once in the second count. $\blacksquare$

Check with $m = 4$, $n = 3$, $r = 3$: $\dbinom40\dbinom33 + \dbinom41\dbinom32 + \dbinom42\dbinom31 + \dbinom43\dbinom30 = 1 + 12 + 18 + 4 = 35 = \dbinom73$ ✓.

Put $m = n$ and $r = n$ in Vandermonde:

$\displaystyle\sum_{k=0}^{n}\binom{n}{k}\binom{n}{n-k} = \binom{2n}{n}$.

Now use the symmetry $\dbinom{n}{n-k} = \dbinom{n}{k}$, and the left side becomes $\sum_k \dbinom{n}{k}^2$. $\blacksquare$

Read it directly: choosing $n$ people from two groups of $n$ means taking $k$ from one and $n-k$ from the other, and the symmetry says "$n-k$ from the second group" is the same count as "$k$ from it".

Check at $n = 4$: $1 + 16 + 36 + 16 + 1 = 70 = \dbinom{8}{4}$ ✓.

Claim. $k\dbinom{n}{k} = n\dbinom{n-1}{k-1}$.

Proof. Count the pairs (committee of size $k$, chair chosen from that committee), out of $n$ people.

First count. Pick the committee ($\dbinom{n}{k}$ ways), then pick its chair from the $k$ members ($k$ ways): $k\dbinom{n}{k}$.

Second count. Pick the chair first, from all $n$ people ($n$ ways), then fill the remaining $k-1$ seats from the other $n-1$ people ($\dbinom{n-1}{k-1}$ ways): $n\dbinom{n-1}{k-1}$.

Both count the same pairs. $\blacksquare$

Check at $n = 8$, $k = 3$: $3\dbinom83 = 3\cdot 56 = 168$ and $8\dbinom72 = 8 \cdot 21 = 168$ ✓.

Apply the identity term by term:

$\displaystyle\sum_{k=0}^{n} k\binom{n}{k} = \sum_{k=1}^{n} n\binom{n-1}{k-1} = n\sum_{j=0}^{n-1}\binom{n-1}{j} = n\,2^{n-1}$,

using $j = k-1$ and the fact that a full row of Pascal's triangle sums to a power of two. $\blacksquare$

In words: add up the sizes of all $2^n$ subsets of an $n$-set. Each element lies in exactly half of them, so it contributes $2^{n-1}$, and there are $n$ elements.

Check at $n = 5$: $0 + 5 + 20 + 30 + 20 + 5 = 80 = 5 \cdot 16$ ✓.

The same trick with $k^2$ gives $\sum k^2\dbinom{n}{k} = n(n+1)2^{n-2}$ — apply absorption twice, or use the square conversion from the previous section.

Claim. The number of solutions of $x_1 + x_2 + \cdots + x_k = n$ in NON-NEGATIVE integers is $\dbinom{n+k-1}{k-1}$.

Proof. Write $n$ stars in a row and insert $k-1$ bars among them; the bars cut the stars into $k$ (possibly empty) groups, and the group sizes are a solution.

The row has $n + k - 1$ symbols in total, and the arrangement is determined entirely by WHICH of those positions hold bars — so there are $\dbinom{n+k-1}{k-1}$ arrangements.

The map from arrangements to solutions is a bijection: every arrangement gives one solution, and every solution is produced by exactly one arrangement (put $x_1$ stars, a bar, $x_2$ stars, a bar, …). $\blacksquare$

Check: $x_1+x_2+x_3 = 4$ has $\dbinom{6}{2} = 15$ non-negative solutions, and listing them gives $15$ ✓.

Claim. $\displaystyle\left|A_1 \cup \cdots \cup A_n\right| = \sum|A_i| - \sum|A_i \cap A_j| + \sum|A_i \cap A_j \cap A_k| - \cdots$

Proof. Take any element $x$ in the union, and suppose it lies in exactly $m \ge 1$ of the sets. Count how much it contributes to the right-hand side.

It is counted $\dbinom{m}{1}$ times among the single sets, $\dbinom{m}{2}$ times among the pairwise intersections, $\dbinom{m}{3}$ times among the triples, and so on. Its total contribution is

$\displaystyle\binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots = 1 - \left[\binom{m}{0} - \binom{m}{1} + \binom{m}{2} - \cdots\right] = 1 - (1-1)^m = 1 - 0 = 1$,

by the binomial theorem. So every element of the union contributes exactly $1$, and elements outside contribute $0$. $\blacksquare$

That is where the alternating signs come from: they are exactly what makes $(1-1)^m$ collapse to zero.

Claim. For any random variables $X_1, \ldots, X_n$ on the same sample space, $E[X_1 + \cdots + X_n] = E[X_1] + \cdots + E[X_n]$.

Proof. Expectation is a weighted sum over outcomes:

$\displaystyle E\left[\sum_i X_i\right] = \sum_{\omega} P(\omega)\sum_i X_i(\omega) = \sum_i \sum_{\omega} P(\omega)X_i(\omega) = \sum_i E[X_i]$,

the middle step being nothing but swapping the order of a finite double sum. $\blacksquare$

Notice what is missing: independence. It is never used. This is why linearity is so powerful — it applies to variables that are tangled together in ways you could not possibly analyse directly.

Claim. For $n \ge 1$, the even-index entries of row $n$ of Pascal's triangle sum to $2^{n-1}$, and so do the odd-index ones.

Proof. The binomial theorem gives two equations:

$\displaystyle (1+1)^n = \sum_k \binom{n}{k} = 2^n$ and $\displaystyle (1-1)^n = \sum_k (-1)^k\binom{n}{k} = 0$.

Add them. The odd terms cancel and the even ones double: $2\sum_{k \text{ even}}\dbinom{n}{k} = 2^n$, so the even sum is $2^{n-1}$. Subtracting instead gives the same value for the odd sum. $\blacksquare$

Check at $n = 5$: evens $1 + 10 + 5 = 16$, odds $5 + 10 + 1 = 16$, and $2^4 = 16$ ✓.

The technique in general is called a roots-of-unity filter: evaluating at $1$ and $-1$ selects residues mod $2$; evaluating at the cube roots of unity selects residues mod $3$, and so on.