# Prove the $3^n < n!$ for all $n > 6$

I'm trying to use induction to prove this. I'm sure it's a simple proof, but I can't seem to get over the first few steps. Any help?

Allow $P(n)=3^n<n!$

Base Case:

$P(7) = 3^7<7! \rightarrow$ True.

Induction:

Assume $P(k) = 3^k<k!$

Now we must prove $P(k+1)$. Here's where I'm lost. If I'm adding a +1 to the exponent on the LHS, where would I add it to the factorial on the RHS?

-
Hint: $3^{k+1}=3^k\cdot 3.$ – Andrew Oct 9 '12 at 4:19
So I multiply the RHS by 3? – Bob John Oct 9 '12 at 4:23
You are multiplying the left by $3$. You are multiplying the right by $n+1$. If the right side was ahead, and $n\ge 2$, it stays ahead. – André Nicolas Oct 9 '12 at 4:23
Take the ratio: $$\varphi(k)=\frac{3^k}{k!}\\ \varphi(k+1)=\frac{3^{k+1}}{(k+1)!}=\varphi(k)\frac{3}{k+1}$$ Obviously $$\frac{3}{k+1}<1 \ \forall \ k>2$$ – Alex Oct 9 '12 at 4:27

The key to induction proofs is finding a way to work your induction hypothesis into the "$k+1$" case.

We want to show $3^{k+1} < (k+1)!$. Since you know $3^k < k!$, we need to keep an eye out for a factor of $3^k$. Let's just start with the lefthand side of the "$k+1$" case and see what we can do. \begin{align*} 3^{k+1} &= 3 \cdot 3^k\\ &< 3 \cdot k! && \text{(inductive hypothesis)}\\ &< (k+1) \cdot k! && \text{(since k > 2)}\\ &= (k+1)! \end{align*}

-

I'm not sure I understand your question. The rest of the comments/answers have interpreted it in one way, but my answer to the question:

Here's where I'm lost. If I'm adding a +1 to the exponent on the LHS, where would I add it to the factorial on the RHS?

Is that the RHS will look like $(k+1)!$. I'm not sure why you might have thought otherwise? Did you think it might be $k! + 1$? Remember that you are inducting on $k$. So wherever you saw a $n$ you'd replace it with $k+1$.

If this was indeed the confusion you had it would be really really worth it to make sure you understand induction better (and maybe even refresh yourself on the definition of a function?). I can write up a loose description of induction that might help you if you want it.

-