Hi there,

For the first part you need to use "strong" induction, that is you need more than one previous case to prove the next (you need 2.)

So for part one:

The base case:

and

Then

using the induction hypothesis on the case n-1 and n-2.

Then

For the second part

Clearly, for the base case.

Then

where by the induction hypothesis proving the result.