First, judging by the explicit formula for , we have and . (This information should have been given explicitly in the beginning of the problem.) Either from the explicit formula or from the recurrence equation one can calculate that , , etc. Therefore, and , which fits the general law that we have to show.

Next, from the original equation we get . The right-hand side looks like the left-hand side where n has been replaced by n - 1. By continuing this way, we indeed can arrive at .

I think it is easier to prove by induction. Both the base case and the induction step have been shown above.

Proving the explicit formula by induction is also straightforward. Follow the general outline: identify the induction statement P(n); prove the base case P(1); fix an arbitrary n, assume P(n - 1) and use it to prove P(n). If you have difficulties, post what you have done and the description of the difficulty.