4
$\begingroup$

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$
  • 2
    $\begingroup$ Well, just note $9n-9\ge 3n$ as soon as $n>1$. $\endgroup$ – Bernard Mar 13 '16 at 1:12
  • $\begingroup$ Why are you trying to prove $n-1$? Shouldn't it be for $n+1$? $\endgroup$ – zz20s Mar 13 '16 at 1:13
  • $\begingroup$ The math book I'm using teaches n-1. I know that's not a great answer, but it is what it is. $\endgroup$ – PJ Johnson Mar 13 '16 at 1:14
  • 1
    $\begingroup$ 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.) $\endgroup$ – Eric Stucky Mar 13 '16 at 1:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Eric Stucky Mar 13 '16 at 1:33
2
$\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$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.