0

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.

1 Answers1

1

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.

J.G.
  • 115,835