# A generalized version of a classic induction proof

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.

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

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.