zeilberger is an 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.
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.
\]
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} + \ldots + a_d \, F_{n+d,k} = \Delta_K \left(R\left(n,k\right) F_{n,k}\right),
\]
where \(\Delta_k\) is the \(k\)-forward difference operator, i.e., \(\Delta_k \left(t_k\right) \equiv t_{k+1} - t_k.\)
There are also verbose versions of the commands which are called by adding one of the following prefixes:
SummaryJust a summary at the end is shown
VerboseSome information in the intermediate steps
VeryVerboseMore information
ExtraEven more information including information on the linear system in Zeilberger’s algorithm
For example:
GosperVerbose, parGosperVeryVerbose,
ZeilbergerExtra, AntiDifferenceSummary.
Returns the hypergeometric anti-difference of \(F_k\), if it exists.
Otherwise AntiDifference returns no_hyp_antidifference.
Returns the rational certificate \(R(k)\) for \(F_k\), that is,
a rational function such
that
\(F_k = R\left(k+1\right) \, F_{k+1} - R\left(k\right) \, F_k,\)
if it exists.
Otherwise, Gosper returns no_hyp_sol.
Returns the summation of \(F_k\) from \(\mathit{k} = \mathit{a}\) to \(\mathit{k} = \mathit{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
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.
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.
Default value: 5
MAX_ORD is the maximum recurrence order attempted by Zeilberger.
Default value: false
When simplified_output is true,
functions in the zeilberger package attempt
further simplification of the solution.
Default value: linsolve
linear_solver names the solver which is used to solve the system
of equations in Zeilberger’s algorithm.
Default value: true
When warnings is true,
functions in the zeilberger package print
warning messages during execution.
Default value: true
When Gosper_in_Zeilberger is true,
the Zeilberger function calls Gosper before calling parGosper.
Otherwise, Zeilberger goes immediately to parGosper.
Default value: true
When trivial_solutions is true,
Zeilberger returns solutions
which have certificate equal to zero, or all coefficients equal to zero.