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

A Algorithms for solving recurrence relations?

  1. Aug 2, 2016 #1

    Stephen Tashi

    User Avatar
    Science Advisor

    Is there good survey of known algorithms for solving recurrence relations ?

    By "solving" a recurrence relation such as [itex] a_n = \sum_{i=1}^{k} { c_k a_{n-k}} [/itex], I mean to express [itex] a_n [/itex] as a function of [itex] n [/itex].

    In the case that the [itex] c_i [/itex] are constants the algorithm based on the "characteristic equation" can be used, but what is know about cases where the [itex] c_i [/itex] are themselves functions of [itex] n [/itex] ?

    For example, it seems that the "next simplest" case would be where the [itex] c_i [/itex] are known linear functions of [itex] n [/itex].
     
  2. jcsd
  3. Aug 2, 2016 #2

    pasmith

    User Avatar
    Homework Helper

    For polynomial [itex]c_k[/itex], the trick is to multiply both sides by [itex]x^n[/itex] and sum from [itex]n=0[/itex] to infinity, turning the recurrence relation into an equation of formal power series. Then you can turn that into a differential equation for [itex]f(x) = \sum a_nx^n[/itex] (valid where the power series converges) by using such identities as [tex]
    n^kx^n = \left(x \frac{d}{dx}\right)^k x^n.[/tex]
     
  4. Aug 2, 2016 #3

    Stephen Tashi

    User Avatar
    Science Advisor

    By an amusing coincidence, my interest in solving recurrence relations is prompted by the problem of solving the recurrence relations that arise in finding power series solutions to differential equations ! Common examples of that type of problem show using the D.E. to formulate the recurrence relation and then solving the recurrence relation "by inspection". So my question concerns finding [itex] a_n [/itex] as an explicit function of [itex] n [/itex].
     
  5. Aug 4, 2016 #4

    pasmith

    User Avatar
    Homework Helper

    The case [tex]
    a_n = (pn + q)a_{n-1}[/tex] has the explicit solution [tex]
    a_n = a_0\prod_{k=1}^n (pk + q).[/tex] This is of course just a special case of the solution of [itex]a_n = f(n)a_{n-1}[/itex] being [tex]
    a_n = a_0\prod_{k=1}^n f(k).[/tex] So where it gets difficult is [tex]
    a_n = (p_1n + q_1)a_{n-1} + (p_2n + q_2)a_{n-2}.[/tex] However such recurrence relations are unlikely to describe coefficients of power series solutions to differential equations as they may not have strictly positive radius of convergence.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Algorithms for solving recurrence relations?
Loading...