15
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I can confirm the bug on Mma 9.0.1, 10.1.0 and 10.2.0 Windows 7 SP1 64 bit. $\endgroup$ – rhermans Oct 9 '15 at 12:41
  • 1
    $\begingroup$ This bug is present in 10.0 and 10.2 for Linux as well. $\endgroup$ – Jason B. Oct 9 '15 at 12:44
  • 1
    $\begingroup$ Also present in 10.2 on OS X. $\endgroup$ – shrx Oct 9 '15 at 12:45
  • 1
    $\begingroup$ Wolfram alpha too. $\endgroup$ – rhermans Oct 9 '15 at 12:46
  • 2
    $\begingroup$ 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. $\endgroup$ – Devendra Kapadia Oct 9 '15 at 20:47
7
$\begingroup$

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  *)
$\endgroup$
5
$\begingroup$

(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
$\endgroup$
-1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.