Proof by Induction: Prove a(n)=2^(n-1)[n+2]

[kmeado07]

Homework Statement

Define the numbers a(0),a(1),a(2),...by a(0)=1, a(1)=3, a(n)=4[a(n-1) - a(n-2)]. for n>=2
Show by induction that for all n>=1, a(n)=2^(n-1) [n+2]

Homework Equations

The Attempt at a Solution

proof by induction is not my stong point, and i really don't know where to start on this question. Any help would be much appreciated!

 

[HallsofIvy]

One nice thing about induction is you always know "where to start"- prove the statement is true for n= 0!

Then you will really want to use "strong induction": If, whenever a statement is true for all k less than n, it true for k= n, then the statement is true for all positive integers.

If the statement is true for all k< n, it is, in particular true for n-1 and n-2: you can assume that
$$a(n-1)= 2^{n-1-1}(n-1+ 2)= 2^{n-2}(n+1)$$
and
$$a(n-2)= 2^{n-2-1}(n-2+2)= 2^{n-3}n$$

Put those into a(n)= 4[a(n-1)- a(n-2)] and see what you get.

 

[kmeado07]

thanks for the help!