Proof by induction question, need help!?

Question

I am really stuck on this question:

If n is a natural number, prove that if Un+2 = 3Un+1 – 2Un, and U1 = 1, U2 = 3, then Un = 2^n - 1.

Answer 1

Use the notation U(n) where n is a natural number.

U(1) = 1, U(2) = 3

If the equation U(n) = 2^n -1 is true, then:

U(3) = 2^3 -1 = 8-1 =7

It should also be true that

U(3) = 3*U(2) - 2*U(1) = 3*3 - 2*1 = 9-2 = 7

So at first glance the equations give the same answer for the case where n=3.  We're off to a good start.

Now we need to prove it in the general case:

If the equation is true:

U(n+2) = 3*U(n+1) - 2*U(n)

Substitute the other equation

2^(n+2) - 1 = 3*(2^(n+1) - 1) - 2*(2^(n) - 1)

2^(n+2) -1 = 3*2^(n+1) - 3 - 2*2^(n) + 2

2^(n+2) = 3*2^(n+1) - 2*2^(n)  {Simplifly the equation, -1 = -3 + 2}

2^2 = 3*2^1 - 2 {divided by 2^n}

4 = 6 - 2

4 = 4 {wow, it's true for the general case of any n}

Since those two equations are equal of the general case of n, and they are equal for n=3, you can now rest assured for n>3!

Woot!