Opened 11 years ago

Last modified 4 years ago

#1291 new enhancement

solving recurrences

Reported by: was Owned by: was
Priority: major Milestone: sage-feature
Component: calculus Keywords:
Cc: burcin, kevin.stueve, kcrisman, robert.marik, eviatarbach, rws, ktkohl Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by rws)

This ticket would provide an interface to Maxima's and Sympy's recurrence-solving functions.

Maxima example:

sage: maxima.load('solve_rec')
?\/Users\/was\/s\/local\/share\/maxima\/5\.13\.0\/share\/contrib\/solve_rec\/solve_rec\.mac
sage: print maxima('solve_rec(a[n]=a[n-1]+a[n-2]+n/2^n, a[n])')
                         n          n                       n
            (sqrt(5) - 1)  %k  (- 1)           (sqrt(5) + 1)  %k
                             1           n                      2    2
       a  = ------------------------- - ---- + ------------------ - ----
        n               n                  n            n              n
                       2                5 2            2            5 2

Sympy example:

>>> from sympy import Function, rsolve
>>> from sympy.abc import n
>>> y = Function('y')

>>> f = (n - 1)*y(n + 2) - (n**2 + 3*n - 2)*y(n + 1) + 2*n*(n + 1)*y(n)

>>> rsolve(f, y(n))
2**n*C0 + C1*factorial(n)

>>> rsolve(f, y(n), { y(0):0, y(1):3 })
3*2**n - 3*factorial(n)

The Maxima help:

sage: maxima.solve_rec?
Maxima 5.13.0 http://maxima.sourceforge.net
Using Lisp CLISP 2.41 (2006-10-13)
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
This is a development version of Maxima. The function bug_report()
provides bug reporting information.
(%i1) 
 -- Function: solve_rec (<eqn>, <var>, [<init>])
     Solves for hypergeometrical solutions to linear recurrence <eqn>
     with polynomials coefficient in variable <var>. Optional arguments
     <init> are initial conditions.

     `solve_rec' can solve linear recurrences with constant
     coefficients, finds hypergeometrical solutions to homogeneous
     linear recurrences with polynomial coefficients, rational
     solutions to linear recurrences with polynomial coefficients and
     can solve Ricatti type recurrences.

     Note that the running time of the algorithm used to find
     hypergeometrical solutions is exponential in the degree of the
     leading and trailing coefficient.

     To use this function first load the `solve_rec' package with
     `load(solve_rec);'.

     Example of linear recurrence with constant coefficients:

          (%i2) solve_rec(a[n]=a[n-1]+a[n-2]+n/2^n, a[n]);
                                  n          n
                     (sqrt(5) - 1)  %k  (- 1)
                                      1           n
          (%o2) a  = ------------------------- - ----
                 n               n                  n
                                2                5 2
                                                          n
                                             (sqrt(5) + 1)  %k
                                                              2    2
                                           + ------------------ - ----
                                                      n              n
                                                     2            5 2

     Example of linear recurrence with polynomial coefficients:

          (%i7) 2*x*(x+1)*y[x] - (x^2+3*x-2)*y[x+1] + (x-1)*y[x+2];
                                   2
          (%o7) (x - 1) y      - (x  + 3 x - 2) y      + 2 x (x + 1) y
                         x + 2                   x + 1                x
          (%i8) solve_rec(%, y[x], y[1]=1, y[3]=3);
                                        x
                                     3 2    x!
          (%o9)                 y  = ---- - --
                                 x    4     2

     Example of Ricatti type recurrence:

          (%i2) x*y[x+1]*y[x] - y[x+1]/(x+2) + y[x]/(x-1) = 0;
                                      y         y
                                       x + 1     x
          (%o2)         x y  y      - ------ + ----- = 0
                           x  x + 1   x + 2    x - 1
          (%i3) solve_rec(%, y[x], y[3]=5)$
          (%i4) ratsimp(minfactorial(factcomb(%)));
                                             3
                                         30 x  - 30 x
          (%o4) y  = - -------------------------------------------------
                 x        6      5       4       3       2
                       5 x  - 3 x  - 25 x  + 15 x  + 20 x  - 12 x - 1584

     See also: `solve_rec_rat', `simplify_products', and
     `product_use_gamma'.


  There are also some inexact matches for `solve_rec'.
  Try `?? solve_rec' to see them.

Change History (9)

comment:1 Changed 11 years ago by burcin

  • Cc burcin added

comment:2 Changed 9 years ago by kevin.stueve

  • Cc kevin.stueve added
  • Report Upstream set to N/A

comment:3 Changed 9 years ago by kcrisman

  • Cc kcrisman added

comment:4 Changed 9 years ago by robert.marik

  • Cc robert.marik added

comment:5 Changed 6 years ago by eviatarbach

  • Cc eviatarbach added

comment:6 Changed 5 years ago by rws

  • Cc rws added

comment:7 Changed 4 years ago by rws

  • Description modified (diff)

comment:8 Changed 4 years ago by rws

  • Description modified (diff)

Some questions must be answered before doing this:

  • Where would this live, misc/?
  • Which way to represent recurrence relations,
    1. equations of indexed values (Maxima);
    2. equations of function expressions (Sympy);
    3. a dedicated class/ring like in #15714?
  • Who commits to the review?

comment:9 Changed 4 years ago by ktkohl

  • Cc ktkohl added
Note: See TracTickets for help on using tickets.