Binomial Coefficients
Let (rk) to denote that choose k elements from a set containing r terms without considering order.
With combinational interpretation. (rk)=n(n−1)…(n−k+1)k(k−1)…1=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}