# A Proof by induction

1. Oct 14, 2004

### eku_girl83

Prove that for all n in the natural numbers 3^n greater than or equal to 1+2^n.

Here's my start:
3^1 greater than or equal to 1+2^1, so the statement is true for n=1.
Assume that for some n, 3^n greater than or equal to 1+2^n
Then 3^n+3^n+3^n greater than or equal to 1+2^n +3^n+3^n.
It follows that 3^(n+1) greater than or equal to 1+2^n+2*3^n.

Where do I go from here? I still need to show that 1+2^n+2*3^n is greater than or equal to 1+2^(n+1)

Thanks!

Last edited: Oct 14, 2004
2. Oct 14, 2004

### NateTG

3. Oct 14, 2004

### mathman

To show 3n+1>1+2n+1
subtract the n expressions from both sides, and you will have to show
2*3n>2n
That looks obviously true,since 3>2.

4. Oct 14, 2004

### somy

good work mathman!!!

5. Oct 16, 2004

### Fredrik

Staff Emeritus
So you'd like to prove that

$$3^n\geq 1+2^n$$

using induction. The statement is obviously true for n=1, so all you have to do is to prove that if it's true for n=k, it's also true for n=k+1 (whatever k is).

So you should start like this:

$$3^{k+1}=3\cdot 3^k\geq 3(1+2^k)\geq\dots$$

Now all you have to do is to show that this is

$$\geq 1+2^{k+1}$$

This is very easy. (Hint: 3>2>1).