# Is this induction procedure correct? ($2^n<n!$)

I am rather new to mathematical induction. Specially inequalities, as seen here How to use mathematical induction with inequalities?. Thanks to that question, I've been able to solve some of the form $1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \leq \frac{n}{2} + 1$.

Now, I was presented this, for $n \ge 4$:

$$2^n<n!$$

I tried to do it with similar logic as the one suggested there. This is what I did:

Prove it for $n = 4$: $$2^4 = 16$$ $$4! = 1\cdot2\cdot3\cdot4 = 24$$ $$16 < 24$$ Assume the following: $$2^n<n!$$ We want to prove the following for $n+1$: $$2^{n+1}<(n+1)!$$ This is how I proved it:

• So first we take $2^{n+1}$ which is equivalent to $2^n\cdot2$
• By our assumption, we know that $2^n\cdot2 < n!\cdot2$
• This is because I just multiplied by $2$ on both sides.
• Then we'll be finished if we can show that $n! \cdot 2 < (n+1)!$
• Which is equivalent to saying $n!\cdot2<n!\cdot(n+1)$
• Since both sides have $n!$, I can cancel them out
• Now I have $2<(n+1)!$
• This is clearly true, since $n \ge 4$

Even though the procedure seems to be right, I wonder:

• In the last step, was it ok to conclude with $2<(n+1)!$? Was there not anything else I could have done to make the proof more "careful"?
• Is this whole procedure valid at all? I ask because, well, I don't really know if it would be accepted in a test.
• Are there any points I could improve? Anything I could have missed? This is kind of the first time I try to do these.
-
I think your proof is fine, if a bit long-winded. But with experience, you'll learn what bits to shorten without losing rigour. –  Harald Hanche-Olsen Nov 27 '12 at 9:51
You should say 2^{n+1}\lt 2\cdot n!$. But because$2\lt $n+1$, it follows that $2\cdot n!\lt (n+1)!$. Unfortunately, you are still writing proofs "backwards" in a logically incorrect way. –  André Nicolas Nov 27 '12 at 9:59
@André: It seems a bit harsh to call this a "logically incorrect way". It's OK as long as "Since both sides have $n!$, I can cancel them out" is interpreted as "dividing through by $n!$ leads to an equivalent inequality". It's true that the reverse order would be clearer, and doing things in this order is incorrect if the implications used only go in one direction, but that's not the case here so the proof is still OK, if suboptimally structured. –  joriki Nov 27 '12 at 10:04
@Omega, your proof is correct..."almost", since as Andre apparently meant, there's some lack of logical rigour in your last lines. You must show that the implications there are double, i.e.: $$n!\cdot 2<(n+1)!\Longleftrightarrow 2<\frac{(n+1)!}{n!}=n+1$$ and then noting the last inequality is trivially true as we're working with $\,n\geq 4\,$... Also, don't right "equivalent" when it should be "equal", as in "$\,2^{n+1}\,$ is "equivalent"(should be "equal"!) to $\,2^n\cdot 2$ –  DonAntonio Nov 27 '12 at 10:47
@joriki: A bit harsh, perhaps, but other posts by the OP had some worse instances that were pointed out. Since the actual understanding of the problem is good, it is worthwhile to vaccinate the OP against $A\to B\to C\to 0=0$, therefore $A$. –  André Nicolas Nov 27 '12 at 16:47

Yes, the procedure is correct. If you want to write this more like the sort of mathematical proof that would be found in a textbook, you might want to make some tweaks.

For example, the base case could be re-written as follows:

When $n = 4$, we have $2^4 = 16 < 24 = 4!$

Next, the inductive hypothesis and the subsequent manipulations:

Suppose that for $n \geq 4$ we have $2^n < n!$

Thus, $2^{n+1} < 2 \cdot n! < (n+1)!$, where the first inequality follows by multiplying both sides of the inequality in our IH by $2$, and the second follows by observing that $2 < n+1$ when $n \geq 4$.

Therefore, by the Principle of Mathematical Induction, $2^n < n!$ for all integers $n \geq 4$. Q.E.D.

Note: I am not making a judgment about whether your write-up or the one I have included here is "better." I'm only observing that the language and format differ, particularly with regard to proofs that are written in paragraph form (typical of math papers) rather than with a sequence of bullet-points (which is what you had).

-