0
$\begingroup$

It's a very classic problem for students learning induction to prove the following statement:

"Prove $n! > 2^n$ for all $n \geq 4$"

I went on to prove a related, still quite simple example:

"Prove $n! > n^2 2^n$ for all $n \geq 8$."

This isn't very different than the first proof, but a little bit more involved, I suppose.

My question is: Is there a general way to prove a statement such as:

"Prove $n! > P(n) x^n$ for all $n \geq \alpha$," where $P(n)$ is a general polynomial in terms of $n, x \geq 1$ and $\alpha$ is some threshold for the base case to be true. In the first example, $\alpha = 4$, and in the second example, $\alpha = 8$.

How might we prove such a statement to be true by induction? There seems to be lots of variables going on, which may make the proof more complicated.

Thanks.

$\endgroup$
  • $\begingroup$ It's easily proven without induction, since $\ln n!\sim n\ln n$. $\endgroup$ – J.G. Oct 17 at 21:16
  • $\begingroup$ I hadn't thought of that! This helps a lot. Thanks. $\endgroup$ – Cjw123 Oct 17 at 21:34
0
$\begingroup$

Since every polynomial is subexponential, we need only check the case $P(n)\equiv1$, and can assume without loss of generality $x\in\Bbb N$ with $x\ge2$. The inductive step is trivial if $\alpha\ge x-1$. By considering the last $\lceil n/2\rceil$ factors for $n\ge2x^2$, $n!>(n/2)^{n/2}\ge x^n$, so we can take $\alpha=2x^2$ in the base step.

| cite | improve this answer | |
$\endgroup$

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.