Binomial Coefficients

Let $\begin{pmatrix}r \\ k \end{pmatrix}$ to denote that choose $k$ elements from a set containing r terms without considering order.

With combinational interpretation. $$ \begin{pmatrix} r \\ k \end{pmatrix} = \frac{n(n - 1) \dots (n - k + 1)}{k(k - 1)\dots 1} = \frac{n!}{(n - k)!\ k!} $$

There are some identities that hold when r is a positive real number and k is non-negative integer.

The first is symmetry identity $$ {r \choose k} = {r \choose r - k} $$ Next, we got *absorption identity* $$ {r \choose k} = \frac{r}{k}{r - 1 \choose k - 1} $$ If we multiply both sides by k, then we have $$ k{r \choose k} = r{r - 1 \choose k - 1} $$ There is a companion identity of the above one. $$ \begin{align}(r - k){r \choose k} &= (r - k) {r \choose r - k} \\&=r{r - 1 \choose r - k - 1} \\&=r{r - 1 \choose k}\end{align} $$ One of the other important formula is called *addition formula* $$ {r \choose k} = {r - 1\choose k - 1} + {r - 1 \choose k} $$ And it's easy to prove.

Beside these, we also have two identities of summation form. $$ \sum_{k = -r}^{n}{{r + k \choose k}} = {r + n + 1 \choose n} $$ and $$ \sum_{k = 0}^{n}{k \choose m} = {n + 1 \choose m + 1} $$ Notice that the summation $0 + 1 + 2 + \dots + n$ is a special case of former identity when $m = 1$ , and its result is equal to $\frac{n(n+ 1)}{2}$ which is ${n + 1 \choose 2}$ manipulated by that formula.

Here is one of the most important identity in binomial coefficients. $$ (x + y)^r =\sum_{k}{{r \choose k}x^ky^{r - k}} $$ And when $x = y = 1$ and $r = n$ is nonnegative integer, we got $$ {n \choose 0} + {n \choose 1} + {n \choose 2} + \dots + {n \choose n} = 2^n $$ If we replace x by -1, then $$ {n \choose 0} - {n \choose 1} + {n \choose 2} - {n \choose 3} + \dots + (-1)^n{n \choose n} = 0 $$

Assumed that $y = 1$ and writing z instead of x to emphasize that an arbitrary complex number can be involved here. $$ (1 + z)^r = \sum_{k}{{r \choose k}z^k} $$