Take the 2-minute tour ×

I today see a approximated equation, when $n \ll u $:

$$\log {u \choose n} \approx n \Big(\log \frac{u}{n} + 1.44\Big)$$

I would like to know how to prove it.

share|improve this question
en.wikipedia.org/wiki/… –  pedja Apr 24 '12 at 8:47
Use Stirling's approximation for $n!$. –  Johannes Kloos Apr 24 '12 at 9:05
@JohnBentin No, I mean n is smaller than u. –  Fan Zhang Apr 24 '12 at 16:12

1 Answer 1

up vote 0 down vote accepted

It looks like pedja has pointed you in the right direction here. On Wikipedia there's the bounds: \begin{align*} {u \choose n} &= \frac{1}{n!} u(u-1)\cdots(u-n+1) \\ & \leq \frac{u^n}{n!} \\ & \leq \left(\frac{u\ e}{n}\right)^n \end{align*} since $n! \geq \left(\frac{n}{e}\right)^n$, and \begin{align*} {u \choose n} & = \frac{u}{n} \cdot \frac{u-1}{n-1} \cdots \frac{u-n+1}{1} \\ & \geq \left(\frac{u}{n}\right)^n. \end{align*}

By taking $\log_2$ of both sides of these bounds, we obtain \[n \log_2 \frac{u}{n} \leq \log_2 {u \choose n} \leq n \left(\log_2 \frac{u}{n}+\log_2 e\right),\] where $\log_2 e$ is approximately $1.44$.

If $n=o(\log u)$, then \[\log_2 {u \choose n} \sim n \log_2 \frac{u}{n},\] so the $1.44$ won't be necessary.

share|improve this answer

Your Answer


