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[const`hold, HoldAll];
holdConstants[expr_, v_] := Module[{factors, constants, summand},
factors = Replace[
expr,
s_Times :> FactorList /@ List @@ s] //
Flatten@Apply[Power, #, {2}] &;
If[Head[factors] === List,
{constants, summand} = Times @@@ Flatten /@ Last@Reap[
Sow[#, FreeQ[#, v]] & /@ factors,
{True, False}];
const`hold[Evaluate@constants] summand,
expr]
]
const`release = const`hold[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] *
const`hold[((-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}] /. const`release
(*
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] /. const`release &,
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 Sum`IteratedUnivariateSummation
. It is straightforward to throw in holdConstants
and const`release
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 Sum`SumParserDump`sumParserEvaluate
. 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:
? Sum`SumParserDump`sumParserEvaluate
(*
...
Sum`SumParserDump`sumParserEvaluate[(-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 Sum`IteratedUnivariateSummation
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.