# Math induction ($n^2 \leq n!$) help please

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.

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

-
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$.

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

-
Thanks for the help – Jason Byrne Oct 29 '12 at 20:01