Dear Fabrizio, dear Maxima user,
I'm trying to apply the so-called "WZ method" I've
learnt in chapter 7 of the book "A = B"
http://www.cis.upenn.edu/~wilf/AeqB.html
to prove combinatorial identities.
Since to do that I need an implementation of Gosper's
algorithm, I made some experiments with the command
nusum and with the Zeilberger package.
I tried a very basic example, and nusum can handle it
while (it seems) Zeilberger package cannot:
\sum_{k} (\binom(n,k) / 2^n) = 1
If I call F(n,k) = binomial(n,k)/2^n, the game is
finding a G(n,k) such that
F(n+1,k) - F(n,k) = G(n,k+1) - G(n,k)
that is the hypergeometric anti-difference of
DeltaF(n,k) = F(n+1,k) - F(n,k)
(if I guess well what an antidifference is).
In this case by pen and paper you can find that:
DeltaF(n,k) = binom(n,k)*(2*k-n-1)/(2*(n+1-k))
G(n,k) = - binomial(n,k-1)/2^(n+1)
Sometimes the ratio G(n,k)/F(n,k) = R(n,k) is called
"the WZ certificate". In this case:
R(n,k) = -k/(2*(n-k+1))
now the Maxima session:
****************************************************
(%i2) load(zeilberger);
(%o2) [...]
(%i3) F(n,k):=binomial(n,k)/2^n;
binomial(n, k)
(%o3) F(n, k) := --------------
n
2
(%i4) defrule(h,binomial(n+1,k),
binomial(n,k)*(n+1)/(n+1-k));
(%i5) DeltaF(n,k):=ratsimp(apply1(F(n+1,k)-F(n,k),h));
(%i6) DeltaF(n,k);
(n - 2 k + 1) binomial(n, k)
(%o6) - ----------------------------
n
(2 n - 2 k + 2) 2
*****************************************************
What follows made me quite disappointed:
*****************************************************
(%i7) AntiDifference(DeltaF(n,k),k);
(%o7) NON_HYPERGEOMETRIC
*****************************************************
But the function IS hypergeometric! The expected
answer is
G(n,k) = - binomial(n,k-1)/2^(n+1) or any equivalent
expression.
*****************************************************
(%i8) Gosper(DeltaF(n,k),k);
(%o8) NON_HYPERGEOMETRIC
*****************************************************
Gosper(f_k, k) should find the WZ certificate, in
this case
R(n,k) = -k/(2*(n-k+1)), but it doesn't.
*****************************************************
(%i9) GosperSum(DeltaF(n,k),k,0,k);
(%o9) NON_HYPERGEOMETRIC
*****************************************************
GosperSum should find the closed formula for the
summation, in this case
G(n,k) = - binomial(n,k-1)/2^(n+1), but it doesn't.
*****************************************************
(%i10) nusum(DeltaF(n,k),k,0,k);
Dependent equations eliminated: (1)
(k + 1) binomial(n, k + 1)
(%o10) - --------------------------
n
2 (n - k) 2
*****************************************************
And nusum happily finds the solution. What went wrong
with Zeilberger package?
Regards,
Giovanni Gherdovich
__________________________________________________
Do You Yahoo!?
Poco spazio e tanto spam? Yahoo! Mail ti protegge dallo spam e ti da tanto spazio gratuito per i tuoi file e i messaggi
http://mail.yahoo.it