Closed form of $ \sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k}2^k k^m$?

200 Views Asked by At

Is there a closed form of the above equation or something that simplifies it? Here is the same equation copied:

$$\sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k}2^k k^m$$

It looks very similar to the Stirling number of the 2nd kind but slightly modified, which looks like this:

$$S(m,n)=\frac{1}{n!}\sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k} k^m$$

4

There are 4 best solutions below

0
On

For each fixed $m$ this sum is hypergeometric, and so computers can solve for a closed form (or tell us that none exists). You can read more in the excellent book $A=B$, which the authors have made freely available at that link.

Now we can start solving these for fixed values of $m$ (by asking sage, say) and we get

$$ \begin{array}{|c|l|} \hline m & S(m) \\ \hline 1 & 2 \, n\\ \hline 2 & 4 \, n^{2} - 2 \, n\\ \hline 3 & 8 \, n^{3} - 12 \, n^{2} + 6 \, n\\ \hline 4 & 16 \, n^{4} - 48 \, n^{3} + 60 \, n^{2} - 26 \, n\\ \hline 5 & 32 \, n^{5} - 160 \, n^{4} + 360 \, n^{3} - 380 \, n^{2} + 150 \, n\\ \hline \vdots & \vdots \\ \hline \end{array} $$

It's not hard to see that $S(m) = (2n)^m + O(n^{m-1})$, and the OEIS lets us push this slightly further. Indeed, the sequence of second order terms, $2,12,48,160,\ldots$ seems to be A001815, which tells us that (probably -- I haven't tried to prove this)

$$S(m) = 2^m n^m - 2^{m-2} m (m-1) n^{m-1} + O(n^{m-2})$$

You can also look at the sequence of linear terms $2,-2,6,-26,150,\ldots$, which is (up to sign) A076726. Unfortunately this doesn't seem to have a nice closed form in terms of $m$. You can probably push this farther with some effort, but naively neither the sequence of third terms $6,60,360,1680,6720\ldots$ or the sequence of quadratic terms $4,-12,60,-380,2940,\ldots$ is in the OEIS. Because of this (and the lack of closed form for the linear terms), my guess is that getting a closed form parameterized by $m$ is going to be quite hard, if it's possible at all. Thankfully, for lots of purposes being able to get a closed form for each fixed $m$ is good enough!


I hope this helps ^_^

1
On

Rewriting with the Pochhammer symbol:

$$\sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k}x^k k^m= (-1)^n\sum_{k=0}^{n}\frac{(2)_{k-1}^m}{(1)_{k-1}^m}\binom{n}{k}(-x)^k $$

helps Wolfram Alpha use the hypergeometric function:

$$\boxed{\sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k}x^k k^m=-(-1)^nxn\,_{m+1}\operatorname F_m(2,\dots,2,1-n;1,\dots 1,2;x),m\in\Bbb N}$$

with $m$$2$”s and $m-1$$1$”s. Also applying a $\binom n k$ integral representation, valid for the variable ranges in the sum, uses the polylogarithm $\operatorname{Li}_v(x)$ and Lerch transcendent $\Phi(z,s,a)$:

$$\sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k}x^k k^m=\frac{(-1)^n}{2\pi}\int_{-\pi}^\pi (e^{it}+1)^n\left(\operatorname{Li}_{-m}\left(-x e^{-i t}\right)-(-x e^{-i t})^{n+1}\Phi\left(-x e^{-i t},-m,n+1\right)\right)dt$$

0
On

I wonder if the $2$ does not hide simpler thing (may be simpler to analyze).

Considering instead $$S(m,n,x)=\sum_{k=0}^{n} (-1)^{n-k}\,\binom{n}{k}\,x^k\, k^m$$ for $m>0$ we have $$S(m,n,x)=n\,x\,(x-1)^{n-m}\,T(m,y,x)\qquad \text{with} \qquad y=n x$$

$$\left( \begin{array}{cc} 1 & 1 \\ 2 & y-1 \\ 3 & y^2-3 y+(x+1)\\ 4 & y^3-6 y^2+(4 x+7) y-\left(x^2+4x+1)\right) \\ 5 & y^4-10 y^3+(10 x+25) y^2-\left(5 x^2+30 x+15\right) y+\left(x^3+11 x^2+11x+1\right)\\ \end{array} \right)$$

0
On

We seek to simplify

$$\sum_{k=0}^n (-1)^{n-k} {n\choose k} 2^k k^m.$$

This is

$$m! [z^m] \sum_{k=0}^n (-1)^{n-k} {n\choose k} 2^k \exp(kz) \\ = m! [z^m] (-1+2\exp(z))^n = m! [z^m] (1+2(\exp(z)-1))^n \\ = m! [z^m] \sum_{q=0}^n {n\choose q} 2^q (\exp(z)-1)^q \\ = \sum_{q=0}^n {n\choose q} 2^q q! {m\brace q}.$$

Now note that when $n\gt m$ we may lower the upper range to $m$ because the Stirling number is zero on the omitted values. On the other hand when $n\lt m$ we may raise to $m$ because the binomial coefficient is zero in the added range. We finally obtain

$$\bbox[5px,border:2px solid #00A000]{ \sum_{q=0}^m n^{\underline{q}} 2^q {m\brace q}.}$$

For example with $m=3$ we find

$$n^{\underline{0}} 2^0 {3\brace 0} + n^{\underline{1}} 2^1 {3\brace 1} + n^{\underline{2}} 2^2 {3\brace 2} + n^{\underline{3}} 2^3 {3\brace 3} \\ = 0 + 2n + 12n(n-1) + 8n(n-1)(n-2) \\ = 8 n^3 - 12 n^2 + 6 n.$$

We have with $m=4$

$$n^{\underline{0}} 2^0 {4\brace 0} + n^{\underline{1}} 2^1 {4\brace 1} + n^{\underline{2}} 2^2 {4\brace 2} + n^{\underline{3}} 2^3 {4\brace 3} + n^{\underline{4}} 2^4 {4\brace 4} \\ = 0 + 2n + 28n(n-1) + 48n(n-1)(n-2) + 16n(n-1)(n-2)(n-3) \\ = 16 n^4 - 48 n^3 + 60 n^2 - 26 n.$$

This computation was suggested in the comments and the other answers. It goes through with $m=0$ as well.