# Strange evaluation of an sum involving binomial coefficients

I stumbled upon this problem while playing with Mathematica 10. Can anyone help me explain the following behaviour?

I define a sum

f[m_] :=
Sum[
Binomial[m - 1, r] Binomial[r, a] Binomial[m - r - 1, b]
z^(r + b) (-1)^(a + b + r + 1),
{r, 0, m - 1}, {a, 0, r}, {b, 0, m - r - 1}]


Now evaluating f[3] gives -(-1 + z)^2 after simplifying. However, evaluating f[m] for unassigned m gives 0, but I expected (-1)^m (-1 + z)^(m - 1). I traced the computation with

Trace[f[m]]


and the trace returned a list of evaluations which only makes a rearrangement of the sum into canonical form; that is, the last two elements in the trace output are simply my defined sum expression in canonical form followed by 0. I am pretty confused by Mathematica's final evaluation to 0.

Edit: corrected a typo -(-1 + z)^(m - 1) to (-1)^m (-1 + z)^(m - 1).

• Isn't the right answer $(-1)^{m}(-1+z)^{(m-1)}$? – Mahdi Apr 3 '15 at 8:02
• You are right. Sorry, that was a typo. – Cai Thinh Apr 3 '15 at 8:22
• Seems to be a bug? – Alexei Boulbitch Aug 10 '15 at 8:11

This question is a little like Need to take infinite sum of residues, is there a way to choose the order of operations for ReleaseHold?. It also reminds me a little of Why does Mathematica simplify $x/x\to1$?, in which the symbolic result is generically true.

### Analysis

The method used in the sum is

Method -> "IteratedSummation"


so we can examine the major steps:

Sum[
Binomial[m - 1, r] Binomial[r, a] Binomial[m - r - 1, b] z^(r + b) (-1)^(a + b + r + 1),
{b, 0, m - r - 1}]
Sum[%, {a, 0, r}]
Sum[%, {r, 0, m - 1}]
(*
((-1)^(2 + a + r) (1 - z)^(m - r) z^r Binomial[-1 + m, r] Binomial[r, a])/(-1 + z)
0
0
*)


The second result is a bit mysterious as fundamentally the sum is equivalent to

Sum[(-1)^a const Binomial[r, a], {a, 0, r}]
(*  const KroneckerDelta[r]  *)


which is no problem. So Mathematica, at some point, must not be able to disentangle the constants from the important factors. We can try simplifying it. Each of these yields 0.

Sum[(-1)^(2 + a + r) (1 - z)^(m - r) z^r Binomial[-1 + m, r] Binomial[r, a] /.
(1 - z)^(m - r) z^r -> u,
{a, 0, r}]
Sum[(-1)^(2 + a + r) (1 - z)^(m - r)(*z^r*) Binomial[-1 + m, r] Binomial[r, a] /.
(1 - z)^(m - r) z^r -> u,
{a, 0, r}]


Curiously each of the following yields a correct result, unfortunately in terms of HypergeometricPFQ. The first one is quite similar to last one above. It's unfortunate in that if we plug them back into Sum to complete the calculation, Sum returns unevaluated. Strictly speaking the HypergeometricPFQ term is only equivalent to KroneckerDelta[r] if r is an integer and r >= 0; but Mathematica seems not to be able to do that transformation.

Sum[(-1)^(2 + a + r)(*(1-z)^(m-r)*)z^r Binomial[-1 + m, r] Binomial[r, a],
{a, 0, r}]
Sum[(-1)^(2 + a + r) (1 - z)^(m - r) z^r Binomial[-1 + m, r] Binomial[r, a] /.
(1 - z)^(m - r) z^r -> u[r],
{a, 0, r}]
(*
(-1)^r z^r Binomial[-1 + m, r] HypergeometricPFQ[{-r}, {}, 1]
(-1)^r Binomial[-1 + m, r] HypergeometricPFQ[{-r}, {}, 1] u[r]
*)


### Working around the limitations

One workaround is to wrap the constants up in a nice package as a single constant. The the summation will be computed correctly. One could also factor the constants out of the sum, such as is done here (or here on Integrate instead of Sum).

We can make a Hold-like wrapper, do the sum, and release the hold. I decided not to use Hold itself, because ReleaseHold might release other instances of Hold that happen to be there.

SetAttributes[consthold, HoldAll];
holdConstants[expr_, v_] := Module[{factors, constants, summand},
factors = Replace[
expr,
s_Times :> FactorList /@ List @@ s] //
Flatten@Apply[Power, #, {2}] &;
{constants, summand} = Times @@@ Flatten /@ Last@Reap[
Sow[#, FreeQ[#, v]] & /@ factors,
{True, False}];
consthold[Evaluate@constants] summand,
expr]
]
constrelease = consthold[c_] :> c;


Example:

It's the second iterated sum that is the problem. Below s1 is the first iterated sum and we show the effect of holdConstants on it and its sum over a.

s1 = Sum[
Binomial[m - 1, r] Binomial[r, a] Binomial[m - r - 1, b] z^(r + b) (-1)^(a + b + r + 1),
{b, 0, m - r - 1}];
holdConstants[s1, a]
(*
(-1)^a Binomial[r, a] *
consthold[((-1)^r (1 - z)^(m - r) z^r Binomial[-1 + m, r])/(-1 + z)]
*)

Sum[s1, {a, 0, r}]
s2 = Sum[holdConstants[s1, a], {a, 0, r}] /. constrelease
(*
0
((-1)^r (1 - z)^(m - r) z^r Binomial[-1 + m, r] KroneckerDelta[r])/(-1 + z)
*)


From here we can get the answer:

s3 = Sum[s2, {r, 0, m - 1}]
(*
-(1 - z)^(-1 + m)
*)


### General workaround

ClearAll[withHeldConstants];
SetAttributes[withHeldConstants, HoldAll];
withHeldConstants[Sum[summand_, iterators__]] :=
Fold[Sum[holdConstants[#, First[#2]], #2] /. constrelease &,
summand, Reverse@{iterators}]

withHeldConstants[
Sum[
Binomial[m - 1, r] Binomial[r, a] Binomial[m - r - 1, b] z^(r + b) (-1)^(a + b + r + 1),
{r, 0, m - 1}, {a, 0, r}, {b, 0, m - r - 1}]]
Simplify[%]
(*
(1 - z)^m/(-1 + z)
-(1 - z)^(-1 + m)
*)


Braver folks may fiddle with the internals. The function to hack for the OP's sum is SumIteratedUnivariateSummation. It is straightforward to throw in holdConstants and constrelease into its code. One thing to beware of, aside from making a mistake and screwing up your kernel session, is that some sums are cached in SumSumParserDumpsumParserEvaluate. It turns out that the OP's is. The cached value is used in future calls. For instance, if you ran the OP's code, you should find this among the definitions:

? SumSumParserDumpsumParserEvaluate
(*
...
SumSumParserDumpsumParserEvaluate[(-1)^(1 + a + b + r) z^(b + r)
Binomial[-1 + m, r] Binomial[-1 + m - r, b] Binomial[r, a], {{r,
0, -1 + m}, {a, 0, r}, {b, 0, -1 + m - r}}, {}] = 0
...
*)


You might need to Unset this definition when you fiddle with SumIteratedUnivariateSummation to see a change take effect.

I was unable to find a system call that resets the summation cache. Normally, there would be no need for it. I think withHeldConstants is a better alternative, but I wanted to record the location of the cache (at least in V9/10), so in the future, if others go trying to help Sum out, they can see if the cached results are thwarting their efforts.

### Is it a bug?

Or just a limitation? You'd think factoring out the constants, which is a first-year student technique, would not be hard to do. Maybe I'm missing something.

I suspect that it relates to convergence. Here are some experiments which may give a clue to that.

Sum[Binomial[m - r - 1, b] z^(r + b) (-1)^(a + b + r + 1), {b, 0, m - r - 1, 1}, GenerateConditions -> True]
ConditionalExpression[((-1)^(a + r) (1 - z)^(m - r) z^r)/(-1 + z), m - r \[Element] Integers && (z != 1 || Re[m - r] > 1) && m >= 1 + r]

Sum[Binomial[r, a] Sum[Binomial[m - r - 1, b] z^(r + b) (-1)^(a + b + r + 1), {b, 0, m - r - 1, 1}], {a, 0, r}, GenerateConditions -> True]
ConditionalExpression[0, r \[Element] Integers && r > 0]

Sum[Binomial[r, a] Sum[Binomial[m - r - 1, b] z^(r + b) (-1)^(a + b + r + 1), {b, 0, m - r - 1, 1}, GenerateConditions -> True], {a, 0, r}, GenerateConditions -> True]
ConditionalExpression[0, m - r \[Element] Integers && (z != 1 || Re[m - r] > 1) && m >= 1 + r && r \[Element] Integers && r > 0]

Sum[Binomial[m - 1, r] Binomial[r, a] Binomial[m - r - 1, b] z^(r + b) (-1)^(a + b + r + 1), {r, 0, m - 1, 1}, {a, 0, r, 1}, {b, 0, m - r - 1, 1}, GenerateConditions -> True]
0

Sum[ Binomial[r, a] (((-1)^(a + r) (1 - z)^(m - r) z^r)/(-1 + z)), {a, 0,   r}, GenerateConditions -> True]
ConditionalExpression[0, r \[Element] Integers && r > 0]

-(1 - z)^(m - r - 1) (-z)^r Sum[ Binomial[r, a] (-1)^a , {a, 0, r}, GenerateConditions -> True]
ConditionalExpression[-(1 - z)^(-1 + m - r) (-z)^r KroneckerDelta[r], r \[Element] Integers && r >= 0]