1
$\begingroup$

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.

3 Answers 3

5

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.

1

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

2

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

  • 0
    Nice answwer. After asking I realized this was a naive question, but your drawing makes my question worth it. Thanks a lot.2012-04-25
6

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?

  • 0
    Yes, that's right, my bad. I've not observed the binomial expansion. Thanks a lot.2012-04-20
5

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