10
$\begingroup$

I am trying to evaluate the following finite sum:
$$ \sum_{k=1}^{n}(-1)^{k}(k-1)!S(n-1, k-1)(\sum_{i=0}^{k-1}H_{i}), $$ where $S(n, k)$ are the Stirling's numbers of the second kind and $H_{i}$ denotes the $i$ harmonic number. Could you please shed some light?

@Gerry Myerson

I think that the first few terms obey the sequence http://oeis.org/A001787 with alternating signs.

$\endgroup$
4
  • 1
    $\begingroup$ Have you tried calculating the first few to see what they look like? $\endgroup$ – Gerry Myerson Aug 23 '13 at 13:21
  • $\begingroup$ I guess the last sum should start at $i=1$? $\endgroup$ – leonbloy Aug 23 '13 at 16:38
  • $\begingroup$ Either $0$ or $1$, as $H_{0}$ is by convention $0$. $\endgroup$ – user91485 Aug 23 '13 at 21:57
  • 1
    $\begingroup$ I don't know how much this will help you, but $\sum_{i=0}^{k-1}H_{i} = k(H_k - 1)$... you can see it easily by calculating $(k+1)(H_{k+1} - 1) - k(H_k - 1)$ $\endgroup$ – ante.ceperic Aug 28 '13 at 9:54
1
$\begingroup$

It may interest the reader that this sum can be evaluated using the technique of annihilated coefficient extractors (ACE).

Start with $$q_n = \sum_{k=1}^n (-1)^k \times (k-1)! \times {n-1 \brace k-1} \times \sum_{j=0}^{k-1} H_j$$ and introduce the generating function $$Q(z) = \sum_{n\ge 1} q_n \frac{z^{n-1}}{(n-1)!}.$$

Recall the bivariate generating function of the Stirling numbers of the second kind which is $$G(z, u) = \exp(u(\exp(z)-1)).$$

Substitute this into $Q(z)$ to get $$\sum_{n\ge 1} \frac{z^{n-1}}{(n-1)!} \sum_{k=1}^n (-1)^k \times (k-1)! \times (n-1)! [z^{n-1}] \frac{(\exp(z)-1)^{k-1}}{(k-1)!} \times \sum_{j=0}^{k-1} H_j.$$

This immediately simplifies to $$\sum_{n\ge 1} z^{n-1} \sum_{k=1}^n (-1)^k \times [z^{n-1}] (\exp(z)-1)^{k-1} \times \sum_{j=0}^{k-1} H_j.$$

Switch summations to obtain $$\sum_{k\ge 1} (-1)^k \times \sum_{j=0}^{k-1} H_j \times \sum_{n\ge k} z^{n-1} [z^{n-1}] (\exp(z)-1)^{k-1}.$$

The inner sum contains the promised annihilated coefficient extractor and everything simplifies to $$\sum_{k\ge 1} (-1)^k \times \sum_{j=0}^{k-1} H_j \times (\exp(z)-1)^{k-1}.$$

Switch sums one more time to obtain $$\sum_{j\ge 0} H_j \sum_{k\ge j+1} (-1)^k (\exp(z)-1)^{k-1}$$ which is $$- \sum_{j \ge 0} H_j \frac{(1-\exp(z))^j}{1-(1-\exp(z))} = - \exp(-z) \sum_{j\ge 0} H_j \times (1-\exp(z))^j.$$

Now ask when the term $1/q$ occurs in the harmonic number $H_j = \sum_{q=1}^j 1/q$ to obtain $$- \exp(-z) \sum_{q\ge 1} \frac{1}{q} \sum_{j\ge q} (1-\exp(z))^j.$$ This is $$- \exp(-z) \sum_{q\ge 1} \frac{1}{q} \frac{(1-\exp(z))^q}{1-(1-\exp(z))} = - \exp(-2z) \sum_{q\ge 1} \frac{1}{q} (1-\exp(z))^q \\ = - \exp(-2z) \log\frac{1}{1-(1-\exp(z))} = z \times \exp(-2z).$$

We are done and we may conclude by extracting coefficients to find $$q_n = (n-1)! [z^{n-1}] \quad z \times\exp(-2z) = (n-1)! [z^{n-2}] \exp(-2z) \\ = (n-1)! \times \frac{(-1)^{n-2} 2^{n-2}}{(n-2)!} = (-1)^n \times (n-1) \times 2^{n-2}.$$

This is indeed OEIS A001787 up to signs: $$0, 1, 4, 12, 32, 80, 192, 448, 1024, 2304, 5120, 11264, 24576,\ldots$$

There is another computation with annihilated coefficient extractors at this MSE link.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks and good luck with your problem. You can always post it as a question (which I prefer) in case you don't succeed. $\endgroup$ – Marko Riedel Jun 24 '14 at 1:10
0
$\begingroup$

Your OEIS guess is correct. The trick is looking at this formula for Stirling numbers of the second kind:

$$\sum_{k = 0}^n {n \brace k} (x)_k = x^n$$

(I'm using Pochhamer symbols)

and noticing that Pochhamer symbol turns out to be really simple for some special values:

$$ (-1)_n = (-1)^n n! $$ $$ (-2)_n = (-1)^n (n+1)! \ \ \ (*)$$

This gives us a few surprising identities:

$$\sum_{k = 0}^n {n \brace k} (-1)^k k! = (-1)^n$$ $$\sum_{k = 0}^n {n \brace k} (-1)^k (k+1)! = (-2)^n$$

That's nice, but I still haven't solved your question, right? Your OEIS sequence looks like $n 2^{n-1}$ - comparing this and few last identities you see it's a derivative of some kind.

This is how harmonic numbers enter the game. Notice:

$$\frac{d}{dx} (x)_n = (x)_n \sum_{k = 0}^{n-1} \frac1{x-k}$$ (just using the multiplication formula for derivation).

Just differentiate the very first formula I wrote in this post, put $x = -2$ and use identity $(*)$!

$\endgroup$
1
  • $\begingroup$ Thank you. This is an elegant approach. $\endgroup$ – user91485 Aug 28 '13 at 23:53

Your Answer

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