Properties of Binomial Coefficients

From ProofWiki
Jump to navigation Jump to 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