Show that $\binom{2n}{n}\geq2^n$ for all $n\in\mathbb{N}_0$.

Question

Show that $\binom{2n}{n}\geq2^n$ for all $n\in\mathbb{N}_0$.

---

First, observe that $\binom{2n}{n} = \frac{(2n)!}{n!(2n-n)!}=\frac{(2n)!}{(n!)^2}=\frac{1\cdot 2\cdot 3\cdot...\cdot 2n-1\cdot 2n}{(n!)^2}=\frac{(1\cdot 3\cdot 5\cdot ... \cdot 2n-1)\cdot(2\cdot 4\cdot 6\cdot ... \cdot 2n)}{(n!)^2}=\frac{(1\cdot 3\cdot 5\cdot ... \cdot 2n-1)\cdot(2\cdot 1\cdot 2\cdot 2\cdot 2\cdot 3\cdot ... \cdot 2n)}{(n!)^2}=\frac{(1\cdot 3\cdot 5\cdot ... \cdot 2n-1)\cdot 2^n\cdot n!}{(n!)^2}=2^n\cdot\frac{1\cdot 3\cdot 5\cdot ... \cdot 2n-1}{(n!)}.$

For $n=0$ we have: $\frac{(2*0)!}{(0!)^2}=1=2^0.$

Now to our inductive step $n+1$: \begin{align*} & \frac{(2(n+1))!}{((n+1)!)^2}\geq2^{n+1}\\ \Leftrightarrow\,\, & \frac{(2n+2)!}{((n+1)!)^2}\geq2^{n+1}\\ \Leftrightarrow\,\, & \frac{1\cdot 2\cdot 3\cdot...\cdot 2n+1 \cdot 2n+2}{((n+1)!)^2}\geq2^{n+1}\\ \Leftrightarrow\,\, & \frac{(1\cdot 3\cdot 5\cdot ... \cdot 2n+1)\cdot(2\cdot 4\cdot 6\cdot ... \cdot 2n \cdot 2n+2)}{((n+1)!)^2}\geq2^{n+1}\\ \Leftrightarrow\,\, & \frac{(1\cdot 3\cdot 5\cdot ... \cdot 2n+1)\cdot 2^{n+1} \cdot (n+1)!}{((n+1)!)^2}\geq2^{n+1}\\ \Leftrightarrow\,\, & 2^{n+1}\cdot \frac{(1\cdot 3\cdot 5\cdot ... \cdot 2n+1)}{((n+1)!)}\geq2^{n+1}\\ \end{align*}

---

Is this proof correct/sufficient? Was induction even needed here or should I have argued instead that $\frac{1\cdot 3\cdot 5\cdot ... \cdot 2n-1}{(n!)}>0$? Is this step necessary even for the induction?

Answer 1

Another approach: the expression equals

$$\frac{2n(2n-1)\cdots (2n-(n-1))}{n!}=\frac{2n}{n}\frac{2n-1}{n-1}\frac{2n-2}{n-2}\cdots \frac{2n-(n-1)}{n-(n-1)}.$$

Since $2n-k \ge 2(n-k),$ $ k=0,\dots ,n-1,$ each fraction on the right is at least $2.$ Since there are $n$ fractions, we have the result.

Answer 2

This proof does not look complete. You reduced the question to a more manageable one, but you didn't actually prove that the more manageable one is true. It also never makes use of the inductive hypothesis - as it stands, it's basically a direct proof, not a inductive proof.

I'd also recommend rewriting it because it's somewhat unclear as it is - it moves backwards, starting at its conclusion and simplifying from there. This is logically fine - as you have the statements are equivalent - but it can be clarified by writing prose to indicate that you are reducing the problem to a simpler one. You could also be more precise by saying that you are actually just rewriting the left hand side - that is, we are dealing with a series of equal expressions more than with a series of equivalent statements.

---

Letting my $n$ be your $n+1$ to keep the expressions clean, you've shown that $${2n\choose n}=\frac{(2n)!}{(n!)^2}=2^n\cdot \frac{1\cdot 3 \cdot \ldots \cdot (2n-1)}{1\cdot 2 \cdot \ldots \cdot n}.$$ You are trying to claim that this is at least $2^n$. So, what you need to show is that $\frac{1\cdot 3 \cdot \ldots (2n-1)}{1\cdot 2\cdot \ldots \cdot n}$ is at least $1$. An easy way to see that is to break it apart as $\frac{1}{1}\cdot \frac{3}1\cdot \ldots \cdot \frac{2n-1}n$, where every factor is at least $1$, so so is their product. (Or, more directly, you can use the method in @zhw's answer)

You can also argue this inductively by noting that if $\frac{1\cdot \ldots \cdot (2n-1)}{1\cdot 2 \cdot\ldots \cdot n}\geq 1$, then multiplying both sides by $\frac{2n+1}{n+1}\geq 1$ we get $\frac{1\cdot 3 \cdot \ldots\cdot (2n+1)}{1\cdot 2 \cdot\ldots\cdot (n+1)}\geq \frac{2n}{n+1}\geq 1$. Or, going that route, you can also note that $$\frac{(2n+2)!}{((n+1)!)^2}=\frac{(2n+1)\cdot (2n+2)}{(n+1)^2}\cdot \frac{(2n)!}{(n!)^2} =2\cdot \frac{2n+1}{n+1}\cdot \frac{(2n)!}{(n!)^2}\geq 2\cdot {2n \choose n}$$ from which point the inductive proof is easy enough construct, since your expression is at least doubling at each step

Answer 3

From this identity and inequality, the proof becomes obvious $$ \binom{2n}n = \sum_{k=0}^n {\binom nk}^2\ge \sum_{k=0}^n \binom nk. $$

This identity is by comparison of coefficients of $x^n$ in $$ (1+x)^{2n}=(1+x)^n (1+x)^n. $$

Answer 4

Another approach: Consider a line of $2n$ people, and we want to put them in two teams of $n$ people say $\color{red}{red}$ and $\color{blue}{blue}$ then what if you restrict to the first $n$ people that you put in the line, they can be whatever because regardless of the choice at most you picked $n$ of them in one team and so $2^n\leq \binom{2n}{n}.$

Example: Say $n = 2,$ then the possibilities are: $$\underbrace{\color{red}{**}}_{\text{first 2}}\color{blue}{**},\hspace{1mm} \underbrace{\color{red}{*}\color{blue}{*}}_{\text{first 2}}\color{blue}{*}\color{red}{*},\hspace{1mm}\underbrace{\color{red}{*}\color{blue}{*}}_{\text{first 2}}\color{red}{*}\color{blue}{*},\hspace{1mm}\underbrace{\color{blue}{*}\color{red}{*}}_{\text{first 2}}\color{red}{*}\color{blue}{*},\hspace{1mm}\underbrace{\color{blue}{*}\color{red}{*}}_{\text{first 2}}\color{blue}{*}\color{red}{*},\hspace{1mm}\underbrace{\color{blue}{*}\color{blue}{*}}_{\text{first 2}}\color{red}{*}\color{red}{*},\hspace{1mm}.$$ Notice that restricting to the first $2$ we get all possibilities of red and blue.