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) + ... + 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\).
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
.
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(k+1) F_(k+1) - R(k) F_k\),
if it exists. Otherwise, Gosper
returns no_hyp_sol
.
Returns the summmation 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.