Recurrence relations - intuition

[Avatrin]

Hi

My calculus textbook is completely crap at explaining recurrence relations. I know the theorems needed to solve difference equations analytically, but I do not understand why they are true.

What websites and/or books can I read to get a better intuitive understanding of recurrence relations?

PS. I am not asking how to solve some specific type of recurrence relation. Homogeneous, non-homogeneous, linear, non-linear, first-order and second order recurrence relations are all relevant.

 

[Thetes]

Avatrin,

Recurrence relations are a way to express a function by using that same function in it's definition. There is usually a base case (at least in any I can remember). Then the solution set can be built iteratively. Take the Fibonacci sequence: 0,1,1,2,3,5,8,13, etc
The sequence is just defined with 2 terms at the start F(0) = 0 and F(1) = 1. Then a relationship F(n)=F(n-1) + F(n-2). This is where things start to get confusing, at least for me, there are a lot of different way to express a set or solution in mathematics. Strangely mathematicians get uncomfortable when something is expressed in terms of itself (like the definition of numbers). The details are http://ulcar.uml.edu/~iag/CS/Fibonacci.html" , but a closed form expression is just a different way (usually much harder and less intuitive) to represent the solution. The benefit comes in calculation of F(n) when n is large. If we wanted a fast way to compute F(1000) the closed solution would directly provide an answer, but the recursive would require computations of all the previous solutions up to n.

 

[Avatrin]

I know what recurrence relations are, and I know how to solve them numerically. However, I do not understand the analytic solutions to them.

For instance, I know the solution of a linear second-order, homogeneous recurrence relation has the form:
x_n = Cr_1^n + Dr_2^n
Where r_1 and r_2 are the roots of a quadratic equation derived from the original recurrence relation.
... But, I do not understand why (the proof in my textbook was pointless)..

I would be able to solve a linear, second-order homogeneous recurrence relation, but I do not understand the process.

 

[Thetes]

Avatrin,

Sorry I glossed over the important part. If I understand correctly, you would like to see the proof of the application of the characteristic polynomial solutions. http://condor.depaul.edu/ntomuro/courses/415/notes/lecture8.html" starts the proof and continues with the cases. It's a proof by induction similar to the tower of hanoi inductive proof from the other site.