Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
2  
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
2  
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

2 Answers 2

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*} $$

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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