I am trying to prove $n^3<n!$ for all integers $n\geq 6.$ It would be trivial to do this by induction if $(n+1)^3<(n+1)n^3$ holds. I looked this up, and I found this is true for integers $n\geq 3.$ However, does anybody know of any more insightful method of proof for either statement, ie. not induction? Thank you.
-
$\begingroup$ Are you familiar with calculus? Based on that I could give you an interesting and useful answer :) $\endgroup$– Sidharth GhoshalJun 8, 2014 at 5:10
-
$\begingroup$ Are you looking for something like $(n^3 = n \cdot n^2) < (n! = n \cdot (n-1)(n-2)\cdots(n-5)\cdots1)$? (Restricted to $n\geq6$, showing $n^2 < (n-1)(n-2)\cdots(n-5)$ should be fairly trivial.) $\endgroup$– PocketsJun 8, 2014 at 5:20
4 Answers
HINT:
If $\displaystyle k!>k^3, (k+1)!=(k+1)\cdot k!>(k+1)k^3$
It is sufficient to show that $\displaystyle (k+1)k^3>(k+1)^3\iff k^3>(k+1)^2$ which holds true for $k\ge3$
For $n=5,5!=120, 5^3=125\implies 5!\not\ge 5^3$
Now establish the base case for $n=6$
Proof by Inception:
By Frogeyedpeas
Consider the difference between two consecutive elements of the sequence $n^3$ and $n!$
That is:
$$n^3 - (n-1)^3 = 3n^2 - 3n + 1$$
and
$$n! - (n-1)! = (n-1)(n-1)! !$$
Consider now the consecutive differences of our differences. That is:
$$3n^2 - 3n + 1 - 3(n-1)^2 + 3(n-1) - 1 =6n - 6$$
$$(n-1)(n-1)! - (n-2)(n-2)! = (n-1)^2(n-2)! - (n-2)(n-2)! = (n^2 - 3n + 3)(n-2)! $$
Now consider the consecutive difference of our consecutive difference of our differences. that is:
$$6n -6 - 6(n-1) +6 = 6$$
$$(n^2 - 3n + 3)(n-2)! - ((n-1)^2 - 3(n-1) + 3)(n-3)! = Something \ that \ isn't \ constant$$
This last line is key:
Something that isn't constant > 6 for some k (And all n greater than that). Meaning:
The consecutive difference of our consecutive difference of our differences for n! is greater than the same for $n^3$ for all numbers larger than k.
And if for that k (or an k2 larger) the consecutive difference of our difference for n! is greater than the same for $n^3$ then the consecutive difference of our difference for n! is always greater than the same for $n^3$ for number greater than or equal to that particularl k2.
But if thats case and another k3 greater than our previous k2 is found such that consecutive difference between n! is greater than the consecutive difference between $n^3$ for all numbers n greater than that k3. Then we can conclude the consecutive difference for n! is always greater than the consecutive difference for all numbers n greater than k3.
But if thats the case and anotehr k4 is found greater than k3 such that $n!$ is greater than $n^3$ then that means for all numbers greater than k4 $n!$ is greater than $n^3$
Start the bottom case with k = 3 and work you way up to complete the proof :)
-
$\begingroup$ I like how your proof starts "By frogeyedpeas", a little bit as if it were a piece of art: "The Raven - By Edgar Allen Poe". :=) "Proof by Inception" is also a nice one ... :=) $\endgroup$ Jun 8, 2014 at 5:56
You can avoid induction if you allow division in the following way:
Let $n\geq 6$. Notice that \begin{align*} n!&=n(n-1)(n-2)(n-3)(n-4)(n-5)!\\ &\geq n(n-1)(n-2)3\cdot 2\cdot 1\tag{1}\\&=6n(n-1)(n-2). \end{align*}
Now, we can make the following evaluation: \begin{align*} \dfrac{n^3}{n(n-1)(n-2)}=\dfrac{n}{n-1}\dfrac{n}{n-2}.\tag{2} \end{align*} It's easily proven that, for a given $k$, the function $f_k:n\mapsto\dfrac{n}{n-k}$ (defined for $n>k$) is decreasing. In particular, since $n\geq 6$, then \begin{align*} \dfrac{n}{n-1}=f_1(n)\leq f_1(6)=\dfrac{6}{5}\quad\text{and}\quad\dfrac{n}{n-2}=f_2(n)\leq f_2(6)=\dfrac{6}{4},\tag{3} \end{align*} so, using (2) and (3), we obtain $$\dfrac{n^3}{n(n-1)(n-2)}\leq\dfrac{6}{5}\dfrac{6}{4}=\dfrac{36}{20}<6,\tag{4}$$ hence, by (4) and (1), $$n^3\leq6n(n-1)(n-2)\leq n!$$
Base case: $n = 6$
$$ 6! = 720 \\ 6^3 = 213 $$
Inductive Step: Assume: $n!\geq n^3$. This implies that $n! = n^3 + \alpha$ where $\alpha \geq 0$. This gives $(n + 1)! = (n+1)n! = (n +1)(n^3 + \alpha) = n^4 + n^3 + \alpha n + \alpha$. Then we look at $(n + 1)^3 = n^3 + 3n^2 + 3n + 1$. Right away, we know that $n^4$ will dominate $n^3$ and thus be greater (at least eventually). Here is what we have:
$$ n^4 + n^3 + \alpha n + \alpha \stackrel{?}{\geq} n^3 + 3n^2 + 3n + 1 \\ n^4 \stackrel{?}{\geq} 3n^2 + (3 - \alpha)n + (1 - \alpha) $$
The right side is biggest when $\alpha$ is the most negative. Therefore the maximum value for the right side occurs when $\alpha = 0$ (since this is the minimum value of $\alpha$). This gives:
$$ n^4 \stackrel{?}{\geq} 3n^2 + 3n + 1 $$
If this holds then it holds for all possible values of $\alpha \geq 0$ (assuming $n \geq 6$). There are a couple of ways to go from here. I think the most straightforward way is to use calculus. We can look at the following function:
$$ f(x) = x^4 - 3x^2 - 3x - 1 \\ f'(x) = 4x^3 - 6x - 3 $$
You can use a root finder to find the zeros. It will show that the only real zero occurs at $x \approx 1.4237$. Therefore if this function is positive at $x = 6$ ($n = 6$) then it's positive for all values $x \geq 6$)--and you can test that to show it is true.