6
$\begingroup$

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.

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

5 Answers 5

3
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ For $m=7$, then your $n=10$, $10!=3628800$ and $10^7=10000000$, $n! < n^m$? $\endgroup$
    – Inceptio
    Apr 24, 2013 at 13:57
  • 1
    $\begingroup$ @Inceptio: thanks for pointing out the typo. I had $m+2$ instead of $2m-2$. With the correction, $M=12$, not $10$. $\endgroup$
    – vadim123
    Apr 24, 2013 at 14:02
  • $\begingroup$ 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$? $\endgroup$
    – Inceptio
    Apr 24, 2013 at 14:05
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .