If I have a recurrence relation such as:

$\displaystyle a(n) = A*a(n-1) + B*a(n-2)$ where $\displaystyle a(0)=X, a(1)=Y$

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 $\displaystyle a(n) = r^n$

Then $\displaystyle r^n=A*r^(n-1)+B*r^(n-2)$

Then $\displaystyle r^2-(A*r)-B=0$

You solve this and you write: $\displaystyle a(n)=C*root1^n+D*root2^n$

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