Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
  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|improve this question
    
You should go to Stack Exchange where more or less the same question has already been discussed: math.stackexchange.com/questions/39042/… –  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
1  
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
add comment

1 Answer 1

up vote 4 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|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
add comment

Your Answer

 
discard

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.