Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm having trouble with a math induction problem. I've been doing other proofs (summations of the integers etc) but I just can't seem to get my head around this.

Q. Prove using induction that $n^2 \leq n!$

So, assume that $P(k)$ is true: $k^2 \leq k!$

Prove that $P(k+1)$ is true: $(k+1)^2 \leq (k+1)!$

I know that $(k+1)! = (k+1)k!$ so: $(k+1)^2 \leq (k+1)k!$ but where can I go from here?

Any help would be much appreciated.

share|improve this question
    
For some basic information about writing math at this site see e.g. here, here, here and here. –  Julian Kuelshammer Oct 29 '12 at 19:03
    
Since you are new to this site, please consider reading this: How to ask a homework question?. In particular, you should use homework tag if your question comes from a homework. I wrote this comment because the question sounds homework-like. –  Julian Kuelshammer Oct 29 '12 at 19:03
    
Hi, thanks for the advice. Sorry about that. –  Jason Byrne Oct 29 '12 at 19:07
5  
Hint: it isn't true. –  Thomas Andrews Oct 29 '12 at 19:13
add comment

3 Answers

The statement you want to prove is for all $n\in\mathbb{N}$ it holds that $n^2\leq n!$ (you called this $P(n)$. So lets first prove $P(4)$ i.e. $4^2\leq 4!$ but since $16\leq 24$ this is clear. So lets assume $P(n)$ and prove $P(n+1)$.

First note that for $n\geq 2$ it holds that $$ 0\leq (n-1)^2+(n-2)=n^2-2n+1+n-2=n^2-n-1 $$ which is equivalent to $n+1\leq n^2$ which gives

$$ (n+1)^2=(n+1)(n+1)\leq (n+1)n^2 $$

by induction hypothesis (i.e. $P(n)$) the term $n^2$ in the last expression is smaller or equal $n!$ so we can continue: $$ (n+1)n^2\leq (n+1)n! = (n+1)! $$ which is the statement we wanted to prove.

My answer is very extensive and explicit. But maybe, you now get a better understanding of what you have to do in general, when you want to prove something by induction.

share|improve this answer
2  
The statement does not hold for $n=2$ or $n=3$ so you can't start with that base case. –  chris Oct 29 '12 at 19:07
    
@chris and Andreas: yeah that was definitly crap :-) fixed it. –  born Oct 29 '12 at 19:20
    
Much appreciated, thank you –  Jason Byrne Oct 29 '12 at 20:02
add comment

Suppose $k^{2}\leq k!$. Then $(k+1)!=(k+1)k!\geq (k+1)k^{2}\geq (k+1)^{2}$, whenever $k\geq 2$.

share|improve this answer
    
What is $x$?$\phantom{x}$ –  Julian Kuelshammer Oct 29 '12 at 19:09
    
Sorry, that was a typo - should have been $k$. –  user123123 Oct 29 '12 at 19:09
    
Hey thanks, that's very clear now –  Jason Byrne Oct 29 '12 at 20:02
add comment

One way to prove this is to strengthen your induction hypothesis slightly: assume $k^2+k\leq k!$ instead of $k^2\leq k!$. You have a base case for this starting with $k=4$, where $k^2+k=20$ and $k!=24$.

Then we want to show $(k+1)^2+k+1<(k+1)!$. Divide both sides by $k+1$ to see this holds just if $k+2<k!$. But we supposed $k^2+k<k!$ and $k\geq 4$, so this holds. Then we've shown for all $n$ that $n^2+n\leq n!$, which implies the conclusion.

share|improve this answer
    
Thanks for the help –  Jason Byrne Oct 29 '12 at 20:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.