Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project!

## #2791 division by zero in simplify_sum

None
open
nobody
5
2014-07-29
2014-07-29
Robert Dodier
No

Following example courtesy of Andre Maute on the mailing list 2014-07-15: "unexpected behavior of simplify_sum"

For the given example, `simplify_sum` causes the error `expt: undefined: 0 to a negative exponent` and returns the original expression.

Tracing `subst` shows that the problem is actually a division by zero: `simplify_sum` attempts something similar to `subst(gfoo = n, .../(n - gfoo))` where `gfoo` is a gensym.

The `n - gfoo` might appear because both `n` and `i` (i.e., the summation limit and the summation index) appear in the summand. I don't know if that's generally a problem for the Zeilberger method (which `simplify_sum` is attempting). I tried the same problem, renaming the summation limit to `m`, but Zeilberger couldn't solve that (Zeilberger returned `false`); so, no error, but no result either.

Here is a session which shows how the immediate cause of the error is `subst`:

```\$ maxima
Maxima 5.32.1 http://maxima.sourceforge.net
using Lisp CLISP 2.49 (2010-07-07)
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.
(%i1) display2d : false \$
(%i2) linel : 72 \$
(%i4) verbose_level : 4 \$
(%i5) s : sum((-1)^n*(-1)^i*binomial(n,i)*binomial(n+i,i-1)/(2*i+1),i,1,n) \$
(%i6) trace (subst);
(%o6) [subst]
(%i7) simplify_sum (s);
1 Enter ?subst
[?g16488,i,(-1)^(n+i)*binomial(n,i)*binomial(n+i,i-1)/(2*i+1)]
1 Exit  ?subst
(1+2*?g16488)^-1*(-1)^(?g16488+n)*binomial(n,?g16488)
*binomial(?g16488+n,-1+?g16488)
1 Enter ?subst
[i,?g16488,
binomial(n,?g16488)*(-1)^(?g16488+n)*binomial(?g16488+n,?g16488-1)
/(2*?g16488+1)]
1 Exit  ?subst (-1)^(n+i)*binomial(n,i)*binomial(n+i,i-1)/(2*i+1)
Trying with simpsum=true ...
1 Enter ?subst
[?g16552,i,(-1)^(n+i)*binomial(n,i)*binomial(n+i,i-1)/(2*i+1)]
1 Exit  ?subst
(1+2*?g16552)^-1*(-1)^(?g16552+n)*binomial(n,?g16552)
*binomial(?g16552+n,-1+?g16552)
1 Enter ?subst
[i,?g16552,
binomial(n,?g16552)*(-1)^(?g16552+n)*binomial(?g16552+n,?g16552-1)
/(2*?g16552+1)]
1 Exit  ?subst (-1)^(n+i)*binomial(n,i)*binomial(n+i,i-1)/(2*i+1)
sum with simpsum=true returns:
'sum((-1)^(n+i)*binomial(n,i)
*binomial(n+i,i-1)
/(2*i+1),i,1,n)
sum_by_parts returns
'sum((-1)^(n+i)*binomial(n,i)*binomial(n+i,i-1)
/(2*i+1),i,1,n)
Trying with integral representation.
1 Enter ?subst
[?g16681,i,(-1)^(n+i)*binomial(n,i)*binomial(n+i,i-1)/(2*i+1)]
1 Exit  ?subst
(1+2*?g16681)^-1*(-1)^(?g16681+n)*binomial(n,?g16681)
*binomial(?g16681+n,-1+?g16681)
1 Enter ?subst
[i,?g16681,
binomial(n,?g16681)*(-1)^(?g16681+n)*binomial(?g16681+n,?g16681-1)
/(2*?g16681+1)]
1 Exit  ?subst (-1)^(n+i)*binomial(n,i)*binomial(n+i,i-1)/(2*i+1)
Trying with Gosper ...
Trying with extended Gosper ...
Trying with Zeilberger ...
1 Enter ?subst
[?g17083,i,(-1)^(n+i)*binomial(n,i)*binomial(n+i,i-1)/(2*i+1)]
1 Exit  ?subst
(1+2*?g17083)^-1*(-1)^(?g17083+n)*binomial(n,?g17083)
*binomial(?g17083+n,-1+?g17083)
1 Enter ?subst
[i,?g17083,
binomial(n,?g17083)*(-1)^(?g17083+n)*binomial(?g17083+n,?g17083-1)
/(2*?g17083+1)]
1 Exit  ?subst (-1)^(n+i)*binomial(n,i)*binomial(n+i,i-1)/(2*i+1)
Summand:
-(-1)^(n+g17074)*binomial(n,g17074+1)
*binomial(n+g17074+1,g17074)
/(2*g17074+3)
Changed to:
-(-1)^(n+g17074)*(n+g17074+1)!
/((g17074+1)*(2*g17074+3)*g17074!^2*(n+1)*(n-g17074-1)!)
Found support: [-1,n]
1 Enter ?subst [n+1,n,n+1]
1 Exit  ?subst n+2
1 Enter ?subst [n,n,-(n+1)*(n+g17074+2)/(n-g17074)]
1 Exit  ?subst -(n+1)*(n+g17074+2)/(n-g17074)
1 Enter ?subst [g17074+1,g17074,g17074+1]
1 Exit  ?subst g17074+2
1 Enter ?subst [g17074+1,g17074,2*g17074+3]
1 Exit  ?subst 2*(g17074+1)+3
1 Enter ?subst [g17074+1,g17074,n-g17074]
1 Exit  ?subst n-g17074-1
1 Enter ?subst [g17074-1,g17074,(g17074+1)*(g17074+2)*(g17074+5/2)]
1 Exit  ?subst g17074*(g17074+1)*(g17074+3/2)
1 Enter ?subst [g17074+1,g17074,_g[0]]
1 Exit  ?subst _g[0]
1 Enter ?subst [n+1,n,n+1]
1 Exit  ?subst n+2
1 Enter ?subst [n+1,n,-(n+1)*(n+g17074+2)/(n-g17074)]
1 Exit  ?subst -(n+2)*(n+g17074+3)/(n-g17074+1)
1 Enter ?subst [n,n,-(n+1)*(n+g17074+2)/(n-g17074)]
1 Exit  ?subst -(n+1)*(n+g17074+2)/(n-g17074)
1 Enter ?subst [g17074+1,g17074,g17074+1]
1 Exit  ?subst g17074+2
1 Enter ?subst [g17074+1,g17074,2*g17074+3]
1 Exit  ?subst 2*(g17074+1)+3
1 Enter ?subst [g17074+1,g17074,n-g17074]
1 Exit  ?subst n-g17074-1
1 Enter ?subst [g17074+1,g17074,n-g17074+1]
1 Exit  ?subst n-g17074
1 Enter ?subst [g17074-1,g17074,(g17074+1)*(g17074+2)*(g17074+5/2)]
1 Exit  ?subst g17074*(g17074+1)*(g17074+3/2)
1 Enter ?subst [g17074+1,g17074,_g[0]]
1 Exit  ?subst _g[0]
1 Enter ?subst
[1,%r1,
[_g[0] = -(4*%r1*n^2+14*%r1*n+12*%r1)/(2*n+5),
_z[0] = -(2*%r1*n^3+9*%r1*n^2+12*%r1*n+4*%r1)/(2*n+5),
_z[1] = -(2*%r1*n^2+7*%r1*n+6*%r1)/(2*n^2+7*n+5),_z[2] = %r1]]
1 Exit  ?subst
[_g[0] = -(4*n^2+14*n+12)/(2*n+5),
_z[0] = -(2*n^3+9*n^2+12*n+4)/(2*n+5),
_z[1] = -(2*n^2+7*n+6)/(2*n^2+7*n+5),_z[2] = 1]
1 Enter ?subst [n+1,n,n+2]
1 Exit  ?subst n+3
1 Enter ?subst [n,n,n+2]
1 Exit  ?subst n+2
1 Enter ?subst [n,n,1]
1 Exit  ?subst 1
1 Enter ?subst [n+1,n,n+2]
1 Exit  ?subst n+3
1 Enter ?subst [n,n,1]
1 Exit  ?subst 1
1 Enter ?subst [n+1,n,1]
1 Exit  ?subst 1
1 Enter ?subst [n,n,n+2]
1 Exit  ?subst n+2
1 Enter ?subst [n+1,n,n+2]
1 Exit  ?subst n+3
Zeilberger returns:
[[-2*g17074*(g17074+1)*(2*g17074+3)*(n+1)*(2*n+3)
/((n-g17074)*(n-g17074+1)),
[-(n+1)*(n+2)*(2*n+1),-(n+2)*(2*n+3),
(n+1)*(n+3)*(2*n+5)]]]
1 Enter ?subst [n = 0,1]
1 Exit  ?subst 1
1 Enter ?subst [n = 0,1]
1 Exit  ?subst 1
1 Enter ?subst
[?g17730,g17074,
-(-1)^(n+g17074)*binomial(n,g17074+1)*binomial(n+g17074+1,g17074)
/(2*g17074+3)]
1 Exit  ?subst
(-1)*(3+2*?g17730)^-1*(-1)^(?g17730+n)*binomial(n,1+?g17730)
*binomial(1+?g17730+n,?g17730)
1 Enter ?subst
[g17074,?g17730,
-binomial(n,?g17730+1)*(-1)^(?g17730+n)*binomial(?g17730+n+1,?g17730)
/(2*?g17730+3)]
1 Exit  ?subst
-(-1)^(n+g17074)*binomial(n,g17074+1)*binomial(n+g17074+1,g17074)
/(2*g17074+3)
1 Enter ?subst
[n = 0,
-'sum((-1)^(n+g17074)*binomial(n,g17074+1)*binomial(n+g17074+1,g17074)
/(2*g17074+3),g17074,0,n-1)]
1 Exit  ?subst 0
1 Enter ?subst
[?g17797,g17074,
-(-1)^(n+g17074)*binomial(n,g17074+1)*binomial(n+g17074+1,g17074)
/(2*g17074+3)]
1 Exit  ?subst
(-1)*(3+2*?g17797)^-1*(-1)^(?g17797+n)*binomial(n,1+?g17797)
*binomial(1+?g17797+n,?g17797)
1 Enter ?subst
[g17074,?g17797,
-binomial(n,?g17797+1)*(-1)^(?g17797+n)*binomial(?g17797+n+1,?g17797)
/(2*?g17797+3)]
1 Exit  ?subst
-(-1)^(n+g17074)*binomial(n,g17074+1)*binomial(n+g17074+1,g17074)
/(2*g17074+3)
1 Enter ?subst
[n = 1,
-'sum((-1)^(n+g17074)*binomial(n,g17074+1)*binomial(n+g17074+1,g17074)
/(2*g17074+3),g17074,0,n-1)]
1 Exit  ?subst
-('sum(binomial(1,g17074+1)*(g17074+1)*(g17074+2)*(-1)^(g17074+1)
/(2*g17074+3),g17074,0,0))
/2
Trying with simpsum=true ...
sum with simpsum=true returns: -2/3
1 Enter ?subst
[n = n,
-(-1)^(n+g17074)*binomial(n,g17074+1)*binomial(n+g17074+1,g17074)
/(2*g17074+3)]
1 Exit  ?subst
-(-1)^(n+g17074)*binomial(n,g17074+1)*binomial(n+g17074+1,g17074)
/(2*g17074+3)
1 Enter ?subst [n = n,n-1]
1 Exit  ?subst n-1
1 Enter ?subst
[n = n+1,
-(-1)^(n+g17074)*binomial(n,g17074+1)*binomial(n+g17074+1,g17074)
/(2*g17074+3)]
1 Exit  ?subst
-(-1)^(n+g17074+1)*binomial(n+1,g17074+1)*binomial(n+g17074+2,g17074)
/(2*g17074+3)
1 Enter ?subst [n = n+1,n-1]
1 Exit  ?subst n
1 Enter ?subst
[n = n+2,
-(-1)^(n+g17074)*binomial(n,g17074+1)*binomial(n+g17074+1,g17074)
/(2*g17074+3)]
1 Exit  ?subst
-(-1)^(n+g17074+2)*binomial(n+2,g17074+1)*binomial(n+g17074+3,g17074)
/(2*g17074+3)
1 Enter ?subst [n = n+2,n-1]
1 Exit  ?subst n+1
1 Enter ?subst
[g17074 = n,
2*g17074*(2*n+3)*(-1)^(n+g17074)*(n+g17074+1)!
/(g17074!^2*(n-g17074)*(n-g17074+1)*(n-g17074-1)!)]
expt: undefined: 0 to a negative exponent.
1 Enter ?subst [i = i+1,(-1)^(n+i)]
1 Exit  ?subst (-1)^(n+i+1)
1 Enter ?subst [i = i+1,0]
1 Exit  ?subst 0
1 Enter ?subst [i = i+1,binomial(n,i)]
1 Exit  ?subst binomial(n,i+1)
1 Enter ?subst
[i = i+1,(-1)^(n+i)*binomial(n,i)^2*binomial(n+i,i-1)/(2*i+1)]
1 Exit  ?subst
(-1)^(n+i+1)*binomial(n,i+1)^2*binomial(n+i+1,i)/(2*(i+1)+1)
1 Enter ?subst [i = i+1,binomial(n+i,i-1)]
1 Exit  ?subst binomial(n+i+1,i)
1 Enter ?subst
[i = i+1,(-1)^(n+i)*binomial(n,i)*binomial(n+i,i-1)^2/(2*i+1)]
1 Exit  ?subst
(-1)^(n+i+1)*binomial(n,i+1)*binomial(n+i+1,i)^2/(2*(i+1)+1)
(%o7) 'sum((-1)^(n+i)*binomial(n,i)*binomial(n+i,i-1)/(2*i+1),i,1,n)
```