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

Base Case:

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

Induction:

Assume $P(k) = 3^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?

  • 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 2012-10-09

2 Answers 2

1

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

0

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.