# How to prove $2^{2n}\leq n!$ for all $n\geq 9$ with induction?

So, first step, base of induction is correct. When we take $n=9$, we get

$262114\leq 362880$.

So, we assume that

$2^{2n}\leq n!$ for all $n\geq 9$ is correct and we want to prove that

$2^{2n+2}\leq (n+1)!$ is correct for all $n\geq 9$.

In induction part, we take $2^{2n}\leq n!$ and multiply it by 4, so on the left side we get $2^{2n+2}$, what is left on the right side is $4n!$.

Now we need to prove that $2^{2n+2}\leq (n+1)!$ is correct.

Can we do that by checking if $(n+1)! \geq 4n!$, because we know for sure that $4n! \geq 2^{2n+2}$ ?

• "we assume that ___ is correct for all $n\geq 9$" No, you assume that ___ is correct for all numbers up to some $n$. – user223391 Oct 13 '16 at 16:10

By induction, you take $n=9$ and get $262114\leq 362880$.
Now, assume $2^{2n}\leq n!$ is correct for all numbers up to some $n>9$.
$$(n+1)!=(n+1)\cdot n!\geq (n+1)\cdot 2^{2n}\geq 4\cdot 2^{2n}=2^{2(n+1)},\;\forall n>9,$$
where the induction hypothesis has been used in the first "$\;\geq$". Thus,
$$2^{2n}\leq n!,\;\forall n\geq 9.$$
• Isn't it easier if we know that $4n!≥2^{2n+2}$ is correct, just to check if $(n+1)!≥4n!$ ? That inequality is valid for $n≥3$, and knowing that our $n$ is $≥9$, so is that kind of proven? That $(n+1)!≥2^{2n+2}$ is right? – Tars Nolan Oct 13 '16 at 16:37