1. Put $B(n,k)=k! S(n,k)$, here $S(n,k)$ be the Srirling numbers of second kind.

Prove that $$ \sum_{j=i+1}^n \frac{(-1)^{j+1-i}}{j-i} B(n,j)= n B(n-1,i),i=0,1,\ldots,n-1 $$

  1. Put $T(n,i)=\displaystyle \sum_{j=i}^n (-1)^{j-i} 2^{n-j} B(n,j) {j-1 \choose i-1}$.

Prove that

$$ \sum_{j=i+1}^n \frac{1-(-1)^{j-i}}{2(j-i)}T(n,j)= n T(n-1,i),i=0 \ldots n-1. $$

  • $\begingroup$ You should go to Stack Exchange where more or less the same question has already been discussed: math.stackexchange.com/questions/39042/… $\endgroup$
    – Nick Gill
    Oct 5, 2012 at 10:14
  • 1
    $\begingroup$ @Nick: To me this question Melania has asked looks a lot harder than the one you link. The way I'd try to attack the above (given my bias towards topological combinatorics) is to try to define posets with these alternating sums as their Moebius functions and try to find a lexicographic shelling for the posets so that the simplified formulas are counting descending chains. But the denominators make this seem very tricky. Without the denominator interferance, the first alternating sum would be (up to some shifting) the Euler characteristic of a skeleta of a type A Coxeter complex. $\endgroup$ Oct 5, 2012 at 11:04
  • 1
    $\begingroup$ Maybe I should ask if I'm missing something -- at least I didn't see how to do this easily. It seemed like the recurrence to which Nick refers (and which I've taught in my combinatorics class) involves letting $n$ grow, whereas this question is more about letting $k$ grow. $\endgroup$ Oct 5, 2012 at 15:06
  • $\begingroup$ Patricia, you're quite right, I commented in haste and I shall now repent at leisure... $\endgroup$
    – Nick Gill
    Oct 8, 2012 at 13:55

1 Answer 1


Here is a proof of the first formula. We use the exponential generating function $\sum_{n=0}^\infty S(n,k) x^n/n! = (e^x-1)^k/k!$.

Multiply the left side by $x^n/n!$ and sum on $n$ from 1 to $\infty$. We obtain \begin{align*} \sum_{j=i+1}^\infty\frac{(-1)^{j+1-i}}{j-i} (e^x-1)^j &=\sum_{k=1}^\infty \frac{(-1)^{k-1}}{k}(e^x-1)^{i+k}\\ &=(e^x-1)^i \sum_{k=1}^\infty \frac{(-1)^{k-1}}{k}(e^x-1)^{k}\\ &=(e^x-1)^i\log(1+(e^x-1))= x(e^x-1)^i\\ &=\sum_{n=1}^\infty n\cdot i!\, S(n-1,i)\frac{x^n}{n!}. \end{align*}

It seems likely that a similar approach will work for the second formula, but I have not tried it.

  • $\begingroup$ Thanks, Ira! Exponential generating functions certainly do seem effective here. $\endgroup$ Oct 5, 2012 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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