Introduction to solve_rec
=========================

solve_rec is a package for solving linear recurrences with polynomial coefficients.

A demo is available with demo(solve_rec);.

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)

Functions and Variables for solve_rec
=====================================

 -- Function: reduce_order (REC, SOL, VAR)

     Reduces the order of linear recurrence REC when a particular solution SOL is known. The reduced reccurence can be used to get other solutions.

     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

 -- Option variable: simplify_products
     Default value: true

     If simplify_products is true, solve_rec will try to simplify products in result.

     See also: solve_rec.

 -- Function: simplify_sum (EXPR)

     Tries to simplify all sums appearing in EXPR to a closed form.

     simplify_sum uses Gosper and Zeilberger algorithms to simplify sums.

     To use this function first load the simplify_sum package with load(simplify_sum).

     Example:

          (%i1) load("simplify_sum")$
          (%i2) sum(binom(n+k,k)/2^k, k, 0, n)
                                       + sum(binom(2*n, 2*k), k, 0, n);
                   n                            n
                  ====                         ====
                  \      binomial(n + k, k)    \
          (%o2)    >     ------------------ +   >    binomial(2 n, 2 k)
                  /               k            /
                  ====           2             ====
                  k = 0                        k = 0
          (%i3) simplify_sum(%);
                                         n
                                        4     n
          (%o3)                         -- + 2
                                        2

 -- 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.

 -- Function: solve_rec_rat (EQN, VAR, [INIT])

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

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

     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)

     See also: solve_rec.

 -- Option variable: product_use_gamma
     Default value: true

     When simplifying products, solve_rec introduces gamma function into the expression if product_use_gamma is true.

     See also: simplify_products, solve_rec.

 -- Function: summand_to_rec (SUMMAND, K, N)
 -- Function: summand_to_rec (SUMMAND, [K, LO, HI], N)

     Returns the recurrence sattisfied by the sum

               hi
              ====
              \
               >     summand
              /
              ====
            k = lo

     where summand is hypergeometrical in K and N. If LO and HI are omited, they are assumed to be lo = -inf and hi = inf.

     To use this function first load the simplify_sum package with load(simplify_sum).

     Example:

          (%i1) load("simplify_sum")$
          (%i2) summand: binom(n,k);
          (%o2)                           binomial(n, k)
          (%i3) summand_to_rec(summand,k,n);
          (%o3)                      2 sm  - sm      = 0
                                         n     n + 1
          (%i7) summand: binom(n, k)/(k+1);
                                          binomial(n, k)
          (%o7)                           --------------
                                              k + 1
          (%i8) summand_to_rec(summand, [k, 0, n], n);
          (%o8)               2 (n + 1) sm  - (n + 2) sm      = - 1
                                          n             n + 1