# Induction problem 1

Here's the claim again, for reference:

Claim: For all positive integers $$n \geq 2$$, $$2^n n! < (2n)!$$

### Solution

Proof by induction on n.

Base: When n=2, $$2^n n! = 4 \cdot 2 = 8$$ and $$(2n)! = 4! = 24$$, so $$2^n n! < (2n)!$$ is true for this value of n.

Induction Hypothesis: Suppose that $$2^n n! < (2n)!$$ is true for $$n = 2, 3, \ldots, k$$ where k is an integer $$\geq 2$$.

Rest of induction step: We need to show that $$2^{k+1} (k+1)! < (2(k+1))!$$

Notice that $$(2(k+1))! = (2k+2)!$$.

By the inductive hypothesis, we know that $$2^{k}k! < (2k)!$$. Therefore \begin{align*} (2k+2)! & = (2k+2) (2k+1) (2k)! \\ &= (2k+1) \left[2 (k+1)\right] (2k)! \\ & > (2k+1) \left[2 (k+1)\right] 2^k k! \\ & = (2k+1) 2^{k+1} (k+1)! \\ \end{align*}

Since $$k \geq 2$$, $$(2k+1) \geq 5 > 1$$. So

$$(2k+1) 2^{k+1} (k+1)! > 2^{k+1} (k+1)!$$.

So therefore we have

$$(2k+2)!> (2k+1) 2^{k+1} (k+1)! > 2^{k+1} (k+1)!$$

So $$2^{k+1} (k+1)! < (2k+2)!$$, which is what we needed to show.