Showing that $n! > n^2$ for $n\geq4$ by induction

Question

My attempt:

Prove $ n! > n^2 $ for $ n \geq 4 $

Base Case: $P(4) = 24 > 16$

Inductive Hypothesis $P(k) : k! > k^2 $

$P(k+1) : (k+1)! > (k+1)^2 $

$ (k + 1)! - (k+1)^2 > 0 $

$ (k+1)(k! - k - 1) > 0 $

First divide the $(k+1)$ on both sides to remove it. Then replacing $k!$ with $k^2$ gives this equation because $k!$ is greater than $k^2$

$k^2 - k - 1 < k! - k - 1$

$k^2 < k!$

$ k! > k^2 $ which is my inductive hypothesis. $\blacksquare$

---

Does this look correct?

Answer 1

You should prove from $P(k)$ to $P(k+1)$ rather than the opposite direction. You have most of the stuff right, you just have to read it from bottom up.

For the inequality, $$k^2-k+1 < k!-k+1$$

In order to reach the line above it. We just have to show that $k^2-k+1 \geq 0.$ This is true as the discriminant is negative and this quadratic function is convex. After which, you multiply everything by $k+1$ of which you are sure it is positive.

Answer 2

Not quite; you are factoring $(k+1)! - (k+1)^2 = (k+1)(k!-k+1)$ when it should be $(k+1)(k!-k-1)$.

Then you should be trying to prove that $k!-k+1 > 0$ (actually it's $k!-k-1$, but let's go with what you posted) but instead of doing that you are showing that, because $k! > k^2$, that it's greater than $k^2-k+1$. This is actually obviously greater than $0$, but you don't state it, so it seems like you aren't proving the right thing.

There are ways to salvage your proof; for example you can say that $k!-k-1 > k^2-k-1$ (by the inductive hypothesis) and then that this is greater than $0$ in any number of ways.

Answer 3

I think you would benefit a great deal from reading the post on how to write a clear induction proof. Concerning your proof here, there are more problems than simple stylistic ones (e.g., how you characterize the inductive hypothesis, how you start the induction step, etc.). I would suggest writing up your proof as follows:

Problem: Prove for all $n\geq4$ that $n!>n^2$ holds.

Proof. For any integer $n\geq4$, let $S(n)$ denote the statement $$ S(n) : n!>n^2. $$ Base step ($n=4$): Note that $S(4)$ says that $4!=24>16=4^2$, which is true.

Inductive step ($S(k)\to S(k+1)$): Fix some $k\geq4$ and assume that $S(k)$ holds where $$ S(k) : k!>k^2. $$ To be proved is that $S(k+1)$ follows where $$ S(k+1) : (k+1)!>(k+1)^2. $$ Beginning with the left-hand side of $S(k+1)$, \begin{align} (k+1)!&= (k+1)k!\tag{by definition of factorial}\\[1em] &> (k+1)k^2\tag{by $S(k)$, the IH}\\[1em] &> k^2+2k+1\tag{since $k^3>2k+1$}\\[1em] &= (k+1)^2,\tag{factor} \end{align} we end up at the right-hand side of $S(k+1)$, completing the inductive step.

Thus, by mathematical induction, the statement $S(n)$ is true for all $n\geq4$. $\blacksquare$

---

Note that $k^3>2k+1$ since $k\geq4$. This inequality is fairly obvious, but you could also prove it by induction or another proof technique if entirely necessary.

Answer 4

$$n!=(n-1)!n\ge n^2\iff(n-1)!\ge n$$ Since $$(n-2)(n-1)=n^2-3n+2\ge n\iff n^2-4n+2\ge 0\iff (n-2)^2-2\ge 0$$ and it is true for $n\ge 4$ it follows that $n!\ge n^2$.

Actually we have, for $n\ge 4$ $$(n-2)(n-1)n\ge n^2$$

Answer 5

Let $n!>n^2$ (i. h.)

We need to show that $(n+1)!>(n+1)^2, \forall n \geq 4$

$$ (n+1)!=(n+1)n! \stackrel{\mathrm{(i. h.)}}{>} (n+1)n^2 > (n+1)(n+1)=(n+1)^2.$$

Note that when $n \geq 4$, the inequality $n^2 > n+1$, is true.