Prove that $2^n < \binom{2n}{n} < 2^{2n}$ 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?
 A: For the second part note that $$2^{2n}=(1+1)^{2n}=1+\binom {2n}1 +\dots + \binom {2n}n+\dots\gt \binom{2n}n$$
A: 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$
A: 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 ;-)
A: 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$.
A: 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}}$$
A: 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}$.
A: 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}$.
