# Proof using the Principle of Mathematical Induction

Use induction to prove that $n! > 3n$ for $n\ge4$.

I have done the base case and got both sides being equal to $24>12$ for $n=4$. However, when doing the inductive step I can't seem to find the right form to match the expression on the right hand side.

So far I have:

Need to show: $(n+1)!>3(n+1)$.

When doing the inductive step:

$(n+1)! = (n+1)n!$

we know that $n!$ is larger than $3n$, then

$(n+1)n! >(n+1)3n$.

Here is where I don't know what to do next, could anyone shed some insight on how to continue after this part? Thanks.

-
You don't want to tag this as set theory, number theory perhaps. –  James Jun 29 '13 at 20:08
@James This problem comes from a chapter on set theory, that's why I tagged it as that. –  Kururugi Suzaku Jun 29 '13 at 20:10
You need to prove an inequality. You cannot assume that $n!=3n$. Note that this is not even true for $n=4$, where you claim that we have equality. –  Andrés Caicedo Jun 29 '13 at 20:19
Again, you are trying to prove an inequality. We do not "know that $n!$ is equal to $3n$, and therefore $(n+1)!=(n+1)3n$", as you say. It is simply not true. –  Andrés Caicedo Jun 29 '13 at 20:26
Another edit, to incorporate the relevant changes you missed. –  Andrés Caicedo Jun 29 '13 at 20:41

In your proof you could do the following: $$n!\geq 3n$$ $$(n+1)!\geq 3n(n+1)$$

Now note that $n\geq 1$, therefore $3n(n+1)\geq 3(n+1)$.....

-
I made a mistake when I wrote the first equation, it should have been $n!$ $>$ 3n –  Kururugi Suzaku Jun 29 '13 at 20:35
@KururugiSuzaku But the idea is clear , I think you can edit it accordingly –  Amr Jun 29 '13 at 20:41

Assume $n!>3n$, then $n!\ge3$ as $3n>3$ for all $n\in\mathbb{N_{\geq4}}$.

This follows

\begin{align} &n!>3\\&(n+1)n!>3(n+1)\\&(n+1)!>3(n+1) \end{align}

-
How do you get $(n+1)!>3(n+1)$ from the line above? If this is not what you meant when you said "Assume $n!>3n$ then $(n+1)!>3(n+1)$", then please write what you meant. –  Andrés Caicedo Jun 29 '13 at 20:46
Hmmm... I should've had reversed the order of the whole argument. –  Maazul Jun 29 '13 at 20:51