[Maxima-discuss] bug in the implementation of Zeilberger algorithm

[Vladimir D. <vla...@gm...>]

Hello, 

I was trying to use the implementation of the Zeilberger algorithm in Maxima (http://maxima.sourceforge.net/docs/manual/de/maxima_77.html#SEC400), both in the most recent version of Maxima for MacOS, and through the sage interface. It seems to me that there is a mistake somewhere in it, which is supported by the following computation (immediately related to one little bit of my current research):

The sequence of commands

load (zeilberger)$
Zeilberger((-1)^(n-k)*binomial(2*n+k,2*n)*binomial(k,n-k)*a^(2*k-n)*b^(n-k)/(2*n+1),k,n);

produces the output

[[b^2*(n-2*k)*(n-2*k+1)*(5120*b^3*n^5+7396*a^2*b^2*n^5-5445*a^4*b*n^5+48\
6*a^6*n^5+10240*b^3*k*n^4-21048*a^2*b^2*k*n^4+9018*a^4*b*k*n^4-729*a^6*k\
*n^4+28672*b^3*n^4+47924*a^2*b^2*n^4-34320*a^4*b*n^4+2997*a^6*n^4+7680*b\
^3*k^2*n^3-9116*a^2*b^2*k^2*n^3+3627*a^4*b*k^2*n^3-486*a^6*k^2*n^3+44544\
*b^3*k*n^3-87236*a^2*b^2*k*n^3+36423*a^4*b*k*n^3-2673*a^6*k*n^3+60160*b^\
3*n^3+119096*a^2*b^2*n^3-82605*a^4*b*n^3+6993*a^6*n^3+2560*b^3*k^3*n^2-1\
632*a^2*b^2*k^3*n^2+216*a^4*b*k^3*n^2+23808*b^3*k^2*n^2-30680*a^2*b^2*k^\
2*n^2+12939*a^4*b*k^2*n^2-1782*a^6*k^2*n^2+67840*b^3*k*n^2-126392*a^2*b^\
2*k*n^2+50577*a^4*b*k*n^2-3078*a^6*k*n^2+58880*b^3*n^2+140944*a^2*b^2*n^\
2-94302*a^4*b*n^2+7632*a^6*n^2+320*b^3*k^4*n-224*a^2*b^2*k^4*n+36*a^4*b*\
k^4*n+4736*b^3*k^3*n-3016*a^2*b^2*k^3*n+378*a^4*b*k^3*n+22720*b^3*k^2*n-\
32464*a^2*b^2*k^2*n+14538*a^4*b*k^2*n-2052*a^6*k^2*n+42880*b^3*k*n-75080\
*a^2*b^2*k*n+27996*a^4*b*k*n-1080*a^6*k*n+26880*b^3*n+78960*a^2*b^2*n-50\
820*a^4*b*n+3852*a^6*n+192*b^3*k^4-144*a^2*b^2*k^4+24*a^4*b*k^4+1920*b^3\
*k^3-1272*a^2*b^2*k^3+156*a^4*b*k^3+6720*b^3*k^2-10536*a^2*b^2*k^2+4968*\
a^4*b*k^2-720*a^6*k^2+9600*b^3*k-15648*a^2*b^2*k+5244*a^4*b*k+4608*b^3+1\
6800*a^2*b^2-10392*a^4*b+720*a^6)/(a^2*(n-k+1)*(n-k+2)),[-5*b^3*(5*n+2)*\
(5*n+3)*(5*n+4)*(5*n+6)*(20*b*n-9*a^2*n+32*b-15*a^2),2*a*(n+1)*(2*n+3)*(\
10000*b^3*n^3-9000*a^2*b^2*n^3+2565*a^4*b*n^3-243*a^6*n^3+36000*b^3*n^2-\
32700*a^2*b^2*n^2+9369*a^4*b*n^2-891*a^6*n^2+40400*b^3*n-37140*a^2*b^2*n\
+10722*a^4*b*n-1026*a^6*n+13560*b^3-12720*a^2*b^2+3720*a^4*b-360*a^6),-4\
*(4*b-a^2)^2*(n+1)*(n+2)*(2*n+3)*(2*n+5)*(20*b*n-9*a^2*n+12*b-6*a^2)]]]

While the sequence of commands 

load (zeilberger)$
Zeilberger((-1)^(n-k)*binomial(2*n+k,2*n)*binomial(k,n-k)*(1/6)^(2*k-n)*(1/120)^(n-k)/(2*n+1),k,n);

produces the output

[[-(n-2*k)*(n-2*k+1)*(7557*n^5-2519*k*n^4+45273*n^4+1705*k^2*n^3-8942*k*\
n^3+103644*n^3+1144*k^3*n^2+4285*k^2*n^2-11053*k*n^2+113154*n^2+132*k^4*\
n+2098*k^3*n+2742*k^2*n-5284*k*n+58872*n+72*k^4+804*k^3+432*k^2-804*k+11\
736)/(5*(n-k+1)*(n-k+2)),[(5*n+2)*(5*n+3)*(5*n+4)*(5*n+6)*(11*n+17),-16*\
(n+1)*(2*n+3)*(1661*n^3+5889*n^2+6478*n+2100),2880*(n+1)*(n+2)*(2*n+3)*(\
2*n+5)*(11*n+6)]]]

The second one is the particular case of the first one, with a=1/6 and b=1/120, however it does not agree with it. 
More interestingly, the first result is actually correct, while the second result is wrong (one can check directly that
the recurrence relation computed by it does not hold. 

I cannot even start to guess what could be wrong, but something is...

Regards,
Vladimir Dotsenko