1
$\begingroup$

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

  • 0
    Are you sure $c \frac{2^n}{n}$ or $c \frac{2^n}{\sqrt n}$2012-05-30

2 Answers 2

1

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

1

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