For any integer $n>1$ prove that,

$$\large 2^n < {2n \choose n} < \frac{2^n}{\prod^{i=n-1}_{i=0}(1-\frac{i}{n})}$$

Now proving that the first term is smaller than the third term is trivial, since the term in the denominator is merely a product of $(1-\frac{i}{n})$ for $i \in \{0,1,2,....n-1\}$. Thus each individual term is less than $1$ and the entire denominator is less than 1, and we know

$$t<1 \implies 1<\frac{1}{t} \implies x<\frac{x}{t}|x,t>0$$

$2^n$ happens to be the total number of possible ways to select $r$ objects from $n$ objects for $r \in \{0,1...n\}$ and $2n \choose n$ happens to be the number of ways to choose $n$ objects from a selection of $2n$ objects, and it seems quite obvious to me that it would be greater than $2^n$ because selecting $r$ objects from $n$ followed by selecting $n-r$ from $2n-r$ would lead to $2n \choose n$. But I am not being able to prove that the second term in the inequality is smaller than the third.

Any help would be warmly appreciated. Also are there any flaws in the argument I presented?

  • $\begingroup$ Do you need a combinatorial proof, or is an algebraic proof fine? $\endgroup$
    – Calvin Lin
    Feb 25 '14 at 12:21
  • $\begingroup$ @CalvinLin I don't need a proof per se, this isn't homework, algebraic proofs are fine. But combinatorial proofs are more satisfying imo. $\endgroup$
    – Guy
    Feb 25 '14 at 12:22

...and here is a combinatorial proof. If you want to construct an $n$-letter word from an alphabet containing $2n$ letters, the number of words is

  • $(2n)!/n!$ if repeated letters are not allowed;

  • $(2n)^n$ if repeated letters are allowed.

Clearly the first is less than or equal to the second, $$\frac{(2n)!}{n!}\le (2n)^n\ ,$$ and this gives your desired inequality after some simple algebra.

  • $\begingroup$ ...simple algebra being diving by $n!$ on both sides, elegant! I am going to wait for a while before accepting though, just to see if someone comes up with something better, people always surprise. $\endgroup$
    – Guy
    Feb 25 '14 at 12:33

(combinatorial proof of RHS)

Multiply the RHS by $\frac{n^n}{n^n}$:

$$ \frac{(2n)!} { n! n!} \leq \frac{2^n n^n} { n!}.$$

The LHS is the number of ways of picking $n$ objects out from $2n$ objects.

For the RHS, consider a string of $n$ objects, each of which are picked out from $2n$ objects, possibly with repetition. Then, there is a bijection between "pick $n$ objects out from $2n$ objects", and the $n!$ ways that these objects can be ordered into a string of $n$ objects. Hence, $LHS \leq RHS$.

It is clear that when we are able to pick an object twice, then we will have string inequality. Hence, for $n\geq 2$, $LHS < RHS$.

(algebraic proof of RHS)

Multiplying by $\frac{n^n}{n^n}$, we want to show that

$$ \frac{(2n)!} { n! n!} \leq \frac{2^n n^n} { n!}.$$

This is obvious, since $$ \frac{ (2n) ! } { n!} = \prod_{i=1}^n (n+i) \leq (2n)^n = 2^nn^n.$$

It is obvious that if $n\geq 2$, then the inequality is weak. Hence, for $n \geq 2$, $LHS < RHS$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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