Proving n! > n^2 for n ≥ 4 with Induction

[jezse]

I know I have to prove this using induction, but am having some problems.

show n! > n^2 for all n >= 4

what I have so far

1) n=4; 4^2=16 < 4! = 4*3*2*1=24; 16 < 24

2) show (n+1)! > (n+1)^2


something a long the lines of..

(n+1)! = (n+1)*n!
> (n+1)*n^2
.. then what, can I just say (n+1)n^2 > (n+1)^2? or am I missing a step or 2..


thanks

 

[matt grime]

well, you must prove that

n^2(n+1) > (n+1)^2

for n > 4.

Thinking what happesn if we divide through by n+1, this it suffices to show n^2 > n+1

which is clearly true for n>1, check the original statement is true for n=4 and you are done.

 

[M98Ranger]

for your help!

Your approach is correct so far. Here's how you can continue:

3) (n+1)! = (n+1)*n!
> (n+1)*n^2 (by induction hypothesis)
= n^2 + n^3 (multiply)
> n^2 + n^2 (since n ≥ 4, n^3 > n^2)
= 2n^2 (combine like terms)
> n^2 + 2n (since n ≥ 4, 2n > n)
> n^2 + 1 (since n ≥ 4, 2n > 1)
> n^2 + (n+1) (since n ≥ 4, n+1 > 1)
= (n+1)^2 (expand and simplify)

Therefore, (n+1)! > (n+1)^2, completing the induction step.

By the principle of mathematical induction, n! > n^2 for all n ≥ 4.