[ < ] [ > ] [ << ] [ Up ] [ >> ] [Top] [Contents] [Index] [ ? ]

# 81. zeilberger

 [ < ] [ > ] [ << ] [ Up ] [ >> ] [Top] [Contents] [Index] [ ? ]

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

Categories:  Sums and products · Share packages · Package zeilberger

 [ < ] [ > ] [ << ] [ Up ] [ >> ] [Top] [Contents] [Index] [ ? ]

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

 [ < ] [ > ] [ << ] [ Up ] [ >> ] [Top] [Contents] [Index] [ ? ]

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

 [ < ] [ > ] [ << ] [ Up ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 81.1.1 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`

`Extra`

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

For example:
`GosperVerbose`, `parGosperVeryVerbose`, `ZeilbergerExtra`, `AntiDifferenceSummary`.

 [ < ] [ > ] [ << ] [ Up ] [ >> ] [Top] [Contents] [Index] [ ? ]

## 81.2 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`.

Categories:  Package zeilberger

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

Categories:  Package zeilberger

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)\$
(%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)                  NON_GOSPER_SUMMABLE
```

Categories:  Package zeilberger

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.

Categories:  Package zeilberger

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

Categories:  Package zeilberger

 [ < ] [ > ] [ << ] [ Up ] [ >> ] [Top] [Contents] [Index] [ ? ]

## 81.3 General global variables

Global variable: MAX_ORD

Default value: 5

`MAX_ORD` is the maximum recurrence order attempted by `Zeilberger`.

Categories:  Package zeilberger

Global variable: simplified_output

Default value: `false`

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

Categories:  Package zeilberger

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.

Categories:  Package zeilberger

Global variable: warnings

Default value: `true`

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

Categories:  Package zeilberger

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

Categories:  Package zeilberger

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.

Categories:  Package zeilberger

 [ < ] [ > ] [ << ] [ Up ] [ >> ] [Top] [Contents] [Index] [ ? ]

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

Categories:  Package zeilberger

Global variable: modular_linear_solver

Default value: `linsolve`

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

Categories:  Package zeilberger

Global variable: ev_point

Default value: `big_primes`

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

Categories:  Package zeilberger

Global variable: mod_big_prime

Default value: `big_primes`

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

Categories:  Package zeilberger

Global variable: mod_threshold

Default value: 4

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

Categories:  Package zeilberger

 [ << ] [ >> ] [Top] [Contents] [Index] [ ? ]

This document was generated by Oliver Kullmann on May, 18 2013 using texi2html 1.76.