1
$\begingroup$

I am trying to prove the inequality in the title for $n\geq 4$; however, I am stuck on the induction step! Any help would be appreciated.

For $n\ge 4$, prove that $n! > n^2$.

Base Case: $n=4$, LHS $4! = 24$, RHS = $4^2 = 16$

$24>16$ : True

Induction Hypothesis: Assume True for $n=k$.

$k! > k^2$

Induction Step: Should be True for $n=k+1$

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

$(k+1) . (k)! > (k^2 + 2k + 1)$

However, here is where I get stuck.

$\endgroup$
  • $\begingroup$ $k! > k^2 \Rightarrow (k+1)k! > (k+1)k^2$. Now, can you show that for $k \geq 4$ we have $$(k+1)k^2 > (k+1)^2$$ That is $$k^2 > k + 1$$ $\endgroup$ – Simon S Apr 27 '15 at 12:15
  • 1
    $\begingroup$ @GeorgeS wrong question... $\endgroup$ – Clement C. Apr 27 '15 at 12:16
  • $\begingroup$ Yes, I just realised. Sorry that was an accident. $\endgroup$ – user230715 Apr 27 '15 at 12:16
  • $\begingroup$ @ClementC. - Can I ask how you got to $(k+1)k^2$? $\endgroup$ – RandomMath Apr 27 '15 at 12:21
  • 1
    $\begingroup$ You're ultimately trying to show that $(k+1)! > (k+1)^2$, so think of working towards this, not from it. It should be your last line. $\endgroup$ – Théophile Apr 27 '15 at 12:24
3
$\begingroup$

Hint:

$$(k+1)!> (k+1)^2$$ can be rewritten as

$$(k+1)\cdot (k!) > (k+1)\cdot(k+1)$$

$\endgroup$
1
$\begingroup$

For the induction step, here is the key part: \begin{align} (k+1)! &= (k+1)\cdot k!\tag{by definition}\\[0.5em] &> (k+1)\cdot k^2\tag{by the inductive hypothesis}\\[0.5em] &= k^3+k^2\tag{expand}\\[0.5em] &> k^2+2k+1\tag{since $k\geq 4$}\\[0.5em] &= (k+1)^2. \end{align} The main problem is realizing that you can deduce that $k^3+k^2>k^2+2k+1$ from the fact that $k\geq 4$.

$\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.