If I have a recurrence relation such as:
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
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?