# $n!>n^m$ for $n\ge?$

I want to find a natural number $N$ in terms of $m(\in\mathbb N)$, such that

$$n!>n^m \;, \forall n \ge N$$

Also, (how) can we prove that $n!-n^m$ is an increasing sequence for $n\ge N$?

I was just solving the problem that $n!>n^2$ for $n\ge 4$. I am trying to generalize the statement, but I don't know how to proceed.

• Have you tried induction?
– rbm
Apr 24, 2013 at 13:18
• Induction on what? I think I should use the fact that $log( n!)> n$, for $n \ge 4$. Apr 24, 2013 at 13:28

Note the following:

1. $n\ge n$.
2. $(n-1)(n-2) \ge n$, for $n$ sufficiently large
3. $(n-3)(n-4) \ge n$, for $n$ sufficiently large
4. $(n-5)(n-6) \ge n$, for $n$ sufficiently large

If we do this for $m$ steps (and provided that $n$ is sufficiently large for all of them), we may multiply the LHS to get $n(n-1)(n-2)\ldots, (n-2m+2)$, which (provided $n>2m-2$) will be smaller than $n!$, while the RHS will be $n^m$. All of the inequalities are implied by the last one, which is $(n-2m+3)(n-2m+2)\ge n$. This rearranges to $n^2+(-4m+4)n+(2m-3)(2m-2)\ge 0$. Take the larger root of this quadratic, and $2m-2$ from above, and the larger of these will serve for $M$.

• For $m=7$, then your $n=10$, $10!=3628800$ and $10^7=10000000$, $n! < n^m$? Apr 24, 2013 at 13:57
• @Inceptio: thanks for pointing out the typo. I had $m+2$ instead of $2m-2$. With the correction, $M=12$, not $10$. Apr 24, 2013 at 14:02
• Make sense now. But N.S' answer is more convincing. Is there a possibility to use induction on your last inequality, for $n>2m-2$? Apr 24, 2013 at 14:05

For the first question: Note that

$k \cdot (n-k)>n \Leftrightarrow kn-n>k^2 \Leftrightarrow n> \frac{k^2}{k-1}=k+1+\frac{1}{k-1}$

Thus, for all $k \neq 2$ and $n> k+2$ we have $k \cdot (n-k)>n$.

Setting this for $k=2, k=3, ..., k=m$ we get that if $n>2(m+2)$ we have

$$n! =1 \cdot [2 \cdot (n-2)]\cdot [3 \cdot (n-3)]...\cdot [m \cdot (n-m)] .. \cdot n >n^m$$

For the second question, I don't think the sequence is increasing, it is just eventually increasing. To prove this, just observe that if $n> 2^m$ and $n>N$ then $n! \cdot n > 2^mn^m$ thus

$$(n+1)!-n!=n! \cdot n > (2n)^m > (n+1)^m > (n+1)^m-n^m$$

Hint:

You have this : $n! <n^n$

$n! <n^{n-1}$ , is this true$?$ Do you know that $n|(n-1)!$ if $n$ is composite$?$

You can get rid of the factorial by taking logs: $$\log(n!) = \sum_{j=1}^n \log(j).$$ Then you can estimate this sum using the integral since $\log$ is monotone: $$\sum_{j=1}^n \log(j) \ge \int_1^n \log(x) dx = n\log(n) -n +1.$$

Then $$n! \ge n^m \Leftrightarrow \log(n!) \ge m \log(n),$$ and to prove this it is sufficient to prove that $$n\log(n) -n +1 \ge m \log(n) \Leftrightarrow (n-m)\log(n) \ge n-1.$$ Assume $n \ge m+1$. Then the last inequality reduces to $$\log(n) \ge \frac{n-1}{n-m}.$$ But $$\max_{n\ge m+1} \frac{n-1}{n-m} = m,$$ so the previous inequality will hold if $$\log(n) \ge m \Leftrightarrow n \ge e^m.$$ Note that $n \ge e^m$ implies $n \ge m+1$ since $e^x \ge x+1$ for $x \ge 0$. So, a sufficient condition for $n! \ge n^m$ is $n \ge e^m.$

This is not so great, so instead we can try restricting to, say $n \ge 2m$. Then $$\max_{n\ge 2m} \frac{n-1}{n-m} = \frac{m-1}{m},$$ so a sufficient condition is then $$\log(n) \ge \frac{m-1}{m} \Leftrightarrow n \ge \exp\left( \frac{m-1}{m}\right).$$ So, a better sufficient condition is $$n \ge \max\left\{2m, \exp\left( \frac{m-1}{m}\right) \right\}.$$ This is more in line with the other solutions since $\frac{m}{m-1}$ remains bounded as $m \to \infty$.

Try to use induction twice. Firstly for $m$, and then for $n$. The plan will look like this:

1. Base case. We need to proove that $n!>n^2, \forall n>N$ and find $N$. It's quite easy.
2. Inductive step. Let's assume that we know $N$ for $m$. We need to find $N'$ in terms of $N$, such that $n!>n^{m+1},\forall n>N'$. Find $N'$ and proove that $(N')!>(N')^{m+1}$ (basis). Then proove that $(n+1)!>(n+1)^{m+1}$ holds if $n!>n^{m+1}$ is true (hint: you also know that $(n+1)!>(n+1)^m$ from first induction (it's true, because $n>N'$ and $N'>N$, hence $n>N$), so you can show that $(n+1)^m<n^{m+1}$). Finally, divide $(n+1)!>(n+1)^{m+1}$ by $n+1$. It's easy to show that $n!>(n+1)^m$, since $n^{m+1}>(n+1)^m$.