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