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$
1
  • 2
    $\begingroup$ Note, this isn't true for $n=1$:$$2^1=\binom21$$ But for $n>1$ it is true. $\endgroup$ Jul 21, 2013 at 16:53

7 Answers 7

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

$\endgroup$
3
  • 1
    $\begingroup$ Excellent answer! $\endgroup$
    – Gerard
    Jul 21, 2013 at 16:10
  • $\begingroup$ this is pretty smart, I saw very similar arguments used in a proof of Bertrand's Postulate... $\endgroup$ Jul 21, 2013 at 23:32
  • $\begingroup$ @Coffee_Table Is there any way to find the ratio between those two terms, i.e. $\frac{\binom{2n}{n}}{2^{2n}}$ $\endgroup$ Oct 26, 2020 at 4:08
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}}$$

$\endgroup$
3
  • $\begingroup$ Wow, nice. I love your style. $\endgroup$
    – nullpotent
    Jul 21, 2013 at 16:47
  • $\begingroup$ @Thomas Andrews Is there any way to find the ratio between those two terms, i.e. $\frac{\binom{2n}{n}}{2^{2n}}$ $\endgroup$ Oct 26, 2020 at 4:10
  • 1
    $\begingroup$ @PrakharNagpal Probably not, no. It is approximately $\frac1{\sqrt{n\pi}}$ $\endgroup$ Oct 26, 2020 at 4:23
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$$

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

$\endgroup$
3
  • 2
    $\begingroup$ And for the second part, consider $(1+1)^{2n}$. $\endgroup$ Jul 21, 2013 at 16:07
  • $\begingroup$ @DanielFischer, ya too obvious:). Anyway thanks for mentioning $\endgroup$ Jul 21, 2013 at 16:08
  • $\begingroup$ @labbhattacharjee Is there any way to find the ratio between those two terms, i.e. $\frac{\binom{2n}{n}}{2^{2n}}$ $\endgroup$ Oct 26, 2020 at 4:09
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 ;-)

$\endgroup$
1
  • 2
    $\begingroup$ The perfect answer. $\endgroup$
    – zyx
    Jul 22, 2013 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}$.

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

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