#369 binomial(x,x) => 1, but binomial(-1,-1) => 0

closed
nobody
5
2010-03-20
2003-08-01
No

binomial(x,x) simplifies to 1 yet binomial(-1,-1) simplifies
to 0.

(C1) binomial(x,x);
(D1) 1
(C2) binomial(-1,-1);
(D2) 0

I agree with (d2) because:

1/(1 - x) = 1 + x + x^2 + ... = sum(binomial(-1,k) (-x)
^k,k,0,inf)

implies

binomial(-1,k) = (-1)^k, for integers k >= 0.

In the recursion relation [Knuth Vol 1, 1.2.6 Eq. (20)]

binomial(r,k) = binomial(r-1,k) + binomial(r-1,k-1)

set r -> 0, k -> 0, and use binomial(0,0) = 1 and binomial
(-1,0) = 1. From this we get binomial(-1,-1) = 0. Also
see, Knuth Vol. 1 (third edition), Section 1.2.6 Exercise
9.

There may be other approaches, but I think using the
recursion relations and other identities to extend the
domain of the binomial function is the best
method.

In short, I think the simplification binomial(x,x) ==> 1
should happen only for real x with x >= 0.

Barton

Discussion

  • Stavros Macrakis

    Logged In: YES
    user_id=588346

    I am not sure what you mean by "there may be other
    approaches". binomial(a,a) should simplify to Q if and only if
    the double limit exists:

    limit binomial(x,y) = Q
    x->a
    y->a

    A necessary (but in general not sufficient) condition for this
    to exist is that the two single limits exist and are equal:

    limit binomial(a,y) = limit binomial(x,a) = Q
    y->a x->a

    If the limit is not well-defined, then binomial(x,x) is not well-
    defined, and it will cause incorrect results in some case or
    another to arbitrarily set it to some value.

    I don't know if this limit is or isn't well-defined. I do know
    that depending on identities with unspecified domains of
    validity is dangerous....

     
  • Wolfgang Jenkner

    Logged In: YES
    user_id=581700

    Unless I am mistaken, the (finite) limit of BINOMIAL(x,y) at some
    lattice-point (a,b) in Z^2 exists if and only if a >= 0.

    The "if" part is easy: Just write the binomial as

    GAMMA(x+1)/(GAMMA(-y+x+1)*GAMMA(y+1))

    and observe that Gamma is certainly continuous in the open right
    half-plane while 1/Gamma is continuous everywhere.

    Now assume a <= -1. We have the following identity (for the proof see
    the Maxima code below)

    %PI*BINOMIAL(-x-1,-y)*BINOMIAL(x,y)*y
    = SIN(%PI*y)*SIN(%PI*(x-y))/SIN(%PI*x)

    We have -a-1 >= 0, so we already know that lim BINOMIAL(-x-1,-y) for
    (x,y)->(a,b) exists. If lim BINOMIAL(x,y) also existed, lim of the
    whole left hand side expression of this identity would exist. Now,
    looking at the right hand side expression we observe that it is
    Z-periodic with respect to x and y (except for a possible sign
    change). So lim of it at (a,b) exists if and only if lim of it at
    (0,0) exists, which is clearly not the case.

    Note: Strictly speaking, the identity is valid on, say, the complement
    of the union of the parallels through lattice-points to the first and
    second axis and to the median of the first quadrant, but this leaves
    us with enough space :-)

    Nevertheless, of course, it's quite customary to define

    BINOMIAL(a,b)=a*(a-1)* ... *(a-b+1)/b!

    for all a in R and b in Z with b >= 0 (for b=0 the numerator is an
    empty product), in accordance with the binomial series. This
    definition happens to coincide with
    limit(limit(BINOMIAL(x,y),y,b),x,a).

    matchdeclare([%%u,%%v],true)$
    sum_is_1(u,v):=is(u+v = 1)$
    let(gamma(%%u)*gamma(%%v),%pi/sin(%pi*%%u),sum_is_1,%%u,%%v);
    let(%%v/gamma(%%u),1/gamma(%%v),sum_is_1,%%u,-%%v);
    letrat:true;
    lhs:%pi*y*binomial(x,y)*binomial(-x-1,-y);
    makegamma(%);
    letsimp(%);
    letsimp(%);
    num(%)/trigexpand(expand(denom(%)));
    lhs=%;

     
  • Robert Dodier

    Robert Dodier - 2006-07-08

    Logged In: YES
    user_id=501686

    If, and from the comments it appears it is not certain, we
    want to make special cases for binomial, we might get the
    desired effect by using an unevaluated conditional. E.g.
    stuff like binomial(x, x) --> if x = -1 then 0 elseif
    realp(x) and x > 0 then 1 else 'binomial(x, x). Just a thought.

     
  • Robert Dodier

    Robert Dodier - 2006-07-08
    • labels: --> Lisp Core - Simplification
    • summary: binomial(x,x) => 1, but binomial(-1,-1) => 0 --> binomial(x,x) => 1, but binomial(-1,-1) => 0
     
  • Dieter Kaiser

    Dieter Kaiser - 2010-03-13

    The following is an implementation of simpbinocoef which does not simplify binomial(x,x) to the number 1, if the sign of the argument x can be negative.

    ;; Binomial has Mirror symmetry
    (defprop %binomial t commutes-with-conjugate)

    (defun simpbinocoef (x vestigial z)
    (declare (ignore vestigial))
    (twoargcheck x)
    (let ((u (simpcheck (cadr x) z))
    (v (simpcheck (caddr x) z))
    (y))
    (cond ((integerp v)
    (cond ((minusp v)
    (if (and (integerp u) (minusp u) (< v u))
    (bincomp u (- u v))
    0))
    ((or (zerop v) (equal u v)) 1)
    ((and (integerp u) (not (minusp u)))
    (bincomp u (min v (- u v))))
    (t (bincomp u v))))
    ((integerp (setq y (sub u v)))
    (cond ((zerop1 y)
    (if (member ($csign u) '($pnz $pn $neg $nz))
    (eqtest (list '(%binomial) u v) x)
    (bincomp u y)))
    (t (bincomp u y))))
    ((complex-float-numerical-eval-p u v)
    (let (($numer t) ($float t))
    ($rectform
    ($float
    ($makegamma (list '(%binomial) ($float u) ($float v)))))))
    ((complex-bigfloat-numerical-eval-p u v)
    ($rectform
    ($bfloat
    ($makegamma (list '(%binomial) ($bfloat u) ($bfloat v))))))
    (t (eqtest (list '(%binomial) u v) x)))))

    We get the results

    (%i1) binomial(x,x);
    (%o1) binomial(x,x)

    (%i2) assume(x>0)$

    (%i3) binomial(x,x);
    (%o3) 1

    In addition the above code implements the numercial evaluation for floating point arguments more consistent and in addition for complex float and float and complex bigfloat values:

    (%i4) binomial(0.5,1/2);
    (%o4) 1.0

    (%i5) binomial(0.5,1/2+%i);
    (%o5) 2.623896851342161-1.279746064016377*%i

    (%i6) binomial(0.5b0,1/2+%i);
    (%o6) 2.62389685134216b0-1.279746064016376b0*%i

    Furthermore, the property mirror symmetry is added:

    (%i7) conjugate(binomial(1+%i,1-%i));
    (%o7) binomial(1-%i,%i+1)

    The testsuite has one changed result, because binomial(t,t) does not simplify to the number 1. t has to be declared to be positive. The share_testsuite has no problems.

    Dieter Kaiser

     
  • Dieter Kaiser

    Dieter Kaiser - 2010-03-20
    • status: open --> closed
     
  • Dieter Kaiser

    Dieter Kaiser - 2010-03-20

    Fixed in csimp2.lisp revision 1.43.binomial(x,x) no longer simplifies to 1, if the sign of x can be negative.
    Closing this bug report as fixed.
    Dieter Kaiser

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks