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}$.
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}$.
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.