# Binomial coefficients upper bound

It's trivial to show that $\binom{n}{k} \leq 2^n$.

I'm trying to find a smallest constant $c$ such that $\binom{n}{k} \leq c \frac{2^n}{n}$.

-
Are you sure $c \frac{2^n}{n}$ or $c \frac{2^n}{\sqrt n}$ –  users31526 May 30 '12 at 12:31

If $k$ is free, then there is no such $c$. From Stirling's formula, we know that

$$\binom{n}{n/2} \sim \sqrt{\frac{2}{\pi}} \frac{2^n}{n^{1/2}}.$$

Thus if we have $\binom{n}{k} \leq c \frac{2^n}{n^s}$ for all $n$ and $0 \leq k \leq n$, then we must have $s \leq \frac{1}{2}$. More generally, for $0 < r < 1$ and $A = \left((1-r)^{1-r}r^r\right)^{-1}$,

$$\binom{n}{rn} \sim \frac{1}{\sqrt{2\pi r(1-r)}} \frac{A^{n}}{n^{1/2}}$$

-

Use this inequality $\binom{n}{k}\leq \binom{n}{\frac{n}{2}}$ and Stirling's formula.

-