1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Hint: $3^{k+1}=3^k\cdot 3.$ $\endgroup$ – Andrew Oct 9 '12 at 4:19
  • $\begingroup$ So I multiply the RHS by 3? $\endgroup$ – Bob John Oct 9 '12 at 4:23
  • 2
    $\begingroup$ 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. $\endgroup$ – André Nicolas Oct 9 '12 at 4:23
  • 2
    $\begingroup$ 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 $$ $\endgroup$ – Alex Oct 9 '12 at 4:27
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.