Introduction to zeilberger
==========================

zeilberger is a implementation of Zeilberger's algorithm for definite hypergeometric summation, and also Gosper's algorithm for indefinite hypergeometric summation.

zeilberger makes use of the "filtering" optimization method developed by Axel Riese.

zeilberger was developed by Fabrizio Caruso.

load (zeilberger) loads this package.

The indefinite summation problem
................................

zeilberger implements Gosper's algorithm for indefinite hypergeometric summation. Given a hypergeometric term F_k in k we want to find its hypergeometric anti-difference, that is, a hypergeometric term f_k such that F_k = f_(k+1) - f_k.

The definite summation problem
..............................

zeilberger implements Zeilberger's algorithm for definite hypergeometric summation. Given a proper hypergeometric term (in n and k) F_(n,k) and a positive integer d we want to find a d-th order linear recurrence with polynomial coefficients (in n) for F_(n,k) and a rational function R in n and k such that

a_0 F_(n,k) + ... + a_d F_(n+d),k = Delta_K(R(n,k) F_(n,k))

where Delta_k is the k-forward difference operator, i.e., Delta_k(t_k) := t_(k+1) - t_k.

Verbosity levels
----------------

There are also verbose versions of the commands which are called by adding one of the following prefixes:

Summary
     Just a summary at the end is shown

Verbose
     Some information in the intermidiate steps

VeryVerbose
     More information

Extra
     Even more information including information on the linear system in Zeilberger's algorithm

For example: GosperVerbose, parGosperVeryVerbose, ZeilbergerExtra, AntiDifferenceSummary.

Functions and Variables for zeilberger
======================================

 -- Function: AntiDifference (F_K, K)

     Returns the hypergeometric anti-difference of F_K, if it exists. Otherwise AntiDifference returns no_hyp_antidifference.

 -- Function: Gosper (F_K, K)
     Returns the rational certificate R(K) for F_K, that is, a rational function such that

     F_k = R(k+1) F_(k+1) - R(k) F_k

     if it exists. Otherwise, Gosper returns no_hyp_sol.

 -- Function: GosperSum (F_K, K, A, B)

     Returns the summmation of F_K from K = A to K = B if F_K has a hypergeometric anti-difference. Otherwise, GosperSum returns nongosper_summable.

     Examples:

          (%i1) load (zeilberger);
          (%o1)  /usr/share/maxima/share/contrib/Zeilberger/zeilberger.mac
          (%i2) GosperSum ((-1)^k*k / (4*k^2 - 1), k, 1, n);

          Dependent equations eliminated:  (1)
                                     3       n + 1
                                (n + -) (- 1)
                                     2               1
          (%o2)               - ------------------ - -
                                            2        4
                                2 (4 (n + 1)  - 1)
          (%i3) GosperSum (1 / (4*k^2 - 1), k, 1, n);
                                          3
                                    - n - -
                                          2       1
          (%o3)                  -------------- + -
                                          2       2
                                 4 (n + 1)  - 1
          (%i4) GosperSum (x^k, k, 1, n);
                                    n + 1
                                   x          x
          (%o4)                    ------ - -----
                                   x - 1    x - 1
          (%i5) GosperSum ((-1)^k*a! / (k!*(a - k)!), k, 1, n);
                                          n + 1
                          a! (n + 1) (- 1)              a!
          (%o5)       - ------------------------- - ----------
                        a (- n + a - 1)! (n + 1)!   a (a - 1)!
          (%i6) GosperSum (k*k!, k, 1, n);

          Dependent equations eliminated:  (1)
          (%o6)                     (n + 1)! - 1
          (%i7) GosperSum ((k + 1)*k! / (k + 1)!, k, 1, n);
                            (n + 1) (n + 2) (n + 1)!
          (%o7)             ------------------------ - 1
                                    (n + 2)!
          (%i8) GosperSum (1 / ((a - k)!*k!), k, 1, n);
          (%o8)                  nonGosper_summable

 -- Function: parGosper (F_{N,K}, K, N, D)
     Attempts to find a D-th order recurrence for F_{N,K}.

     The algorithm yields a sequence [s_1, s_2, ..., s_m] of solutions. Each solution has the form

     [R(n, k), [a_0, a_1, ..., a_d]]

     parGosper returns [] if it fails to find a recurrence.

 -- Function: Zeilberger (F_{N,K}, K, N)
     Attempts to compute the indefinite hypergeometric summation of F_{N,K}.

     Zeilberger first invokes Gosper, and if that fails to find a solution, then invokes parGosper with order 1, 2, 3, ..., up to MAX_ORD. If Zeilberger finds a solution before reaching MAX_ORD, it stops and returns the solution.

     The algorithms yields a sequence [s_1, s_2, ..., s_m] of solutions. Each solution has the form

     [R(n,k), [a_0, a_1, ..., a_d]]

     Zeilberger returns [] if it fails to find a solution.

     Zeilberger invokes Gosper only if gosper_in_zeilberger is true.

General global variables
========================

 -- Global variable: MAX_ORD
     Default value: 5

     MAX_ORD is the maximum recurrence order attempted by Zeilberger.

 -- Global variable: simplified_output
     Default value: false

     When simplified_output is true, functions in the zeilberger package attempt further simplification of the solution.

 -- Global variable: linear_solver
     Default value: linsolve

     linear_solver names the solver which is used to solve the system of equations in Zeilberger's algorithm.

 -- Global variable: warnings
     Default value: true

     When warnings is true, functions in the zeilberger package print warning messages during execution.

 -- Global variable: gosper_in_zeilberger
     Default value: true

     When gosper_in_zeilberger is true, the Zeilberger function calls Gosper before calling parGosper. Otherwise, Zeilberger goes immediately to parGosper.

 -- Global variable: trivial_solutions
     Default value: true

     When trivial_solutions is true, Zeilberger returns solutions which have certificate equal to zero, or all coefficients equal to zero.

Variables related to the modular test
=====================================

 -- Global variable: mod_test
     Default value: false

     When mod_test is true, parGosper executes a modular test for discarding systems with no solutions.

 -- Global variable: modular_linear_solver
     Default value: linsolve

     modular_linear_solver names the linear solver used by the modular test in parGosper.

 -- Global variable: ev_point
     Default value: big_primes[10]

     ev_point is the value at which the variable N is evaluated when executing the modular test in parGosper.

 -- Global variable: mod_big_prime
     Default value: big_primes[1]

     mod_big_prime is the modulus used by the modular test in parGosper.

 -- Global variable: mod_threshold
     Default value: 4

     mod_threshold is the greatest order for which the modular test in parGosper is attempted.