Finite sum related to Stirling numbers

Question

I am wondering if there is a closed form solution for the following sum: $$ \sum _{k =0}^{n-1} \frac{(-1)^{k} (n-k)^{n+1} }{(k+1)(k+2)}\binom{n}{k}. $$

If the the factors $(k+1)(k+2)$ in the denominator weren't there, the sum would equal $n!S(n+1,n)$, where $S(n,m)$ denotes a Stirling number of the second kind. This made me wonder if 'Stirling polynomials' of the form $$ \mathcal{S}(x)=\sum _{k =0}^{n-1} (n-k)^{n+1}\binom{n}{k}x^k $$ admit a closed form solution. The value of my sum could then be obtained by integrating $\mathcal{S}$ twice.

Any other strategy to evaluate the sum are also very welcome.

Answer 1

Re-write your sum as follows: $$\sum_{k=0}^n {n\choose k} \frac{(-1)^k}{(k+1)(k+2)} (n-k)^{n+1}.$$

Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Now in the present case we clearly have $$A(z) = \sum_{q\ge 0} \frac{(-1)^q}{(q+1)(q+2)} \frac{z^q}{q!} = \frac{1}{z^2} \sum_{q\ge 0} (-1)^{q+2} \frac{z^{q+2}}{(q+2)!} = \frac{1}{z^2} \left(\exp(-z) - 1 + z \right).$$ Furthermore we also have $$B(z) = \sum_{q\ge 0} q^{n+1} \frac{z^q}{q!} = \exp(z) \sum_{k=1}^{n+1} {n+1\brace k} z^k.$$

It follows that the sum is given by $$n![z^n] A(z) B(z) =n! [z^n] \frac{1}{z^2} \left(1 - \exp(z) + z\exp(z)\right) \sum_{k=1}^{n+1} {n+1\brace k} z^k$$ This becomes $$n! [z^{n+2}] \left(\sum_{k=1}^{n+1} {n+1\brace k} z^k - \exp(z) \sum_{k=1}^{n+1} {n+1\brace k} z^k + z\exp(z) \sum_{k=1}^{n+1} {n+1\brace k} z^k\right)$$ which is $$n! \left( - \sum_{k=1}^{n+1} {n+1\brace k} \frac{1}{(n+2-k)!} + \sum_{k=1}^{n+1} {n+1\brace k} \frac{1}{(n+1-k)!} \right)$$ which further simplifies to $$n! \sum_{k=1}^{n+1} {n+1\brace k} \frac{n+1-k}{(n+2-k)!}.$$

The proof for the closed form of $B(z)$ is by induction and quite simple, I posted it at this MSE link.

Answer 2

We can get a better closed form using a different technique.

Suppose we seek to evaluate $$\sum_{k=0}^{n-1} \frac{(-1)^k(n-k)^{n+1}}{(k+1)(k+2)} {n\choose k}.$$

This is $$\frac{1}{(n+2)(n+1)} \sum_{k=0}^{n-1} (-1)^k (n-k)^{n+1} {n+2\choose k+2} \\ = \frac{1}{(n+2)(n+1)} \sum_{k=0}^{n-1} (-1)^{k+2} (n+2-(k+2))^{n+1} {n+2\choose k+2} \\ = \frac{1}{(n+2)(n+1)} \sum_{k=2}^{n+1} (-1)^{k} (n+2-k)^{n+1} {n+2\choose k} \\ = -\frac{(n+2)^n}{n+1} + (n+1)^n + \frac{1}{(n+2)(n+1)} \sum_{k=0}^{n+2} (-1)^{k} (n+2-k)^{n+1} {n+2\choose k}.$$

Restrict to the sum for a moment and introduce $$(n+2-k)^{n+1} = \frac{(n+1)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+2}} \exp((n+2-k)z) \; dz.$$

Observe that this is zero when $k=n+2$ which is the correct value. We get for the sum $$\frac{n!}{(n+2)\times 2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+2}} \exp((n+2)z) \sum_{k=0}^{n+2} (-1)^{k} {n+2\choose k} \exp(-kz) \; dz \\ = \frac{n!}{(n+2)\times 2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+2}} \exp((n+2)z) (1-\exp(-z))^{n+2} \; dz \\ = \frac{n!}{(n+2)\times 2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+2}} (\exp(z)-1)^{n+2} \; dz$$

This is $$\frac{n!}{(n+2)} [z^{n+1}] (\exp(z)-1)^{n+2} = 0$$ because $\exp(z)-1 = z +\frac{1}{2} z^2 + \frac{1}{6} z^3+\cdots.$

We conclude that the initial sum is equal to $$-\frac{(n+2)^n}{n+1} + (n+1)^n.$$