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.

  • 5
    $\begingroup$ Hint: it isn't true. $\endgroup$ – Thomas Andrews Oct 29 '12 at 19:13
  • $\begingroup$ Not proposing to close, just linking to the node of this network of duplicates. $\endgroup$ – Lee David Chung Lin Feb 6 at 18:51

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

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

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.

| cite | improve this answer | |
  • 2
    $\begingroup$ The statement does not hold for $n=2$ or $n=3$ so you can't start with that base case. $\endgroup$ – chris Oct 29 '12 at 19:07
  • $\begingroup$ @chris and Andreas: yeah that was definitly crap :-) fixed it. $\endgroup$ – born Oct 29 '12 at 19:20
  • $\begingroup$ Much appreciated, thank you $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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