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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
5  
Hint: it isn't true. – Thomas Andrews Oct 29 '12 at 19:13

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|cite|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

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|cite|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

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|cite|improve this answer
    
Thanks for the help – Jason Byrne Oct 29 '12 at 20:01

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.