22
$\begingroup$

I'd like to show $n!>n^{10} $ for large enough n ( namely $ n \geq 15 $).

By induction, I do not know how to proceed at this step:

$$ (n+1)\cdot n!>(n+1)^{10} $$

As I can't see how to simplify $(n+1)^{10} $.

This seems like such a trivial thing (and it probably is), yet I can't do it. Isn't there an easier way to show this?

(P.S. I need to refrain from the use of derivatives, integrals etc., I suppose, then you could work something out with the slope of the respective functions)

$\endgroup$
32
$\begingroup$

You need to work in the fact that $n! \gt n^{10}$ as that is the heart of the induction. So for $n \gt 15$ $$\text {Base case } 15!-15^{10}=731023977375 \gt 0\\ \text {Assume }n! \gt n^{10}\\(n+1)! =(n+1)n!\gt (n+1)n^{10}=(n+1)^{10}\frac {n^{10}}{(n+1)^9}$$ Now we need to argue that the last fraction on the right is greater than $1$ and we are home.

$$\frac {n^{10}}{(n+1)^9} = n\left(1-\frac 1{n+1}\right)^9\gt n\left(1-\frac 9{n+1}\right)\gt 15\cdot \frac 7{16}\gt 1$$

$\endgroup$
  • $\begingroup$ Could you please elaborate, how you got to $ (n+1)n^{10} $ ? Should it not be $ (n+1)^{10} $ ? $\endgroup$ – Jonathan Dec 1 '16 at 22:51
  • 1
    $\begingroup$ I just multiplied the first inequality by $n+1$ on both sides. That gave me $(n+1)!$ on the left like I wanted. Now I need to show that the right is greater than $(n+1)^{10}$, which is what I do with the rest. $\endgroup$ – Ross Millikan Dec 1 '16 at 22:56
  • $\begingroup$ I see now, I didn't read your post properly, I apologise $\endgroup$ – Jonathan Dec 1 '16 at 22:56
  • $\begingroup$ So, $(\frac{7}{16})^{9} > \frac{7}{16}$? $\endgroup$ – Atomosk Dec 2 '16 at 6:12
  • $\begingroup$ @Atomosk: No, but $(\frac {15}{16})^9 \gt \frac 7{16}$. That is what I claimed. $\endgroup$ – Ross Millikan Dec 2 '16 at 6:15
12
$\begingroup$

Since it's needed, here's the base case of $15! > 15^{10}$ without (much) calculation:

$15! = 2^{7}\cdot 2^{3}\cdot{2}\cdot 3^{5}\cdot{3}\cdot 5^{3}\cdot 7^2\cdot 11\cdot 13 \\ \phantom{15!} = 2^{11}\cdot 3^{6}\cdot 5^{3}\cdot 7^2\cdot 11\cdot 13 \\ \phantom{15!} = 16^2\cdot 15^3\cdot 18 \cdot (14\cdot 21)\cdot (22\cdot13) \\ \phantom{15!} > 15^2\cdot 15^3 \cdot 15\cdot 15^2\cdot 15^2 = 15^{10}$

$\endgroup$
5
$\begingroup$

Remember to show the base case, namely that $15! > 15^{10}$. After that is verified, make the induction hypothesis (IH):

IH: $m! > m^{10}$

Show: $(m+1)! > (m+1)^{10}$ using IH.

As you've done so far, what we need to show is: \begin{align} (m+1)! = (m+1)m! > (m+1)^{10} \end{align}

Also note that $(m+1)^{10} = (m+1)(m+1)^9$. So, cancelling the ''$m+1$'' terms, we need to show $m! > (m+1)^9$ using the fact that $m! > m^{10}$.

Finally, notice that if we can show that $m^{10} > (m+1)^9$ then we are done. Equivalently, we just need to show that $\frac{m^{10}}{(m+1)^9} > 1$. I'll leave this up to you.

$\endgroup$
4
$\begingroup$

This is just a fun observation: $$ (n!)^2= \prod_{i=1}^n i(n+1-i)>n^n $$ so at least for $n\geq 20$ we have $\sqrt{(n!)^2}=n!>n^{n/2}\geq n^{10}$. Given this, we would only need to account for the cases $n=15,...,19$. But this is not an inductive approach, of course.

$\endgroup$
  • 1
    $\begingroup$ Your 2k agrees with mine as a nice elementary bound. But your proof is simpler. $\endgroup$ – marty cohen Dec 1 '16 at 23:54
  • $\begingroup$ @martycohen: Yes, the $2k$ was what I had in mind too :o) $\endgroup$ – String Dec 1 '16 at 23:59
3
$\begingroup$

Let $n\geq 15$ such that

$$n!\geq n^{10}$$

we want that

$$(n+1)!=(n+1)n!\geq(n+1)n^{10}$$

$$\geq (n+1)^{10}$$

which means that we want to prove

$$n\geq (1+\frac 1n)^9$$

or

$$n^{\frac{n}{9}}\geq (1+\frac 1n)^n$$

and this is true for large enough $n$ cause the sequence on the left goes to $+\infty$, while the sequence on the right goes to $e$.

$\endgroup$
3
$\begingroup$

The handiest inequalities for $n!$ are $(n/e)^n < n! < (n/e)^{n+1}$.

These are easily proved by induction from $(1+1/n)^n < e < (1+1/n)^{n+1}$, and these have been proved here a number of times.

From $n! > (n/e)^n$, to show that $n! > n^k$ for large enough $n$, it is enough to show that $(n/e)^n > n^k$ for large enough $n$.

$(n/e)^n > n^k \iff n^{n-k} > e^n \iff n^{1-k/n} > e $.

If you are not worrying about getting the best possible bound, take $n > 2k$. Then $n^{1-k/n} > n^{1/2} > (2k)^{1/2} \gt e $ for $2k > e^2$.

If $2k < e^2$, choose $n > \max(2k, e^2)$.

Therefore, if $n > \max(2k, e^2)$ then $n! > n^k$.

$\endgroup$
3
$\begingroup$

There's no need for induction or anything beyond elementary arithmetic. For $n\geq 15$, \begin{align*} n!&\geq n(n-1)\cdots(n-9)\times 5\cdot 4\cdot 3\cdot 2 \\ &= 120n(n-1)\cdots(n-9)\\ &> n \cdot \frac{15}{14}(n-1)\cdot \frac{15}{13}(n-2)\cdots \frac{15}{6}(n-9)\\ &\geq n^{10}\,, \end{align*} where the strict inequality is because the third line is approximately $53n(n-1)\cdots(n-9)$ and the final inequality is because, for all $i$ and $n$ with $1\leq i<15\leq n$, $$\frac{15}{15-i}(n-i) = n + \frac{(n-15)i}{15-i} \geq n\,.$$

$\endgroup$
2
$\begingroup$

Replacing $n$ by $n+1$, the LHS is multiplied by $n+1$ while the RHS is multiplied by $\left(1+\frac1n\right)^{10}$, which is bounded (by $1024$ for $n\ge1$, but by $2$ for $n\ge15$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.