# Combinatorial inequality $\binom{n}{j}\leqslant 2^n$

I was trying to prove (or to find a counterexample) of the following inequality:

$$\binom{n}{j}\leqslant 2^n$$

As I coudn't find a proof/counterexample, I tested some numbers and could see it working up to $n=12$. Does anyone have a proof/counterexample of it? I've tried to pass the $\log_2$ in both sides, in order to use properties of $\log$, but I could't find anything better. Any help will be appreciated.

-

The hint above is what you need.

$$\sum_{j=0}^{n}\binom{n}{j}=2^n$$

or

$$1+n+\frac{n(n-1)}{2}+\dots+\huge\binom{n}{j}\normalsize+\dots+\frac{n(n-1)}{2}+n+1=2^n$$

For understand a litle more what's going, see this images:

When we have $n=0$,

$\binom 0 0=1=2^0=1$, so it's ok.

Let's see what happens when we increase $n$.

In this case, $n=1$, and the $\binom n j$ is the blue curve.

A this case, $n=10$, and the blue curve is $\binom n j$.

Now we can you see what happens when $n$ grows.

-
Nice answwer. After asking I realized this was a naive question, but your drawing makes my question worth it. Thanks a lot. –  matgaio Apr 25 '12 at 20:52

Hint:

• $\displaystyle\sum_{j=0}^n \binom n j=2^n$

• $\displaystyle \binom n j, j \in [n]$ is the number of ways of choosing $j$ objects from $n$ of them. Can this be zero or negative?

-
Fast typing ;-) –  dtldarek Apr 20 '12 at 21:28
@dtldarek :) ${}{}{}$ –  user21436 Apr 20 '12 at 21:28
However, my hint would be different: $2^n = (1+1)^n$ ;-) –  dtldarek Apr 20 '12 at 21:29
Yes, that's right, my bad. I've not observed the binomial expansion. Thanks a lot. –  matgaio Apr 20 '12 at 21:33

Consider a set $S$ with $n$ elements. $2^n$ is the cardinality of the collection of all subsets of $S$, whereas $\binom nk$ is the cardinality of all the subsets of $S$ with cardinal $k$.

-