#3940 simplify_sum (Zeilberger method) computes incorrect answer

[Dave Morris]

As reported on sage-devel and sage trac ticket #33326, maxima calculates an incorrect value for the following sum, which should evaluate to (2x + 1)^n:

(%i1) load("simplify_sum");
(%i2) simplify_sum(sum(binomial(n,s) * (x+1)^s * x^(n-s), s, 0, n));
(%o2) 2^n*x^n

Maxima obtains the correct value if the constant 1 is changed to the variable y:

(%i3) simplify_sum(sum(binomial(n,s) * (x+y)^s * x^(n-s), s, 0, n));
(%i4) (y+2*x)^n

The following verbose session shows that the bug is in Zeilberger, which is calculating an incorrect recurrence relation: sm_(n+1) should be (2x + 1) sm_n, not (2x) sm_n. So this bug is different from bug number 3788, where the recurrence relation is correct, but the initial value is wrong.

(%i3) verbose_level: 100;
100
(%i4) simplify_sum(sum(binomial(n,s) * (x+y)^s * x^(n-s), s, 0, n));
Trying with simpsum=true ...
sum with simpsum=true returns: sum((binomial(n,s))*x^(n\-s)*(x+1)^s,s,0,n)
sum_by_parts returns sum((binomial(n,s))*x^(n\-s)*(x+1)^s,s,0,n)
Trying with integral representation.
Trying with Gosper ...
Trying with extended Gosper ...
Trying with Zeilberger ...
Summand: (binomial(n,g6342))*x^(n\-g6342)*(x+1)^g6342
Changed to: (n!*x^(n\-g6342)*(x+1)^g6342)/(g6342!*(n\-g6342)!)
Found support: [0,n]
Zeilberger returns: [[(g6342*x)/(n\-g6342+1),[2*x,\-1]]]
Trying with simpsum=true ...
sum with simpsum=true returns: 1"
Degree of recurrence: 1
Zeilberger recurrence: 2*sm[n]*x - sm[n+1]=0
Initial conditions: [sm[0]=1]
Solving recurrence returns: sm[n]=2^n*x^n
Simplified solution: 2^n*x^n
Zeilberger method returns: 2^n*x^n

[Robert Dodier]

Thanks for the detailed analysis, Dave, that's very helpful.

[Dave Morris]

In case it helps, the problem (surprisingly!) does not seem to arise when the constant is negative:

(%i1)
load("simplify_sum");
for k: -5 while k <= 5 do
        print(simplify_sum(sum(binomial(n,s) * (x + k)^s * x^(n-s), s, 0, n)));

(%o1)   
(2*x-5)^n
(2*x-4)^n
(2*x-3)^n
(2*x-2)^n
(2*x-1)^n
2^n*x^n
2^n*x^n
2^n*x^n
2^n*x^n
2^n*x^n
2^n*x^n