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 here (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. This (http://condor.depaul.edu/ntomuro/courses/415/notes/lecture8.html) goes through the (simple) types of recurrence relations but leaves out an important proof. Which I think is what you are wanting to see, so page 41 (http://www.google.com/url?sa=t&source=web&cd=1&ved=0CB0QFjAA&url=http%3A%2F%2Farts-sciences.und.edu%2Fmath%2F_files%2Fdocs%2Fcourses% 2Fsupp%2Fmath-408%2Fmath-408-notes-b.pdf&rct=j&q=math-408-notes-b.pdf&ei=z3mXToKEGeWEsAL57tTTBA&usg=AFQjCNFMiXxp7kC_rrTa0GmcxhbfG6SfSw&sig2=tXDBNdeAaszUMLsbks7Gsg&cad=rja) 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.