How to Prove 1+2n ≤ 3^n for All Positive Integers by Induction?

[zeion]

Homework Statement

Show that the statement holds for all positive integers n.

1+2n <= 3^n

Homework Equations

The Attempt at a Solution

n = 1
1+2 <= 3

n = k
1+2k <= 3^k

n = (k+1)

1+2(k+1) <= 3^(k+1)
2k + 3 <= (3)(3^k)

Not sure what to do now

2k/3 + 1 <= 3^k

 

[VietDao29]

Homework Statement

Show that the statement holds for all positive integers n.

1+2n <= 3^n

Homework Equations

The Attempt at a Solution

n = 1
1+2 <= 3

n = k
1+2k <= 3^k

n = (k+1)

1+2(k+1) <= 3^(k+1)
2k + 3 <= (3)(3^k)

Not sure what to do now

2k/3 + 1 <= 3^k

Hint:

Use your Induction Hypothesis (i.e, 1 + 2k <= 3^k) to move on.

Remember that, you are trying to prove: 1 + 2(k+1) <= 3^{k + 1}.

So: 1 + 2(k+1) = 2k + 3 = 2k + 1 + 2 <= ...

 

[zeion]

Assume:
3^k >= 1 + 2(k+1)
Then:
3^(k+1) = 3^k(3) >= (1 + 2(k+1))(3)

Then to proof it (1 + 2(k+1))(3) >= 1 + 2(k+1)

(1 + 2k + 2)(3) >= 1 + 2k + 2
6k + 9 >= 2k + 3
3(2k + 3) >= 2k + 3

Is that right??

 

[VietDao29]

Assume:
3^k >= 1 + 2(k+1)

No, your assumption is incorrect. :( What you should have assumed is:

3^k >= 1 + 2k

NOT

3^k >= 1 + 2(k + 1)

Let's try to do it again then.

 

[zeion]

Assume:
3^k >= 1 + 2k

Then:
3^k+1 = 3^k(3) >= (3)(1+2k)

Proof that:
3(1+2k) >= (1 + 2k)

 

[VietDao29]

Assume:
3^k >= 1 + 2k

Then:
3^k+1 = 3^k(3) >= (3)(1+2k)

Proof that:
3(1+2k) >= (1 + 2k)

Yup. And what's left is just to prove that 3(1+2k) >= (1 + 2k). Note that we already have k >= 0.

How can you go about proving the above inequality?

 

[zeion]

If k >= 0 then (1 + 2k) is > 0.
Let a be (1 + 2k)
3a >= a

 

[NaomiTjipombo]

can someone pls help to proof the following by induction:
A^n=P D^n P^(-1)

 

[gb7nash]

You might want to start your own thread.