I worked out a proof by induction for my specific problem. I still don't understand how I got the equation though. Can anyone explain it?
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?
A second order linear homogeneous recurrence relation has the form...
a) we first demonstrate that if and are two independent solution of (1), then also , where and are arbitrary constants, is also solution of (1)...
... for what we have supposed is...
... so that multiplying the first of (2) by and the second of (2) by we obtain...
... that is what we want to demonstrate...
b) ... then we demonstrate that if and are constant and and are two real dinstict roots of the equation...
... then and ...
... setting is the first of (3) we obtain...
... that is what we want to demonstrate. The same is for ...
I'll explain the steps.
I don't know if it will clear up the mystery for you.
First, we conjecture that the generating function is exponential.
. . Let
So we have: .
Quadratic Formula: .
Form a linear combination of the two roots:
. . .
Use the first two terms of the sequence to set up a system of equations:
Solve the system: .
Substitute into  and we have the closed form of the recurrence.