Answer.
It might be difficult to see a pattern, so we will calculate the terms without simplifying at all.
Now it should be easier to see a pattern. It seems we have which is an explicit formula.
Proof.
Show
Proof of induction step: By the recursive definition of the sequence, Thus,
Therefore, by induction,