Prove that $2^n < \binom{2n}{n} < 2^{2n}$

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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$

Answer 5

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 ;-)

Answer 6

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

Answer 7

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