Properties of Binomial Coefficients

From ProofWiki
Jump to: navigation, search

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 = \left({-1}\right)^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

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


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

$\displaystyle \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

$\displaystyle \forall n \in \Z: \sum_{i \mathop = 0}^n \left({-1}\right)^i \binom n i = \delta_{n 0}$


Sum of Even Index Binomial Coefficients

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


Sum of Odd Index Binomial Coefficients

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


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

$\displaystyle \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

$\displaystyle \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

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


Increasing Sum of Binomial Coefficients

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


Increasing Alternating Sum of Binomial Coefficients

$\displaystyle \sum_{j \mathop = 0}^n \left({-1}\right)^{n + 1} j \binom n j = 0$


Chu-Vandermonde Identity

$\displaystyle \sum_k \binom r k \binom s {n - k} = \binom {r + s} n$


Sum of Squares of Binomial Coefficients

$\displaystyle \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}$

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


Particular Values

Binomial Coefficient $\dbinom 0 0$

$\dbinom 0 0 = 1$


Binomial Coefficient $\dbinom 0 n$

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


Binomial Coefficient $\dbinom 1 n$

$\dbinom 1 n = \begin{cases} 1 & : n \in \left\{ {0, 1}\right\} \\ 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 = \left[{n \ge 0}\right]$

where $\left[{n \ge 0}\right]$ 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 \left({r - 1}\right)} 2$


Also see