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?
Best Answer
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*} $$