Question

Proof of n! > n^2 by induction

Answer 1

The problem asks me to prove that n! is greater than n^2 for n >= 4. I'm not quite sure what to do.

Can anyone help push me in the right direction?

Answer 2

Well, for induction, you usually end up proving the n=1 (or in this case n=4) case first. You've got that done.

Then you need to identify your indictive hypothesis:
e.g.
n!>2n

and
n>4


In class the proof might look something like this:
(n+1)!=n!(n+1)

from the inductive hypothesis we have
n!(n+1)>2n(n+1)

since
n>1
we have
2n(n+1)>2n(2)

and
2n(2)=2n+1

Now, we can string it all togther to get the inequality:
(n+1)!=n!(n+1)>2n(n+1)>2n(2)=2n+1

(n+1)!>2n+1


In general, it's worth trying to figure out wether it 'safe'
to multiply
n!>2n

by
n+1>2

while preserving the inequality.
Which is really what I wanted to do in my head. As soon as you are sure it is legitemate, you're done.

Answer 3

\[n! = \prod_{k=1}^{n}k\]
thus:
\[\prod_{k=1}^{n}k > n^2\]
you can use that to expand the product and just show implicitly that n!>n^2

Answer 4

Any idea how to do it by induction?

Answer 5

Start with:
1.
n≥4

2.
n!>2n

and try to get to
(n+1)!>2n+1

Then you need to identify your indictive hypothesis:
e.g.
n!>2n

and
n>4


In class the proof might look something like this:
(n+1)!=n!(n+1)

from the inductive hypothesis we have
n!(n+1)>2n(n+1)

since
n>1
we have
2n(n+1)>2n(2)

and
2n(2)=2n+1

Now, we can string it all togther to get the inequality:
(n+1)!=n!(n+1)>2n(n+1)>2n(2)=2n+1

(n+1)!>2n+1


In general, it's worth trying to figure out wether it 'safe'
to multiply
n!>2n

by
n+1>2

while preserving the inequality.
Which is really what I wanted to do in my head. As soon as you are sure it is legitemate, you're done.

Answer 6

Would it be sufficient to say

\[n! > n^2\]
\[n!*(n+1) > n^2*(n+1)>(n+1)^2\]
so
\[(n+1)! > (n+1)^2\]

Answer 7

I would add...
\[(n+1)!\]\[=n!(n+1)>n^2(n+1)>(n^2-1)(n+1)\]\[=(n-1)(n+1)(n+1)=(n-1)(n+1)^2>(n+1)^2\]

Answer 8

Thanks :D