Ask Your Question
1

Incorrect symbolic sum w/binomial coefficients

asked 2021-05-20 22:55:09 +0100

Glenn Tesler gravatar image

This should give (t+1)^(n-1), but instead it gives 0:

sage: var('n k t');
sage: sum(binomial(n-1,k-1)*t^(k-1), k, 1, n)
0

A version w/o -1's works correctly:

sage: var('n k t');
sage: sum(binomial(n,k)*t^k, k, 0, n)
(t + 1)^n

With -2's, it's left unevaluated:

sage: var('n k t');
sage: sum(binomial(n-2,k-2)*t^(k-2), k, 2, n)
sum(t^(k - 2)*binomial(n - 2, k - 2), k, 2, n)

However, Mathematica and Maple can do problems like this. E.g., in Mathematica,

In[1]:= Sum[Binomial[n-2, k-2]*t^(k-2), {k, 2, n}]
Out[1]= (1 + t)^(-2 + n)

With positive offsets instead of negative offsets, it works correctly:

sage: var('n k t');
sage: sum(binomial(n+2,k+2)*t^(k+2), k, -2, n)
(t^2 + 2*t + 1)*(t + 1)^n

The result is correct, although it could be simplified better: (t + 1)^(n + 2)

Version: 'SageMath version 9.2, Release Date: 2020-10-24'

I also get the same results on http://sagecell.sagemath.org

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
2

answered 2021-05-22 12:04:02 +0100

Emmanuel Charpentier gravatar image
sage: var("t, k, n")
(t, k, n)
sage: foo = sum(binomial(n - 1, k - 1)*t^(k - 1), k, 1, n, hold=True) ; foo
sum(t^(k - 1)*binomial(n - 1, k - 1), k, 1, n)
sage: foo.unhold()
0

Problematic, indeed. Workaround : try to replace "non-atomic" symbolic expressions by variables in binomial's arguments :

sage: var("k1, n1")
(k1, n1)

But this is not a simple substitution : k is a summation variable, so it must be treated as such :

sage: bar = foo.maxima_methods().changevar(k1-(k - 1), k1, k).subs(n - 1==n1) ; bar
sum(t^k1*binomial(n1, k1), k1, 0, n1)

(You'll note that this is different from your version w/o -1...)

Now we can compute the result and express it in terms of the original variables ; since there is no summation anymore, a simple substitution suffices :

sage: bar.unhold().subs({k1:k - 1, n1:n - 1})
(t + 1)^(n - 1)

This is the same answer as Mathematica's :

sage: %%mathematica
....: Sum[Binomial[n-1, k-1]*t^(k-1), {k, 1, n}]
....: 
....: 
               -1 + n
        (1 + t)

Giac agrees :

sage: sum(t^(k - 1)*binomial(n - 1, k - 1), k, 1, n, algorithm="giac")
(t + 1)^(n - 1)

Sympy concurs, but assorts its answer of a complicated condition, not yet backtranslatable in Sage. So we treat it manually :

sage: gee = foo._sympy_().doit().simplify()
sage: gee = foo._sympy_().doit().simplify() ; gee
Piecewise(((t + 1)**(n - 1), (Abs(t) <= 1) & ((Abs(t) < 1) | (re(n) - 1 > -1)) & (Ne(t, -1) | (Abs(t) < 1) | (re(n) - 1 > 0)) & (Ne(t, -1) | (re(n) - 1 <= -1) | (re(n) - 1 > 0))), (Sum(t**k*binomial(n - 1, k - 1), (k, 1, n))/t, True))
sage: gee.args[0][0]._sage_()
(t + 1)^(n - 1)

This now Trac#31844.

HTH,

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-05-20 22:55:09 +0100

Seen: 281 times

Last updated: May 22 '21