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?

  • 1
    Hint: $3^{k+1}=3^k\cdot 3.$2012-10-09
  • 0
    So I multiply the RHS by 3?2012-10-09
  • 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.2012-10-09
  • 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