Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recurrence relations - intuition

  1. Oct 12, 2011 #1

    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.
  2. jcsd
  3. Oct 12, 2011 #2

    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" [Broken], 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.
    Last edited by a moderator: May 5, 2017
  4. Oct 13, 2011 #3
    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.
  5. Oct 13, 2011 #4

    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" [Broken] 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.
    Last edited by a moderator: May 5, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook