The factorial formula facilitates relating nearby binomial coefficients. For instance, if
k is a positive integer and
n is arbitrary, then {{NumBlk2|:| \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}|5}} and, with a little more work, \binom {n-1}{k} - \binom{n-1}{k-1} = \frac{n-2k}{n} \binom{n}{k}. We can also get \binom {n-1}{k} = \frac{n-k}{n} \binom {n}{k}. Moreover, the following may be useful: \binom{n}{k}\binom{k}{j} = \binom{n}{j}\binom{n-j}{k-j}=\binom{n}{k-j}\binom{n-k+j}{j}. For constant
n, we have the following recurrence: \binom{n}{k} = \frac{n-k+1}{k} \binom{n}{k-1}. To sum up, we have \binom {n}{k} = \binom n{n-k} = \frac{n-k+1}{k} \binom {n}{k-1} = \frac{n}{n-k} \binom {n-1}{k} = \frac{n}{k} \binom {n-1}{k-1} = \frac{n}{n-2k} \Bigg(\binom {n-1}{k} - \binom{n-1}{k-1}\Bigg) = \binom{n-1}k + \binom{n-1}{k-1}.
Sums of the binomial coefficients The formula {{NumBlk2|:| \sum_{k=0}^n \binom n k = 2^n|∗∗}} says that the elements in the th row of Pascal's triangle always add up to 2 raised to the th power. This is obtained from the binomial theorem () by setting and . The formula also has a natural combinatorial interpretation: the left side sums the number of subsets of {1, ...,
n} of sizes
k = 0, 1, ...,
n, giving the total number of subsets. (That is, the left side counts the
power set of {1, ...,
n}.) However, these subsets can also be generated by successively choosing or excluding each element 1, ...,
n; the
n independent binary choices (bit-strings) allow a total of 2^n choices. The left and right sides are two ways to count the same collection of subsets, so they are equal. The formulas {{NumBlk2|:|\sum_{k=0}^n k \binom{n}{k} = n 2^{n-1}|6}} and \sum_{k=0}^n k^2 \binom n k = (n + n^2)2^{n-2} follow from the binomial theorem after
differentiating with respect to (twice for the latter) and then substituting . The
Chu–Vandermonde identity, which holds for any complex values
m and
n and any non-negative integer
k, is {{NumBlk2|:| \sum_{j=0}^k \binom m j \binom{n-m}{k-j} = \binom n k|7}} and can be found by examination of the coefficient of x^k in the expansion of using equation (). When , equation () reduces to equation (). In the special case , using (), the expansion () becomes (as seen in Pascal's triangle at right) {{Image frame|width=395 \begin{array}{c} 1 \\ 1 \qquad 1 \\ 1 \qquad 2 \qquad 1 \\ {\color{blue}1 \qquad 3 \qquad 3 \qquad 1} \\ 1 \qquad 4 \qquad 6 \qquad 4 \qquad 1 \\ 1 \qquad 5 \qquad 10 \qquad 10 \qquad 5 \qquad 1 \\ 1 \qquad 6 \qquad 15 \qquad {\color{red}20} \qquad 15 \qquad 6 \qquad 1 \\ 1 \qquad 7 \qquad 21 \qquad 35 \qquad 35 \qquad 21 \qquad 7 \qquad 1 \end{array} }} {{NumBlk2|:| \sum_{j=0}^m \binom{m}{j} ^2 = \binom {2m} m,|8}} where the term on the right side is a
central binomial coefficient. Another form of the Chu–Vandermonde identity, which applies for any integers
j,
k, and
n satisfying , is {{NumBlk2|:|\sum_{m=0}^n \binom m j \binom {n-m}{k-j}= \binom {n+1}{k+1}.|9}} The proof is similar, but uses the binomial series expansion () with negative integer exponents. When , equation () gives the
hockey-stick identity \sum_{m=k}^n \binom m k = \binom {n+1}{k+1} and its relative \sum_{r=0}^m \binom {n+r} r = \binom {n+m+1}{m}. Let
F(
n) denote the
n-th
Fibonacci number. Then \sum_{k=0}^{\lfloor n/2\rfloor} \binom {n-k} k = F(n+1). This can be proved by
induction using () or by
Zeckendorf's representation. A combinatorial proof is given below.
Multisections of sums For integers
s and
t such that ,
series multisection gives the following identity for the sum of binomial coefficients: \binom{n}{t}+\binom{n}{t+s}+\binom{n}{t+2s}+\ldots=\frac{1}{s}\sum_{j=0}^{s-1}\left(2\cos\frac{\pi j}{s}\right)^n\cos\frac{\pi(n-2t)j}{s}. For small , these series have particularly nice forms; for example, \binom{n}{0} + \binom{n}{3}+\binom{n}{6}+\cdots = \frac{1}{3}\left(2^n +2 \cos\frac{n\pi}{3}\right) \binom{n}{1} + \binom{n}{4}+\binom{n}{7}+\cdots = \frac{1}{3}\left(2^n +2 \cos\frac{(n-2)\pi}{3}\right) \binom{n}{2} + \binom{n}{5}+\binom{n}{8}+\cdots = \frac{1}{3}\left(2^n +2 \cos\frac{(n-4)\pi}{3}\right) \binom{n}{0} + \binom{n}{4}+\binom{n}{8}+\cdots = \frac{1}{2}\left(2^{n-1} +2^{\frac{n}{2}} \cos\frac{n\pi}{4}\right) \binom{n}{1} + \binom{n}{5}+\binom{n}{9}+\cdots = \frac{1}{2}\left(2^{n-1} +2^{\frac{n}{2}} \sin\frac{n\pi}{4}\right) \binom{n}{2} + \binom{n}{6}+\binom{n}{10}+\cdots = \frac{1}{2}\left(2^{n-1} -2^{\frac{n}{2}} \cos\frac{n\pi}{4}\right) \binom{n}{3} + \binom{n}{7}+\binom{n}{11}+\cdots = \frac{1}{2}\left(2^{n-1} -2^{\frac{n}{2}} \sin\frac{n\pi}{4}\right)
Partial sums Although there is no
closed formula for
partial sums \sum_{j=0}^k \binom n j of binomial coefficients, one can again use () and induction to show that for , \sum_{j=0}^k (-1)^j\binom{n}{j} = (-1)^k\binom {n-1}{k}, with special case \sum_{j=0}^n (-1)^j\binom n j = 0 for . This latter result is also a special case of the result from the theory of
finite differences that for any polynomial
P(
x) of degree less than
n, \sum_{j=0}^n (-1)^j\binom n j P(j) = 0. Differentiating ()
k times and setting
x = −1 yields this for , when 0 ≤
k \sum_{j=0}^n (-1)^j\binom n j P(n-j) = n!a_n|10}} where a_n is the coefficient of degree
n in
P(
x). More generally for (), \sum_{j=0}^n (-1)^j\binom n j P(m+(n-j)d) = d^n n! a_n where
m and
d are complex numbers. This follows immediately applying () to the polynomial instead of , and observing that still has degree less than or equal to
n, and that its coefficient of degree
n is
dnan. The
series \frac{k-1}{k} \sum_{j=0}^\infty \frac 1 {\binom {j+x} k}= \frac 1 {\binom{x-1}{k-1}} is convergent for
k ≥ 2. This formula is used in the analysis of the
German tank problem. It follows from \frac{k-1}k\sum_{j=0}^{M}\frac 1 {\binom{j+x} k}=\frac 1{\binom{x-1}{k-1}}-\frac 1{\binom{M+x}{k-1}} which is proved by
induction on
M.
Identities with combinatorial proofs Many identities involving binomial coefficients can be proved by
combinatorial means. For example, for nonnegative integers {{tmath|{n} \geq {q} }}, the identity \sum_{k=q}^n \binom{n}{k} \binom{k}{q} = 2^{n-q}\binom{n}{q} (which reduces to () when
q = 1) can be given a
double counting proof, as follows. The left side counts the number of ways of selecting a subset of [
n] = {1, 2, ...,
n} with at least
q elements, and marking
q elements among those selected. The right side counts the same thing, because there are \tbinom n q ways of choosing a set of
q elements to mark, and 2^{n-q} to choose which of the remaining elements of [
n] also belong to the subset. In Pascal's identity \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}, both sides count the number of
k-element subsets of [
n]: the two terms on the right side group them into those that contain element
n and those that do not. The identity () also has a combinatorial proof. The identity reads \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}. Suppose you have 2n empty squares arranged in a row and you want to mark (select)
n of them. There are \tbinom {2n}n ways to do this. On the other hand, you may select your
n squares by selecting
k squares from among the first
n and n-k squares from the remaining
n squares; any
k from 0 to
n will work. This gives \sum_{k=0}^n\binom n k\binom n{n-k} = \binom {2n} n. Now apply () to get the result. If one denotes by the sequence of
Fibonacci numbers, indexed so that , then the identity \sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor} \binom {n-k} k = F(n) has the following combinatorial proof. One may show by
induction that counts the number of ways that a strip of squares may be covered by and tiles. On the other hand, if such a tiling uses exactly of the tiles, then it uses of the tiles, and so uses tiles total. There are \tbinom{n-k}{k} ways to order these tiles, and so summing this coefficient over all possible values of gives the identity.
Sum of coefficients row The number of
k-
combinations for all
k, {{tmath|1=\sum_{0\leq{k}\leq{n} }\binom nk = 2^n}}, is the sum of the
nth row (counting from 0) of the binomial coefficients. These combinations are enumerated by the 1 digits of the set of
base 2 numbers counting from 0 to , where each digit position is an item from the set of
n.
Dixon's identity Dixon's identity is \sum_{k=-a}^{a}(-1)^{k}\binom{2a}{k+a}^3 =\frac{(3a)!}{(a!)^3} or, more generally, \sum_{k=-a}^a(-1)^k\binom{a+b}{a+k} \binom{b+c}{b+k}\binom{c+a}{c+k} = \frac{(a+b+c)!}{a!\,b!\,c!}\,, where
a,
b, and
c are non-negative integers.
Continuous identities Certain trigonometric integrals have values expressible in terms of binomial coefficients: For any , \int_{-\pi}^{\pi} \cos((2m-n)x)\cos^n(x)\ dx = \frac{\pi}{2^{n-1}} \binom{n}{m} \int_{-\pi}^{\pi} \sin((2m-n)x)\sin^n(x)\ dx = \begin{cases} (-1)^{m+(n+1)/2} \frac{\pi}{2^{n-1}} \binom{n}{m}, & n \text{ odd} \\ 0, & \text{otherwise} \end{cases} \int_{-\pi}^{\pi} \cos((2m-n)x)\sin^n(x)\ dx = \begin{cases} (-1)^{m+(n/2)} \frac{\pi}{2^{n-1}} \binom{n}{m}, & n \text{ even} \\ 0, & \text{otherwise} \end{cases} These can be proved by using
Euler's formula to convert
trigonometric functions to complex exponentials, expanding using the binomial theorem, and integrating term by term.
Congruences If
n is prime, then \binom {n-1}k \equiv (-1)^k \mod n for every
k with . More generally, this remains true if
n is any number and
k is such that all the numbers between 1 and
k are coprime to
n. Indeed, we have \binom {n-1} k = {(n-1)(n-2)\cdots(n-k)\over 1\cdot 2\cdots k} = \prod_{i=1}^{k}{n-i\over i}\equiv \prod_{i=1}^{k}{-i\over i} = (-1)^k \mod n. == Generating functions ==