A sequence (F1,F2,F3,) is dened recursively as follows. (This recursive denition is called a recurrence equation.)

Fn = (1, n = 1,

2F[subscript(n +1)], n 2. )

(a) Compute F1,F2,,F10 and tabulate results.

(b) Prove by induction on n that

Fn = 2^n 1, n 1.