1
$\begingroup$

How does one prove by induction that

$n! > n^2$

for $n \geq 4$

  • 0
    This is not true when n=12012-12-16
  • 4
    How does one prove anything by induction? Can you say which part of the general method is problematic in this case?2012-12-16
  • 0
    Should there be some restriction on the value of $n$, because the statement is false for $n = 1, 2, 3$?2012-12-16
  • 3
    The OP probably intended for $n \geq 4$.2012-12-16
  • 1
    @cardinal yes, of course!2012-12-16
  • 1
    I edited it sorry it deserved a -1....2012-12-16
  • 0
    Related question: [How to prove $a^n < n!$ for all $n$ sufficiently large, and $n! \leq n^n$ for all $n$, by induction?](http://math.stackexchange.com/questions/6581/how-to-prove-an-n-for-all-n-sufficiently-large-and-n-leq-nn-for-al)2012-12-16
  • 0
    See also: [Prove by induction that $n^2$n^2\le n!$](http://math.stackexchange.com/questions/764808/hint-in-proving-that-n2-le-n) – 2015-02-09

2 Answers 2

3

To prove that this inequality holds for $n \geq 4$, first we verify the base case, which is trivial, as $24 >16$.

Now assume for some $k$ that $k! > k^2$. Then $(k+1)! > (k+1)k^2 = k^3+k^2 > (k+1)^2$. We can verify the right hand inequality, as this implies that $k^2 > k+1 \implies k^2-k-1>0$, which is clearly true for $k \geq 4$; the inductive step has thus been proven and we're done.

  • 0
    did you mean $k^3-k-1>0$?2012-12-16
  • 0
    I meant $k^2-k-1>0$; I got that expression by dividing the right hand inequality by $k+1$.2012-12-16
  • 0
    ahh sorry my bad2012-12-16
  • 0
    Thanks, I didn't see the other post answered when searching2012-12-16
3

Hint:

If $n! > n^2$ holds, can you show that $$ (n+1)! = n! (n+1) > (n+1)^2 = n^2 +2 n+1?$$