2
$\begingroup$

I'd like to prove $n^2 \in o(n!)$ for $n \in \mathbb{N}$. More specifically, this means $$ \exists c \in \mathbb{R}, n_0 \in \mathbb{N} \forall n \geq n_0: n^2 < c \cdot n! $$

My ideas

I've initially considered a proof by induction, using $c=1$ and $n_0 = 4$. In the induction step (i.e. considering $n > n_0$, I find that $$ n^2 + 2n + 1 < n! + 2n + 1 $$ However, I still have to conclusively show that $n! + 2n + 1 < (n+1) \cdot n!$. This fact seems rather obvious, however I am unable to express it.

Is there a better way to go about this task?

$\endgroup$
4
  • $\begingroup$ If you directly consider the inequality $n^2 / c\cdot n!$ and divide both sides by $n^2$, then you get $1 < \frac{c(n-1)}{n} (n-2)!$ (assuming $n$ is sufficiently large). So, it suffices to show that $\frac{c(n-1)}{n}$ is greater than some constant, say 1, for every sufficiently large $n$. Do you see any idea from here? $\endgroup$
    – Kanu Kim
    Commented Oct 21, 2019 at 18:47
  • 2
    $\begingroup$ $n!+2n+1<n!+2n!+n! = 4n!<(n+1)\cdot n!$ when $(n+1)> 4$. And $n!>n$ is just $n>2$ $\endgroup$
    – kingW3
    Commented Oct 21, 2019 at 19:01
  • $\begingroup$ @Kanu Given that $\frac{c(n-1)}{n} = c - \frac{c}{n}$, it's clear that the corresponding sequences converge towards $c$, so if we choose $c > 1$, there must be an $n_0$ such that $\frac{c(n-1)}{n} > 1 \forall n > n_0$. And since obviously $1 < (n-2)!$ for $n > 2$, that should be enough to prove the inequality. Correct? $\endgroup$
    – StckXchnge-nub12
    Commented Oct 21, 2019 at 19:02
  • $\begingroup$ Yes, you're correct. Moreover, you can find an explicit $n_0$ for the inequality $c(n-1)/n > 1$; because $$ \frac{n-1}n > \frac 1 c \iff \frac 1 n < 1 - \frac 1 c = \frac {c-1}c \iff n > \frac c{c-1},$$ $n_0 = \lceil \frac{c}{c-1}\rceil $ makes the inequality hold for any $n\ge n_0$. Or just take $n_0=2$ and use $\frac{n-1}n \ge \frac 2 3$ to take some $c> 3/2$. $\endgroup$
    – Kanu Kim
    Commented Oct 21, 2019 at 19:12

2 Answers 2

Reset to default
0
$\begingroup$

As Kanu said in the comment, this can be done directly. But to follow your approach, $n! + 2n + 1 < (n+1) \cdot n!$ is equivalent to $2n+1 < n \cdot n!$. Now since clearly $n! > 3$ and $2n+1 < 3n$ for $n \geq 3$, the latter inequality follows: $$2n+1 < 3n < n! \cdot n.$$

$\endgroup$
0
$\begingroup$

By limit definition we have

$$n^2 \in o(n!) \iff \lim_{n\to \infty} \frac{n^2}{n!}\to 0$$

and since $n!>n^3$ for $n\ge 6$ we have that $$\frac{n^2}{n!}\le \frac1n \to 0$$

$\endgroup$

You must log in to answer this question.

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