Symbolic sum of Stirling numbers gives wrong answer

Question

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}]

gives the correct answer 1.

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$.

Answer 1

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  *)

Answer 2

(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

Answer 3

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.