# Proof by induction question

1. Sep 25, 2009

### zeion

1. The problem statement, all variables and given/known data

Show that the statement holds for all positive integers n.

1+2n <= 3^n

2. Relevant equations

3. 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

2. Sep 25, 2009

### VietDao29

Hint:

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

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

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

3. Sep 25, 2009

### 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??

4. Sep 25, 2009

### VietDao29

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

3k >= 1 + 2k

NOT

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

Let's try to do it again then.

5. Sep 25, 2009

### zeion

Assume:
3k >= 1 + 2k

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

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

6. Sep 26, 2009

### VietDao29

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?

7. Sep 26, 2009

### zeion

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

8. May 25, 2011

### NaomiTjipombo

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

9. May 25, 2011