Algorithms for solving recurrence relations?

  • #1
Stephen Tashi
Science Advisor
7,864
1,602
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].
 
Mathematics news on Phys.org
  • #2
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]
 
  • Like
Likes mfb
  • #3
pasmith said:
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]

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].
 
  • #4
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.
 
  • Like
Likes Stephen Tashi

Similar threads

Back
Top