Hey guys, was hoping someone could walk me thru an induction proof

Im given: for

Prove that for all natural numbers n.

First is base case. We see that and base case done.

Now inductive step. Assume is true.....now what do I do?

I know how to set up a proof by induction of a sum, but these recurrence formulas just aren't clear yet.

After this, how would I go about proving an inequality using a recurrence formula...like this problem below:

Prove if then

Thanks!