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

Close

#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)
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.
(%i1) display2d : false $
(%i2) linel : 72 $
(%i3) load (simplify_sum) $
(%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)

Discussion