# Proof by induction

1. Jan 5, 2009

1. The problem statement, all variables and given/known data
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]

2. Relevant equations

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

2. Jan 5, 2009

### HallsofIvy

Staff Emeritus
Re: proo

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.

3. Jan 5, 2009