1

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

Brevan Ellefsen
  • 14,793
Tars Nolan
  • 387
  • "we assume that ___ is correct for all $n\geq 9$" No, you assume that ___ is correct for all numbers up to some $n$. –  Oct 13 '16 at 16:10

1 Answers1

1

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

Edu
  • 1,888
  • 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
  • 1
    @TarsNolan I don't feel that's easier at all :) The proof of the original inequality is direct. What you suggest imply to prove a new inequality... But if you feel better that way, go ahead! – Edu Oct 13 '16 at 16:54