# Proving $3^n \geq 3n$ using mathematical induction

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.

• Well, just note $9n-9\ge 3n$ as soon as $n>1$. – Bernard Mar 13 '16 at 1:12
• Why are you trying to prove $n-1$? Shouldn't it be for $n+1$? – zz20s Mar 13 '16 at 1:13
• The math book I'm using teaches n-1. I know that's not a great answer, but it is what it is. – PJ Johnson Mar 13 '16 at 1:14
• PJ: I suspect what is happening is the following: your book says that (after doing the base case) if you assume it to be true for $n-1$, and you then prove it for $n$, then you say 'Induction!' and are done. If this is true, you should not be manipulating the $n-1$ case. Rather, you should start with the $n$ case, and manipulate it until it looks like $n-1$ case (possibly with some extras hanging around.) – Eric Stucky Mar 13 '16 at 1:31
• Making the change of variables $m=n-1$, you can also assume the $m$ case, and prove the $m+1$ case. (In other words, start with the $m+1$ case, and make it look like the $m$ case). This is what most books do, but as you can see, they are equivalent because you're just making an easy substitution. – Eric Stucky Mar 13 '16 at 1:33

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.

Prove (again by induction) that 9(n-1) is larger or equal than 3n for n larger or equal than 2.