If I have a recurrence relation such as:

where

how do I solve this?

Wikipedia explains how to solve such an equation and I used it and it worked for me. But I don't understand how it works.

This is what Wiki says (in short):

With our equation above we try to find an answer of the form

Then

Then

You solve this and you write:

You then work out what C and D are (using a(0) and a(1) which you already know and you have your equation.

(This is the link to wikipedia's explanation:

Recurrence relation - Wikipedia, the free encyclopedia)

Could someone explain why this works please.

And also, how does one prove that the new formula is correct?

Thanks