# Basic combinatorics proofs

$$\displaystyle \binom{n + 1}{2} - \binom{n}{2} = n$$
$$\displaystyle \binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}$$
For $$0 \le k \le n$$,  $$\displaystyle n! = \binom{n}{k}k!(n - k)!$$.
For $$0 \le k \le n$$,  $$\displaystyle \binom{n}{k} = \binom{n}{n - k}$$.
For $$k, n \ge 0$$,  $$\displaystyle \left({\mkern-5mu}{\binom{n}{k}}\mkern-5mu\right) = \binom{n + k - 1}{k}$$.
For $$0 \le k \le n$$,  $$\displaystyle \sum_{k = 0}^n \binom{n}{k} = 2^n$$.
For any $$x, y \in \mathbb{N}$$ and $$n \ge 1$$,  $$\displaystyle (x + y)^n = \sum_{k = 0}^n \binom{n}{k}x^ky^{n - k}$$.
For $$0 \le k \le n$$,  $$\displaystyle \sum_{k = 0}^n \binom{n}{2k} = 2^{n - 1}$$.
For $$0 \le k \le n$$,  $$\displaystyle \sum_{k = 0}^n \binom{n}{2k} = 2^{n - 1}$$.
For $$0 \le k \le n$$,  $$\displaystyle k\binom{n}{k} = n\binom{n - 1}{k - 1}$$.
For $$0 \le m \le k \le n$$,  $$\displaystyle \binom{n}{k}\binom{k}{m} = \binom{n}{m}\binom{n - m}{k - m}$$.
$$\displaystyle \binom{2n}{2} = 2\binom{n}{2} + n^2$$
Algebraic proof