Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

The hint above is what you need.




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.

share|cite|improve this answer
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


  • $\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?

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.