12
$\begingroup$

Prove that $2^n < \binom{2n}{n} < 2^{2n}$. This is proven easily enough by splitting it up into two parts and then proving each part by induction.

First part: $2^n < \binom{2n}{n}$. The base $n = 1$ is trivial. Assume inductively that some $k$ satisfies our statement. The inductive step can be proved as follows.

$2^k < \binom{2k}{k} \implies 2^{k+1} < 2\binom{2k}{k} = \frac{2(2k)!}{k!k!} = \frac{2(2k)!(k + 1)}{k!k!(k + 1)} = \frac{2(2k)!(k+2)}{(k+1)!k!}<\frac{(2k)!(2k+2)(2k+1)}{(k+1)!k!(k+1)} = \binom{2(k+1)}{k+1}$

Second part: $2^{2n} > \binom{2n}{n}$. Again, the base is trivial. We can assume that for some $k$ our statement is satisfied and prove that inductive step as follows:

$2^{2k} > \binom{2k}{k} \implies 2^{2k + 2} > 2^2\binom{2k}{k} = \frac{2\cdot2(2k)!}{k!k!} = \frac{2\cdot2(2k)!(k+1)(k+1)}{k!k!(k+1)(k+1)} = \frac{(2k)!(2k+2)(2k+2)}{(k+1)!(k+1)!} > \frac{(2k)!(2k+1)(2k+2)}{(k+1)!(k+1)!} = \binom{2(k+1)}{k+1}$

Is there a non-inductive derivation for the inequality?

$\endgroup$
  • 2
    $\begingroup$ Note, this isn't true for $n=1$:$$2^1=\binom21$$ But for $n>1$ it is true. $\endgroup$ – Thomas Andrews Jul 21 '13 at 16:53
28
$\begingroup$

To see that $\binom{2n}{n} < 2^{2n}$, apply the binomial theorem $$2^{2n} = (1+1)^{2n} = \sum_{k=0}^{2n} \binom{2n}{k} > \binom{2n}{n}.$$

To see that $2^n < \binom{2n}{n}$, write it as a product $$\binom{2n}{n} = \frac{2n}{n} \cdot \frac{2n-1}{n-1} \cdot ... \cdot \frac{n+1}{1},$$ where each factor is $\ge 2$, and for $n > 1$, some factors are strictly greater than $2$. The claim is not true if $n=1$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Excellent answer! $\endgroup$ – Gerard Jul 21 '13 at 16:10
  • $\begingroup$ this is pretty smart, I saw very similar arguments used in a proof of Bertrand's Postulate... $\endgroup$ – Coffee_Table Jul 21 '13 at 23:32
15
$\begingroup$

As I noted in a comment, this is only true for $n>1$. For $n=1$, you have $2^1=\binom 21$.

A purely combinatorial approach.

Let $S$ be a set with $n$ elements. Let $T=S\times\{1,2\}$. Let $R=\{X\subset T:\left|X\right|=n\}$. Then you need to show that:

$$\left|\mathcal P(S)\right|< \left|R\right| < \left|\mathcal P(T)\right|$$

Where $\mathcal P(Y)$ is the power set of $Y$.

Now, $R\subsetneq \mathcal P(T)$, so you really only need to prove the left side.

Define $f:\mathcal P(S)\to R$ for $X\subseteq S$ by:

$$f(X)=\{(x,1):x\in X\}\cup \{(x,2):x\in S\setminus X\}$$

Then $f$ is $1-1$, so all you really need is that it isn't onto. But it is easy to come up with elements of $R$ not in the image of $f$ when $n>1$.

Another way to get the left side inequality is:

$$\binom{2n}{n}=\sum_{k=0}^n\binom{n}{k}^2 >\sum_{k=0}^n\binom{n}{k}=2^n$$

The equation used here for $\binom {2n}{n}$ is fairly well-know and easily proved, and the second step is only true for $n>1$, again.

These are very rough bounds for $\binom{2n}{n}$. We actually have that $$\binom{2n}{n}\sim \frac{2^{2n}}{\sqrt{n\pi}}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Wow, nice. I love your style. $\endgroup$ – nullpotent Jul 21 '13 at 16:47
8
$\begingroup$

For the second part note that $$2^{2n}=(1+1)^{2n}=1+\binom {2n}1 +\dots + \binom {2n}n+\dots\gt \binom{2n}n$$

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

For the first part, we don't need induction as $$\binom {2n}n=\prod_{0\le r\le n-1}\frac{2n-r}{n-r}=2\prod_{1\le r\le n-1}\frac{2n-r}{n-r}>2\cdot 2^{n-1}$$ and $2n-r>2(n-r)$ for $r>0$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ And for the second part, consider $(1+1)^{2n}$. $\endgroup$ – Daniel Fischer Jul 21 '13 at 16:07
  • $\begingroup$ @DanielFischer, ya too obvious:). Anyway thanks for mentioning $\endgroup$ – lab bhattacharjee Jul 21 '13 at 16:08
4
$\begingroup$

Combinatorial argument:

Take $n$ pairs of people, that is $2n$ people total, and then you can pick:

  • one person from each pair in $2^n$ ways,
  • any $n$ individuals in $\binom{2n}{n}$ ways,
  • any subset of those people in $2^{2n}$ ways.

I hope this helps ;-)

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ The perfect answer. $\endgroup$ – zyx Jul 22 '13 at 4:11
1
$\begingroup$

Let $A$ be the set of all binary words containing $n$ bits, $B$ be the set of all binary words containing $2n$ bits, exactly $n$ of which are $1's$, $C$ be the set of all binary words containing $2n$ bits.

Then as $B$ is a proper subset of $C$ we have $\binom{2n}{n} <2^{2n}$.

We define a function $E : B \to A$ by $E(x)=$erase the last $n$ digits of $x$. This function is onto but not one-to-one, thus $B$ has more elements than $A$. This proves $\binom{2n}{n} >2^{n}$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

The central binomial coefficient is largest implies a lower bound of $(2^{2n})/(2n+1)$. This exceeds $2^n$ for $n>1$ and is almost its square for large $n$.

There are more subsets than subsets of a fixed cardinality implies an upper bound of $2^{2n}$.

| cite | improve this answer | |
$\endgroup$

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.