# Symbolic sum of Stirling numbers gives wrong answer

Bug introduced in 9.0.1 or earlier and fixed in 10.4.1

This issue originated from my attempt to answer a question on MathOverflow:

 Sum[StirlingS2[i, 2], {i, 0, n}]


on Mathematica 10.2.0.0 gives as answer $\frac{1}{2} (-3 + 2^{1 + n} - 2 n)$, while the correct answer is $\frac{1}{2} (1-3 + 2^{1 + n} - 2 n)$; the error appears only in the symbolic sum, for example, setting $n=2$:

 Sum[StirlingS2[i, 2], {i, 0, 2}]


The contradiction can also be seen plainly by

Sum[StirlingS2[i, 2], {i, 0, n}]
Sum[StirlingS2[i, 2], {i, 1, n}]
StirlingS2[0, 2]

Out[1]= 1/2 (-3 + 2^(1 + n) - 2 n
Out[2]= -1 + 2^n - n
Out[3]= 0


If the last output is correct, the two summations should be the same.

I did not encounter an error in the evaluation of Sum[StirlingS2[i, m], {i, 0, n}] for any $m\neq2$.

• I can confirm the bug on Mma 9.0.1, 10.1.0 and 10.2.0 Windows 7 SP1 64 bit. – rhermans Oct 9 '15 at 12:41
• This bug is present in 10.0 and 10.2 for Linux as well. – Jason B. Oct 9 '15 at 12:44
• Also present in 10.2 on OS X. – shrx Oct 9 '15 at 12:45
• Wolfram alpha too. – rhermans Oct 9 '15 at 12:46
• This is a bug in Sum. The problem is caused by an internal transformation of StirlingS2[i, 2] which is valid only if i>=1. This leads to the incorrect result for the sum starting at i=0. Sorry for the confusion. – Devendra Kapadia Oct 9 '15 at 20:47

As a workaround you can generate a sequence and use FindSequenceFunction

max = 10;

seq = Sum[StirlingS2[i, 2], {i, 0, #}] & /@
Range[max]

(*  {0, 1, 4, 11, 26, 57, 120, 247, 502, 1013}  *)

f[n_] = FindSequenceFunction[seq][n] //
Simplify

(*  -1 + 2^n - n  *)

seq === (f /@ Range[max])

(*  True  *)


(This is a comment that got too long.)

As Devendra notes,

This is a bug in Sum. The problem is caused by an internal transformation of StirlingS2[i, 2] which is valid only if $\mathtt{i}\ge 1$. This leads to the incorrect result for the sum starting at $\mathtt{i} = 0$. Sorry for the confusion.

So,

Sum[StirlingS2[i, 2], {i, 0, n}] // Simplify (* wrong! *)
-3/2 + 2^n - n

StirlingS2[0, 2] + Sum[StirlingS2[i, 2], {i, 1, n}] (* correct *)
-1 + 2^n - n


Here's how it happened, I believe: as noted in page 258 of Concrete Mathematics, there is the identity

$$\left\{{n}\atop{2}\right\}=[n>0]\left(2^{n-1}-1\right)$$

(In Mathematica, StirlingS2[n, 2] == Boole[n > 0] (2^(n - 1) - 1).)

The error is due to the fact that

With[{n = 0}, {StirlingS2[n, 2], 2^(n - 1) - 1}]
{0, -1/2}


and this discrepancy is thus carried over to the summation:

Sum[2^(i - 1) - 1, {i, 0, n}] // Simplify
-3/2 + 2^n - n


when it should have been

Sum[2^(i - 1) - 1, {i, 1, n}] // Simplify
-1 + 2^n - n


My (minor) contribution to the question was made in a comment: @ Devendra Kapadia: Your reasoning seems to hold only for the sum of StirlingS2[2,k]. Defining s[k_,n_]:=Sum[StirlingS2[i,k],{i,0,n}] the call s[k,n] gives correct symbolic results for $k = 1$ and $k =3,4,...$ but $n = 2$ fails.

Here I'd like to discuss briefly a spin-off of the problem.

Bob Hanlon suggested to find the correct symbolic formula using FindSequenceFunction[].

This works out correctly and quickly for the general case as well, and studying it leads to an interesting connection to a well known number theoretical function, the (von) Mangoldt function.

Define

s[k_, n_] := Sum[StirlingS2[i, k], {i, 0, n}]


Let us find the general symbolic formula using Bob Hanlon's procedure for the first few Terms:

t = Table[
FindSequenceFunction[s[k, #] & /@ Range[30]][n], {k, 1, 10}]

(* Out[10]=
{n, -1 + 2^n - n, 1/4 (3 - 2^(2 + n) + 3^n + 2 n),
1/36 (-11 + 9 2^(1 + n) + 2^(1 + 2 n) - 3^(2 + n) - 6 n),
1/288 (25 - 3 2^(4 + n) - 2^(4 + 2 n) + 4 3^(2 + n) + 3 5^n + 12 n), (-137 +
75 2^(2 + n) + 25 2^(3 + 2 n) - 100 3^(1 + n) + 2^(2 + n) 3^(1 + n) -
3 5^(2 + n) -
60 n)/7200, (1/43200)(147 - 45 2^(3 + n) - 25 2^(4 + 2 n) + 50 3^(2 + n) -
2^(3 + n) 3^(2 + n) + 9 5^(2 + n) + 10 7^n + 60 n), (1/2116800)(-1089 +
735 2^(2 + n) + 1225 2^(2 + 2 n) + 15 2^(2 + 3 n) - 490 3^(2 + n) -
147 5^(2 + n) + 49 6^(2 + n) - 10 7^(2 + n) - 420 n), (1/33868800)(2283 -
105 2^(6 + n) - 245 2^(6 + 2 n) - 15 2^(6 + 3 n) + 3920 3^(1 + n) -
49 2^(6 + n) 3^(1 + n) + 35 3^(1 + 2 n) + 588 5^(2 + n) + 80 7^(2 + n) +
840 n), (1/914457600)(-7129 + 2835 2^(3 + n) + 2205 2^(5 + 2 n) +
405 2^(5 + 3 n) - 560 3^(4 + n) - 35 3^(4 + 2 n) - 15876 5^(1 + n) +
7 2^(3 + n) 5^(1 + n) + 49 6^(4 + n) - 720 7^(2 + n) - 2520 n)}
*)


The denominators are

Denominator /@ t

(*
Out[16]= {1, 1, 4, 36, 288, 7200, 43200, 2116800, 33868800, 914457600}
*)


This sequence is

"https://oeis.org/A180170 a(0) = 1, a(n) = n*a(n-1)*A014963(n)."

where

"https://oeis.org/A014963 exponential of Mangoldt function M(n): a(n) = 1 unless n is a prime or prime power when a(n) = that prime."

The summation of the OP as well as the Mangoldt function is not discussed in http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html.

• Please correct a typo A0A014963 -> A014963. – Vaclav Kotesovec Oct 19 '15 at 15:26
• Thanks for pointing this out to me. Correction done. – Dr. Wolfgang Hintze Oct 20 '15 at 13:41
• To whom it concers: it is always nice to know why a contribution was upvoted or, like in this case, downvoted. Thanks in advance. – Dr. Wolfgang Hintze Apr 12 '17 at 19:42