So I have to prove that $3^n$ is greater than or equal to $3n$ using induction. The base case is a not a problem, but I can't seem to figure out where to go for $(n-1)$. I've tried saying: $$3^n=3\cdot3^{n-1}>3\cdot3(n-1)$$ $$3\cdot3(n-1)=9n-9$$
I'm pretty sure my end goal is $3n$, but I'm not really sure how to get there. Any suggestions would be much appreciated.
$\endgroup$ 72 Answers
$\begingroup$I will show that we may assume that the inequality holds for some $k$ and use that to show that it holds for $k+1$.
Use the base case $n=2$, $3^2>3(2)$, which is obviously true.
Now, assume that for $n=k$ that $3^k>3k$. This is called the induction hypothesis. Now, we must prove the inequality for $k+1$.
$3^k>3k$ via our induction hypothesis.
$3\cdot3^k>3\cdot3k$ multiplying by $3$ on both sides.
$3^{k+1}>3\cdot3k>3k+3=3(k+1)$
Thus, the inductive step and our proof are complete.
$\endgroup$ 2 $\begingroup$Prove (again by induction) that 9(n-1) is larger or equal than 3n for n larger or equal than 2.
$\endgroup$
