Properties of Binomial Coefficients

Theorem

This page gathers together some of the simpler and more common identities concerning binomial coefficients.

Symmetry Rule for Binomial Coefficients

Let $n \in \Z_{>0}, k \in \Z$.

Then:

$\dbinom n k = \dbinom n {n - k}$

Negated Upper Index of Binomial Coefficient

$\dbinom r k = \paren {-1}^k \dbinom {k - r - 1} k$

Moving Top Index to Bottom in Binomial Coefficient

$\dbinom n m = \paren {-1}^{n - m} \dbinom {-\paren {m + 1} } {n - m}$

Factors of Binomial Coefficient

For all $r \in \R, k \in \Z$:

$k \dbinom r k = r \dbinom {r - 1} {k - 1}$

where $\dbinom r k$ is a binomial coefficient.

Hence:

$\dbinom r k = \dfrac r k \dbinom {r - 1} {k - 1}$ (if $k \ne 0$)

and:

$\dfrac 1 r \dbinom r k = \dfrac 1 k \dbinom {r - 1} {k - 1}$ (if $k \ne 0$ and $r \ne 0$)

Pascal's Rule

For positive integers $n, k$ with $1 \le k \le n$:

$\dbinom n {k - 1} + \dbinom n k = \dbinom {n + 1} k$

This is also valid for the real number definition:

$\forall r \in \R, k \in \Z: \dbinom r {k - 1} + \dbinom r k = \dbinom {r + 1} k$

Sum of Binomial Coefficients over Lower Index

$\ds \sum_{i \mathop = 0}^n \binom n i = 2^n$

Alternating Sum and Difference of $r \choose k$ up to $n$

$\ds \sum_{k \mathop \le n} \paren {-1}^k \binom r k = \paren {-1}^n \binom {r - 1} n$

Alternating Sum and Difference of Binomial Coefficients for Given n

$\ds \forall n \in \Z_{\geq 0}: \sum_{i \mathop = 0}^n \paren {-1}^i \binom n i = \delta_{n 0}$

Sum of Even Index Binomial Coefficients

$\ds \sum_{i \mathop \ge 0} \binom n {2 i} = 2^{n - 1}$

Sum of Odd Index Binomial Coefficients

$\ds \sum_{i \mathop \ge 0} \binom n {2 i + 1} = 2^{n - 1}$

Sum of $r+k \choose k$ up to $n$

$\ds \forall n \in \Z: n \ge 0: \sum_{k \mathop = 0}^n \binom {r + k} k = \binom {r + n + 1} n$

Rising Sum of Binomial Coefficients

$\ds \sum_{j \mathop = 0}^m \binom {n + j} n = \binom {n + m + 1} {n + 1} = \binom {n + m + 1} m$

Sum of Binomial Coefficients over Upper Index

\(\ds \sum_{j \mathop = 0}^n \binom j m\)

\(=\)

\(\ds \binom {n + 1} {m + 1}\)

\(\ds \)

\(=\)

\(\ds \dbinom 0 m + \dbinom 1 m + \dbinom 2 m + \cdots + \dbinom n m = \dbinom {n + 1} {m + 1}\)

Increasing Sum of Binomial Coefficients

$\ds \sum_{j \mathop = 0}^n j \binom n j = n 2^{n - 1}$

Increasing Alternating Sum of Binomial Coefficients

$\ds \sum_{j \mathop = 0}^n \paren {-1}^{n + 1} j \binom n j = 0$

Chu-Vandermonde Identity

\(\ds \sum_{k \mathop = 0}^n \binom r k \binom s {n - k}\)

\(=\)

\(\ds \binom r 0 \binom s n + \binom r 1 \binom s {n - 1} + \binom r 2 \binom s {n - 2} + \cdots + \binom r n \binom s 0\)

\(\ds \)

\(=\)

\(\ds \binom {r + s} n\)

Sum of Squares of Binomial Coefficients

$\ds \sum_{i \mathop = 0}^n \binom n i^2 = \binom {2 n} n$

Binomial Coefficient: $\left({-1}\right)^n \dbinom {-n} {k - 1} = \left({-1}\right)^k \dbinom {-k} {n - 1}$

$\paren {-1}^n \dbinom {-n} {k - 1} = \paren {-1}^k \dbinom {-k} {n - 1}$

Binomial Coefficient as Infinite Product

\(\ds \prod_{n \mathop = 1}^\infty \frac {\paren {n + b} } n \frac {\paren {n + a - b} } {\paren {n + a} }\)

\(=\)

\(\ds \frac {\paren {1 + b} } 1 \frac {\paren {1 + a - b} } {\paren {1 + a} } \times \frac {\paren {2 + b} } 2 \frac {\paren {2 + a - b} } {\paren {2 + a} } \times \cdots\)

\(\ds \)

\(=\)

\(\ds \dbinom a b\)

Particular Values

Binomial Coefficient $\dbinom 0 0$

$\dbinom 0 0 = 1$

Binomial Coefficient $\dbinom 0 n$

$\dbinom 0 n = \delta_{0 n}$

$\dbinom m n = \begin{cases}\dfrac {m!} {n! \paren {m - n}!} & : 0 \le n \le m \\&\\0 & : \text { otherwise } \end{cases}$

Binomial Coefficient $\dbinom 1 n$

$\dbinom 1 n = \begin{cases} 1 & : n \in \set {0, 1} \\ 0 & : \text {otherwise} \end{cases}$

N Choose Negative Number is Zero

Let $n \in \Z$ be an integer.

Let $k \in \Z_{<0}$ be a (strictly) negative integer.

Then:

$\dbinom n k = 0$

Binomial Coefficient with Zero

$\forall r \in \R: \dbinom r 0 = 1$

Binomial Coefficient with One

$\forall r \in \R: \dbinom r 1 = r$

Binomial Coefficient with Self

$\forall n \in \Z: \dbinom n n = \sqbrk {n \ge 0}$

where $\sqbrk {n \ge 0}$ denotes Iverson's convention.

That is:

$\forall n \in \Z_{\ge 0}: \dbinom n n = 1$

$\forall n \in \Z_{< 0}: \dbinom n n = 0$

Binomial Coefficient with Self minus One

$\forall n \in \N_{>0}: \dbinom n {n - 1} = n$

Binomial Coefficient with Two

$\forall r \in \R: \dbinom r 2 = \dfrac {r \paren {r - 1} } 2$

Also see

• Summations of Products of Binomial Coefficients