$$ \binom{n}{r} = \binom{n - 1}{r - 1} + \binom{n - 1}{r} $$
言わずもがな.パスカルの三角形
$$ \binom{n}{r} = \frac{n}{r} \binom{n - 1}{r - 1} $$
定義から明らか.
$$ \sum_{i = r}^{n} \binom{i}{r} = \binom{n + 1}{r + 1} $$
Hockey-stick identity. 次のように1を繰り返し適用. $\binom{n + 1}{r + 1} = \binom{n}{r} + \binom{n}{r + 1} = \binom{n}{r} + \binom{n - 1}{r} + \binom{n - 1}{r + 1} = \binom{n}{r} + \binom{n - 1}{r} + \binom{n - 2}{r} + \binom{n - 2}{r + 1} = \dots$
$$ \sum_{i = 0}^{r}\binom{n}{i}\binom{m}{r - i} = \binom{n + m}{r} $$
$|A| = n$, $|B| = m$ であるとき,$A$ と $B$ の排他和から $r$ 個取るのは,$A$ から $i$ 個取って $B$ から $r - i$ 個取ることになる.
$$ \sum_{i = 0}^{r}\binom{n}{i}\binom{m}{r + i} = \binom{n + m}{n + r} $$
上と類似.左辺は $\sum_{i = 0}^{r}\binom{n}{n - i}\binom{m}{i + r}$ と書き直せる. $A$ と $B$ の排他和から $n + r$ 個取るときには,少なくとも $B$ から $r$ 個は取るので,$B$ から $i + r$ 個,$A$ から $n - i$ 個取ることになる.
$$ \sum_{r = 0}^{n} r \binom{n}{r} = n 2^{n - 1} $$
(左辺) $= \sum_{r = 1}^{n} r \binom{n}{r} = n \sum_{r = 1}^{n} \binom{n - 1}{r - 1} = n 2^{n - 1} =$ (右辺)