2
$\begingroup$

I need to find the set of positive integers such that $n! \geq n^3$, and then prove my answer is true using cases and induction on $n$.

There is a lemma that I will need to prove and use for this proof.

The lemma is :

$n^2+2n+1\leq n^3$ when $n\geq$ ??


Here is my outline of the proof:

Claim: The set of all positive integers that satisfy $n! \geq n^3$ is $\{n\in \mathbb{Z} | n=1$ or $n\geq 6\}$

Let us prove the following Lemma : $n^2+2n+1\leq n^3$ when $n\geq 3$

Let $n \in \mathbb{Z}^+$

$n^2+2n+1 \leq n^2+2n+n$ when $n\geq 1$

$n^2+2n+1 \leq n^2+n^2+n$ when $n\geq 2$

$n^2+2n+1 \leq n^2+n^2+n^2$ when $n \geq 3$

$n^2+2n+1 \leq 3n^2 \leq n^3$ when $n \geq 3$

Thus, we have $n^2+2n+1\leq n^3$ when $n\geq 3$

This lemma is important because when we use induction on $n$, we want to eventually show that

$n!\geq n^3$ implies $(n+1)!\geq(n+1)^3$

In order to show this, we need to multiply both sides of $n!\geq n^3$ by $(n+1)$

Our result would be $(n+1)n!\geq (n+1)n^3$

Now we need to show that $(n+1)n^3\geq (n+1)(n+1)^2$ so that we can get to our goal.

Using our lemma, we have proved that $(n+1)^2\leq n^3$ when $n\geq 3$, so we know that we can use induction on our original claim so long as $n\geq 3$.

So using our lemma, we can assume that if $(n+1)n!\geq (n+1)n^3$ is true, then $(n+1)!\geq(n+1)^3$ is also true, so long as $n\geq 3$

Now we can use cases and induction to prove our claim.

Case 1: $n=1$, $1!\geq 1^3$

Case 2: $n=2$, $2!\ngeq 2^3$

Case 3: $n=3$, $3!\ngeq 3^3$

Case 4: $n=4$, $4!\ngeq 4^3$

Case 5: $n=5$, $5!\ngeq 5^3$

Case 6: $n=6$, $6!\geq 6^3$

Let us use induction on $n$ to prove that $n! \geq n^3$ for all positive integers greater than or equal to $6$.

Base case: $n=6$. $6!\geq 6^3$, so we have proved the base case.

Inductive step: Suppose we have $(\star)$ $n!\geq n^3$. We want to show that $(n+1)!\geq(n+1)^3$. Let us multiply both sides of $(\star)$ by $(n+1)$.

We have $(n+1)n!\geq (n+1)n^3$ This can be rewritten as $(n+1)!\geq (n+1)n^3$

Using our lemma, we can assume that if $(n+1)!\geq (n+1)n^3$ is true, then $(n+1)!\geq(n+1)^3$ is also true, so long as $n\geq 3$.

This completes the induction, and we have proved the claim.


My questions are:

1) Have I completely proved the lemma?

2) Are there any errors in the proof?

3) How can I improve this proof?

$\endgroup$

2 Answers 2

2
$\begingroup$

I think your proof is correct, but using a lemma and then doing induction is overkill for this question! In general, I would also strongly advise against trying to use both sides of an equation simultaneously in an inductive proof. It's not impossible to do, but it's one of the main sources of error when people are doing inductive proofs - you don't want to assume what you are trying to prove. You have avoided errors in this case, but I wouldn't recommend it as a general strategy.

For this question, you want to show $n!\ge n^3, \forall n\ge 6$. You have correctly shown the base case, so we will assume that $k!\ge k^3$ for some $k\in \mathbb{Z}$, $k\ge 6$. Then for $n=k+1$:

$$ \begin{split} LHS=(k+1)!=(k+1)\cdot k!&\ge (k+1)\cdot k^3 \\ &\ge (k+1)\cdot (k+1)^2 \text{, since } k\ge 6 \\ &=(k+1)^3 \\ &=RHS \end{split} $$

And the result follows by induction. The only thing you may want to show using induction again is that $k^3\ge (k+1)^2$ for $k\ge 3$ (which is what your lemma shows - I would use induction to prove the lemma rather than your approach) but this is not a hard proof and the result is probably clear. In any case, having shown this, the above is really all you need - you don't need to multiply both sides of the inductive hypothesis etc.

$\endgroup$
2
  • $\begingroup$ I agree that proving the lemma over-complicates this basic proof, but it is a requirement for this assignment, which is secretly the most difficult task I have ran into. I don't know how to fully prove the lemma, because it appears obvious to me that it is true. $\endgroup$
    – klorzan
    Nov 11, 2015 at 22:39
  • 1
    $\begingroup$ You can prove the lemma using induction. The base case is $n=3$. Then assuming $k^3\ge (k+1)^2$ we have for $n=k+1$: $$ \begin{split} LHS=(k+1)^3=k^3+3k^2+3k+1&\ge (k+1)^2+3k^2+3k+1 \\ &=4k^2+5k+1 \\ &\ge 4k^2+4k+1 \\ &\ge k^2+4k+4 \\ &=(k+2)^2 \\ &=RHS \end{split} $$ $\endgroup$ Nov 11, 2015 at 23:31
1
$\begingroup$

Let $f(x) = x^3 - (x + 1)^2$

$f'(x) = 3x^2 - 2x + 2$. $f'(x) = 0$ when $x = \frac{2 \pm \sqrt(4 - 24}{6}$ so $f'(x)$ never equals $0$ for any real x. So $f(x)$ has no extrema and thus only one real root.

$ f(2) = -1; f(3) = 18$ so $f(x)$ has only one real root is between 2 and 3. So $f(n) > 0$ iff $n^3 > (n+1)^2$ iff $n \ge 3$.

=====

D'oh! The obvious easiest way:

Let $ m = n+1;$ $\frac{n^3}{n^2 + 2n + 1} = \frac{(m - 1)^3}{m^2}$

$= \frac{m^3 - 3m^2 + 3m -1}{m^2} = m - 3 + (\frac 3 m - \frac 1 {m^2})> m -3$

so $\frac{n^3}{n^2 + 2n + 1} > n -2$

so $\frac{n^3}{n^2 + 2n + 1} > 1 \iff n^3 > n^2 + 2n + 1$ when $n \ge 3$.

$\endgroup$

You must log in to answer this question.

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