#1291: solving recurrences
-------------------------------+----------------------------
Reporter: was | Owner: was
Type: enhancement | Status: new
Priority: major | Milestone: sage-feature
Component: calculus | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
-------------------------------+----------------------------
Description changed by rws:
Old description:
> Sage should be able to easily solve at least some recurrences. Maxima is
> actually pretty capable here.
> {{{
> 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
>
> }}}
>
> Somebody should wrap this:
> {{{
>
> 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.
> }}}
New description:
Sage should be able to easily solve at least some recurrences. Maxima is
actually pretty capable here.
{{{
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
}}}
Somebody should wrap this:
{{{
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.
}}}
Since there is also `sympy.rsolve` which is quite capable, this ticket
should wrap both maxima and sympy.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/1291#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
