## #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 &gt;= 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 -&gt; 0, k -&gt; 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) ==&gt; 1
should happen only for real x with x &gt;= 0.

Barton

## Discussion

• Stavros Macrakis - 2003-08-14

Logged In: YES
user_id=588346

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

limit binomial(x,y) = Q
x-&gt;a
y-&gt;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-&gt;a x-&gt;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 - 2003-08-22

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 &gt;= 0.

The &quot;if&quot; 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 &lt;= -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 &gt;= 0, so we already know that lim BINOMIAL(-x-1,-y) for
(x,y)-&gt;(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 &gt;= 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 - 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 - 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 - 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))
(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 - 2010-03-20
• status: open --> closed

• 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