4

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.

N. F. Taussig
  • 76,571
PJ Johnson
  • 107
  • 2
    Well, just note $9n-9\ge 3n$ as soon as $n>1$. – Bernard Mar 13 '16 at 01:12
  • Why are you trying to prove $n-1$? Shouldn't it be for $n+1$? – zz20s Mar 13 '16 at 01: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 01:14
  • Well one is a product of 3's, the other is a sum of 3's. Just note that for any positive integers, $a, b$, greater than 1, $ab \gt a+b$. – ThisIsNotAnId Mar 13 '16 at 01:16
  • I'd love to, however I'm not smart enough to figure out how changing it from n-1 to n+1 would change the proof. I also have to assume that n is greater than or equal to two, so I would think that that would also change. – PJ Johnson Mar 13 '16 at 01:17
  • 1
    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 01:31
  • 1
    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 01:33

2 Answers2

2

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.

zz20s
  • 6,712
  • Hello, I have a doubt with regards to your answer. I do not understand the following step: $3k+1>3⋅3k>3k+3$. How did you get $3k+3$? Cheers!! – Gtexx Mar 28 '22 at 07:58
  • I got it. It's because if 3k + 1 is greater than 33k then it is certainly greater 3k + 3. eg. 33(2) > 3*2 + 3 => 18 > 9: Hence true. – Gtexx Apr 28 '22 at 23:12
1

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

J. Alvarez
  • 31