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

  • $\begingroup$ "we assume that ___ is correct for all $n\geq 9$" No, you assume that ___ is correct for all numbers up to some $n$. $\endgroup$ – 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.$$

  • $\begingroup$ 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? $\endgroup$ – Tars Nolan Oct 13 '16 at 16:37
  • 1
    $\begingroup$ @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! $\endgroup$ – Edu Oct 13 '16 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.