# Combinatorial identities

Here’s some random combinatorial identities.

Theorem 1 For any ${n\geqslant 1}$ and ${1\leqslant k\leqslant n-1}$,

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

Proof: For a computational proof,

\displaystyle \begin{aligned} \binom{n-1}k + \binom{n-1}{k-1} &= \frac{(n-1)!}{k!(n-1-k)!} + \frac{(n-1)!}{(k-1)!(n-1-(k-1))!}\\ &= \frac{(n-1)!}{k!(n-1-k)!} + \frac{(n-1)!}{(k-1)!(n-k)!}\\ &= \frac{(n-1)!(n-k)}{k!(n-k)!} + \frac{(n-1)!k}{k!(n-k)!}\\ &= \frac{(n-1)!(n-k+k)}{k!(n-k)!}\\ &= \frac{n!}{k!(n-k)!}\\ &= \binom nk. \end{aligned}

For a combinatorial proof, the LHS is the number of ${k}$-element subsets of ${[n]}$ and the RHS is the number of ${k}$-element subsets of ${[n-1]}$ plus the number of ${k-1}$-element subsets of ${[n-1]}$. Since each ${k}$-element subset of ${[n]}$ either has ${k}$ elements or ${k-1}$ elements of ${[n-1]}$, the two quantities are equal. $\Box$

Theorem 2 For any ${n\geqslant 0}$,

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

Proof: For a computational proof, note that

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

and if the statement holds for some ${n\geqslant0}$ then

\displaystyle \begin{aligned} \sum_{k=0}^{n+1}\binom {n+1}k &= \sum_{k=0}^{n+1}\left[\binom nk + \binom n{k-1}\right]\\ &= \sum_{k=0}^n \binom nk + \sum_{k=1}^{n+1}\binom n{k-1}\\ &= 2\sum_{k=0}^n \binom nk\\ &= 2\cdot 2^n = 2^{n+1}. \end{aligned}

For a combinatorial proof, the LHS is the sum of the number of ${k}$-element subsets of ${[n]}$ for ${k=0,1,\ldots, n}$ and the RHS is the number of subsets of ${[n]}$. Since each subset of ${[n]}$ has exactly one of ${0,1,\ldots,n}$ elements, the two quantities are equal. $\Box$

Theorem 3 For any ${n\geqslant 0}$,

$\displaystyle \sum_{k=0}^n k\binom nk = n2^{n-1}.$

Proof: We compute:

\displaystyle \begin{aligned} \sum_{k=0}^n k\binom nk &= \sum_{k=1}^n k\frac{n!}{k!(n-k)!}\\ &= n\sum_{k=1}^n \frac{(n-1)!}{(k-1)!(n-k)!}\\ &= n\sum_{k=0}^{n-1}\frac{(n-1)!}{k!(n-(k+1))!}\\ &= n\sum_{k=0}^{n-1}\binom {n-1}k\\ &= n2^{n-1}. \end{aligned}

$\Box$

Theorem 4 For any ${n\geqslant1}$ and ${1\leqslant k\leqslant n}$,

$\displaystyle \binom nk = \frac nk\binom{n-1}{k-1}.$

Proof: Since

$\displaystyle \binom{n-1}k = \frac{(n-1)!}{k!(n-1-k)!} = \frac{(n-1)!(n-k)}{k(k-1)!(n-k)!},$

we have

\displaystyle \begin{aligned} \binom nk &= \binom{n-1}{k-1} + \binom{n-1}k\\ &= \binom{n-1}{k-1} + \frac{n-k}k\binom{n-1}{k-1}\\&=\frac nk\binom{n-1}{k-1}. \end{aligned}

$\Box$