\input texinfo
@c makeinfo solve_rec.texi         to make .info
@c texi2html solve_rec.texi        to make .html
@c texi2pdf solve_rec.texi         to make .pdf

@setfilename solve_rec.info
@settitle solve_rec

@ifinfo 
@macro var {obj}
<\obj\>
@end macro
@end ifinfo

@node Top, Introduction to solve_rec, (dir), (dir)
@top
@menu
* Introduction to solve_rec::
* Definitions for solve_rec::
* Function and variable index::
@end menu

@node Introduction to solve_rec, Definitions for solve_rec, Top, Top
@section Introduction to solve_rec

@code{solve_rec} is a package for solving linear recurrences with polynomial
coefficients.

A demo is available with @code{demo(solve_rec);}.

Example:

@example
(%i1) load("solve_rec")$
(%i2) solve_rec((n+4)*s[n+2] + s[n+1] - (n+1)*s[n], s[n]);
                                    n
                 %k  (2 n + 3) (- 1)          %k
                   1                            2
(%o2)       s  = -------------------- + ---------------
             n     (n + 1) (n + 2)      (n + 1) (n + 2)
@end example

@node Definitions for solve_rec, Function and variable index, Introduction to solve_rec, Top

@section Definitions for solve_rec

@deffn {Function} reduce_order (@var{rec}, @var{sol}, @var{var})

Reduces the order of linear recurrence @var{rec} when a particular solution
@var{sol} is known. The reduced reccurence can be used to get other solutions.

Example:

@example
(%i3) rec: x[n+2] = x[n+1] + x[n]/n;
                                      x
                                       n
(%o3)               x      = x      + --
                     n + 2    n + 1   n
(%i4) solve_rec(rec, x[n]);
WARNING: found some hypergeometrical solutions! 
(%o4)                    x  = %k  n
                          n     1
(%i5) reduce_order(rec, n, x[n]);
(%t5)                    x  = n %z
                          n       n

                           n - 1
                           ====
                           \
(%t6)                %z  =  >     %u
                       n   /        %j
                           ====
                           %j = 0

(%o6)             (- n - 2) %u     - %u
                              n + 1     n
(%i6) solve_rec((n+2)*%u[n+1] + %u[n], %u[n]);
                                     n
                            %k  (- 1)
                              1
(%o6)                 %u  = ----------
                        n    (n + 1)!

So the general solution is

             n - 1
             ====        n
             \      (- 1)
       %k  n  >    -------- + %k  n
         2   /     (n + 1)!     1
             ====
             n = 0
@end example

@end deffn

@defvr {Option variable} simplify_products

If @code{simplify_products} is @code{true}, @code{solve_rec} will try to
simplify products in result. The default value is @code{true}.

See also: solve_rec.

@end defvr

@deffn {Function} solve_rec (@var{eqn}, @var{var}, [@var{init}])
Solves for hypergeometrical solutions to linear recurrence @var{eqn} with
polynomials coefficient in variable @var{var}. Optional arguments @var{init}
are initial conditions.

@code{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 @code{solve_rec} package with
@code{load(solve_rec);}.

Example of linear recurrence with constant coefficients:

@example
(%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
@end example

Example of linear recurrence with polynomial coefficients:

@example
(%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
@end example

Example of Ricatti type recurrence:

@example
(%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
@end example


See also: solve_rec_rat, simplify_products, product_use_gamma.

@end deffn

@deffn {Function} solve_rec_rat (@var{eqn}, @var{var}, [@var{init}])

Solves for rational solutions to linear recurrences. See solve_rec for
description of arguments.

To use this function first load the @code{solve_rec} package with
@code{load(solve_rec);}.

Example:

@example
(%i1) (x+4)*a[x+3] + (x+3)*a[x+2] - x*a[x+1] + (x^2-1)*a[x];
(%o1)  (x + 4) a      + (x + 3) a      - x a
                x + 3            x + 2      x + 1
                                                   2
                                               + (x  - 1) a
                                                            x
(%i2) solve_rec_rat(% = (x+2)/(x+1), a[x]);
                       1
(%o2)      a  = ---------------
            x   (x - 1) (x + 1)
@end example


See also: solve_rec.

@end deffn

@defvr {Option variable} product_use_gamma

When simplifying products, @code{solve_rec} introduces gamma function
into the expression if @code{produce_use_gamma} is @code{true}. The default
value is @code{true}.

See also: simplify_products, solve_rec.

@end defvr

@deffn {Function} summand_to_rec (@var{summand}, @var{k}, @var{n})

Returns the recurrence sattisfied by the sum

@example
    inf
    ====
    \
     >     summand
    /
    ====
  k = minf
@end example

where summand is hypergeometrical in @var{k} and @var{n}. Zeilberger package
must be loaded before using this function.

To use this function first load the @code{solve_rec} package with
@code{load(solve_rec)} and the @code{zeilberger} package with
@code{load(zeilberger)}.

@example
(%i17) load("zeilberger")$
(%i18) summand: binom(3*k+1,k)*binom(3*(n-k),n-k)/(3*k+1)$
(%i19) summand_to_rec(summand, k, n);
Dependent equations eliminated:  (3 2)
(%o19) - 4 (n + 2) (2 n + 3) (2 n + 5) sm
                                         n + 2
                    2
 + 12 (2 n + 3) (9 n  + 27 n + 22) sm
                                     n + 1
 - 81 (n + 1) (3 n + 2) (3 n + 4) sm
                                    n
(%i21) sum(''summand, k, 0, n), n=0;
(%o21)                       1
(%i22) sum(''summand, k, 0, n), n=1;
(%o22)                       4
(%i23) product_use_gamma: false$
(%i24) solve_rec(%o19, sm[n], sm[0]=1, sm[1]=4);
              n - 1               n - 1
              /===\               /===\
               ! !                 ! !                n
             ( ! !   (3 %j + 2)) ( ! !   (3 %j + 4)) 3
               ! !                 ! !
              %j = 0              %j = 0
(%o24) sm  = ------------------------------------------
         n            n - 1
                      /===\
                       ! !                n
                     ( ! !   (2 %j + 3)) 2  n!
                       ! !
                      %j = 0
@end example

@end deffn

@node Function and variable index,  , Definitions for solve_rec, Top
@appendix Function and variable index
@printindex fn
@printindex vr

@bye
