3
$\begingroup$
  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. $$

Improve this question
$\endgroup$
4
  • $\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
    Commented 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$
    – Patricia Hersh
    Commented 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$
    – Patricia Hersh
    Commented 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
    Commented Oct 8, 2012 at 13:55

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, Ira! Exponential generating functions certainly do seem effective here. $\endgroup$
    – Patricia Hersh
    Commented Oct 5, 2012 at 19:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .