MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
  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. $$

share|cite|improve this question
You should go to Stack Exchange where more or less the same question has already been discussed:… – Nick Gill Oct 5 '12 at 10:14
@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. – Patricia Hersh Oct 5 '12 at 11:04
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. – Patricia Hersh Oct 5 '12 at 15:06
Patricia, you're quite right, I commented in haste and I shall now repent at leisure... – Nick Gill Oct 8 '12 at 13:55
up vote 6 down vote accepted

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.

share|cite|improve this answer
Thanks, Ira! Exponential generating functions certainly do seem effective here. – Patricia Hersh Oct 5 '12 at 19:30
Thank you! It was absolutely great! – Melania Oct 5 '12 at 22:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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