Looking for an easy proof that the binomial coefficient is bounded by $2^{n-1}$

Question

I am looking for the easiest proof that $\binom{n}{k}\leq 2^{n-1}$ (hopefully even with no induction...).

Note: if $k\neq \frac{n}{2}$, then I have a one liner: $$2\binom{n}{k} = \binom{n}{k}+\binom{n}{n-k} \leq (1+1)^n = 2^n.$$

So perhaps it suffices to show that $\binom{2 d}{d} \leq 2^{2d-1}$, but I would prefer a proof with no separation to cases.

I am not seeing how $\binom nk + \binom n{n-k}\leqslant (1+1)^n$. Perhaps you could elaborate on that? — Math1000, Oct 16 '19 at 16:19
Expand the rhs, then you get many positive terms including the two on the lhs — Lior B-S, Nov 09 '19 at 02:09

score 2 · Accepted Answer · answered Oct 16 '19 at 13:56

2

$\binom{2n}{n} = \binom{2n-1}{n-1} + \binom{2n-1}{n} = 2 \binom{2n-1}{n-1}$

and $\binom{2n-1}{n-1} \le 2^{2n-2}$ by your one liner

$\Rightarrow \binom{2n}{n} \le 2^{2n-1}$

answered Oct 16 '19 at 13:56

gandalf61

1 Answers1