Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers

up vote 5 down vote accepted

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.

share|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
add comment

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?

share|improve this answer
2  
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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.