Back to Math Tools
Back to notes

# Binomial Coefficients

## Basic identities

The absorption identities. \begin{align} \binom{r}{k} &= \frac{r}{k}\binom{r-1}{k-1},\ k\in\mathbb{Z}\backslash\{0\},\\ k\binom{r}{k} &= r\binom{r-1}{k-1},\ k\in\mathbb{Z},\\ (r-k)\binom{r}{k} &= r\binom{r-1}{k},\ k\in\mathbb{Z}. \end{align}

The addition identities. \begin{align} \binom{r}{k} &= \binom{r-1}{k} + \binom{r-1}{k-1},\ k\in\mathbb{Z},\\ \sum_{k\leq n}\binom{r+k}{k} &= \binom{r+n+1}{n},\ k\in\mathbb{Z},\\ \sum_{0\leq k\leq n}\binom{k}{m} &= \binom{n+1}{m+1},\ m,n\in\mathbb{N}\cup\{0\}. \end{align}

The trinomial revision. \begin{align} \binom{r}{m}\binom{m}{k} &= \binom{r}{k}\binom{r-k}{m-k},\ m,k\in\mathbb{Z}. \end{align}

The Vandermonde convolution. \begin{align} \sum_k\binom{r}{k}\binom{s}{n-k} &= \binom{r+s}{n}. \end{align}

## Stirling’s approximation

Let’s first recall the original Stirling’s formula for factorial.

• Approximation form. \begin{align} n! \sim \sqrt{2\pi n}(\frac{n}{e})^n \, . \end{align}

• Upper/Lower bound form. \begin{align} \sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n}\leq n!\leq en^{n+\frac{1}{2}}e^{-n} \, . \end{align}

• Asymptotic form. $$n! = \sqrt{2\pi n}(\frac{n}{e})^n(1+O(\frac{1}{n})) \, .$$

Apply the above Stirling’s approximation, we have:

• Upper/Lower bound for binomial coefficients. \begin{align} (\frac{n}{k})^k\leq\binom{n}{k}\leq(\frac{en}{k})^k \, . \end{align}
• Entropy bound for binomial coefficients. $$(1-o(1))2^{nH(k/n)}\leq\binom{n}{k}\leq(1+o(1))2^{nH(k/n)} \, .$$

## Binomial theorem

Let $x$, $y$ be arbitrary reals and $n\in\N$, we have $$(x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k.$$

### Multinomial theorem

Let $x_1,\dots,x_m\in\R$ and $n\in\N$, we have $$(x_1+\dots+x_m)^n = \sum_{k_1+\dots+k_m=n}\binom{n}{k_1,\dots,k_m}x_1^{k_1}\cdots x_m^{k+m}.$$

### Generalized binomial theorem

Newton generalized the binomial theorem from nonnegative integers to real exponents.

Let $x$, $y$, and $r$ be arbitrary reals such that $\card{x}>\card{y}$, we have \begin{align} (x+y)^r &= \sum_{k=0}^{\infty}\binom{r}{k}x^{r-k}y^k\\
&= x^r + rx^{r-1}y + \frac{r(r-1)}{2}x^{r-2}y^2 + \frac{r(r-1)(r-2)}{3!}x^{r-3}y^3+\cdots. \end{align}

Note that as $r$ is not a nonnegative integer, we need to redefine $\binom{r}{k}$ for arbitrary $r\in\R$ as follows.

$$\binom{r}{k} = \frac{r(r-1)\cdots(r-k+1)}{k!} = \frac{(r)_k}{k!},$$ where $(\cdot)_k$ is the Pochhammer symbol.

\begin{align} \end{align} \begin{align} \end{align} \begin{align} \end{align}