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:
using the induction hypothesis on the case n-1 and n-2.
For the second part
Clearly, for the base case.
where by the induction hypothesis proving the result.