Simplify binomial sum

Question

It is well-known that for any integer $j$ $$ \sum _{i=0}^k (-1)^{i} \binom{k}{i} (j-i)^k = k! $$ But I wonder if there's a closed form for the following sum $$ \sum _{i=j}^k (-1)^{i} \binom{k}{i} (j-i)^k $$

The following table gives the value for this $k = 1,\cdots, 6$ and $j = 0, \cdots k$.

1   0                   
2   1   0               
6   5   1   0           
24  23  12  1   0       
120 119 93  27  1   0   
720 719 662 360 58  1   0

Answer 1

Suppose we seek an alternate representation of

$$\sum_{p=q}^k (-1)^p {k\choose p} (q-p)^k.$$

This is

$$\sum_{p=0}^k (-1)^p {k\choose p} (q-p)^k - \sum_{p=0}^{q-1} (-1)^p {k\choose p} (q-p)^k.$$

We get for the first piece

$$k! [z^k] \sum_{p=0}^k (-1)^p {k\choose p} \exp((q-p)z) \\ = k! [z^k] \exp(qz) \sum_{p=0}^k (-1)^p {k\choose p} \exp(-pz) \\ = k! [z^k] \exp(qz) (1-\exp(-z))^k.$$

Now $(1-\exp(-z))^k = z^k + \cdots$ so this evaluates to $k!.$ We thus have

$$k!- \sum_{p=0}^{q-1} (-1)^p {k\choose p} (q-p)^k.$$

Using an Iverson bracket we get for the sum component

$$[w^{q-1}] \frac{1}{1-w} \sum_{p\ge 0} (-1)^p {k\choose p} (q-p)^k w^p \\ = k! [z^k] [w^{q-1}] \frac{1}{1-w} \exp(qz) (1-w\exp(-z))^k \\ = k! \;\underset{z}{\mathrm{res}}\; \frac{1}{z^{k+1}} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^q} \frac{1}{1-w} \exp(qz) (1-w\exp(-z))^k.$$

We now apply Jacobi's Residue Formula. We put $w=v \exp((1-v)u)$ and $z = (1-v)u$. The scalar to obtain a non-zero constant term in $u$ and $v$ for $z$ and $w$ is $u$ for $z$ and $v$ for $w.$ Using the determinant of the Jacobian we obtain

$$ \begin{vmatrix} 1 & 0 \\ 0 & 1 \end{vmatrix}^{-1} \begin{vmatrix} 1-v & -u \\ v (1-v) \exp((1-v)u) & \exp((1-v)u) - u v \exp((1-v)u) \\ \end{vmatrix} \\ = \exp((1-v)u) \begin{vmatrix} 1-v & - u \\ v (1-v) & 1 - uv \\ \end{vmatrix} \\ = \exp((1-v)u) (1 - uv - v + uv^2 + uv - uv^2) \\ = \exp((1-v)u) (1 - v).$$

Doing the substitution we find

$$k! \;\underset{u}{\mathrm{res}}\; \frac{1}{u^{k+1}} \frac{1}{(1-v)^{k+1}} \;\underset{v}{\mathrm{res}}\; \frac{1}{v^q} \frac{1}{\exp(q(1-v)u)} \\ \times \frac{1}{1-v\exp((1-v)u)} \exp(q(1-v)u) (1-v\exp((1-v)u)\exp(-(1-v)u))^k \\ \times \exp((1-v)u) (1-v) \\ = k! \;\underset{u}{\mathrm{res}}\; \frac{1}{u^{k+1}} \frac{1}{(1-v)^{k+1}} \;\underset{v}{\mathrm{res}}\; \frac{1}{v^q} \frac{1}{1-v\exp((1-v)u)} (1-v)^k \\ \times \exp((1-v)u) (1-v) \\ = k! \;\underset{u}{\mathrm{res}}\; \frac{1}{u^{k+1}} \;\underset{v}{\mathrm{res}}\; \frac{1}{v^q} \frac{1}{1-v\exp((1-v)u)} \exp((1-v)u) \\ = k! \;\underset{u}{\mathrm{res}}\; \frac{1}{u^{k+1}} \;\underset{v}{\mathrm{res}}\; \frac{1}{v^q} \frac{1}{\exp((v-1)u)-v}.$$

Consider on the other hand the quantity

$$\sum_{p=0}^{q-1} \left\langle k \atop p \right\rangle.$$

This is

$$k! [z^k] \sum_{p=0}^{q-1} [w^p] \frac{1-w}{\exp((w-1)z)-w} \\ = k! [z^k] [w^{q-1}] \frac{1}{1-w} \frac{1-w}{\exp((w-1)z)-w} \\ = k! [z^k] [w^{q-1}] \frac{1}{\exp((w-1)z)-w} \\ = k! \;\underset{z}{\mathrm{res}}\; \frac{1}{z^{k+1}} \;\underset{w}{\mathrm{res}}\; \frac{1}{w^q} \frac{1}{\exp((w-1)z)-w}.$$

This is the same as the sum term and we conclude the argument having shown that

$$\sum_{p=q}^k (-1)^p {k\choose p} (q-p)^k = k! - \sum_{p=0}^{q-1} \left\langle k \atop p \right\rangle$$

which is

$$\bbox[5px,border:2px solid #00A000]{ \sum_{p=q}^k (-1)^p {k\choose p} (q-p)^k = \sum_{p=q}^k \left\langle k \atop p \right\rangle.}$$

Reference, as per request. The Jacobi Residue Formula is Theorem 3 in the paper A Combinatorial Proof of the Multivariable Lagrange Inversion Formula by I. Gessel.

Answer 2

This answer is a supplement to @MarkoRiedel's interesting derivation. We provide a somewhat different approach to derive the identity \begin{align*} \color{blue}{\sum_{p=0}^{q-1} \left\langle k \atop p \right\rangle = \sum_{p=0}^{q-1} (-1)^p {k\choose p} (q-p)^k}\tag{1} \end{align*} which is the crucial one in @MarkoRiedels answer. I also use his notation to ease comparison.

---

The numbers $ \left\langle k \atop p \right\rangle$ are the Eulerian numbers as they are defined in Concrete Mathematics , Section 6.2 by D.E. Knuth, R.L. Graham and O. Patashnik.

Double generating function: In order to show (1) we start with a double generating function $A(t,u)$ of the Eulerian numbers stated as formula [14v] in Advanced Combinatorics by L. Comtet.

We obtain according to formula [5g] in Comtet: \begin{align*} \color{blue}{A(t,u)}&=1+\sum_{k=1}^\infty\sum_{q=1}^k \left\langle k \atop q-1 \right\rangle \frac{t^k}{k!}u^q\tag{2}\\ &\,\,\color{blue}{=\frac{1-u}{1-ue^{t(1-u)}}}\\ &=(1-u)\sum_{p=0}^\infty u^pe^{pt(1-u)}\\ &=\sum_{p=0}^\infty u^p\sum_{l=0}^\infty \frac{p^l}{l!}t^l(1-u)^{l+1}\\ &\,\,\color{blue}{=\sum_{p=0}^\infty u^p\sum_{l=0}^\infty\frac{p^l}{l!}t^l\sum_{j=0}^{l+1}\binom{l+1}{j}(-1)^ju^j}\tag{3} \end{align*}

Note that Comtet uses a slightly different definition of Eulerian numbers, which results in the lower index $q-1$ of $\left\langle k \atop q-1 \right\rangle$ in (2).

Coefficient comparison:

Coefficient comparison of (2) and (3) gives \begin{align*} \color{blue}{\left\langle k \atop q-1 \right\rangle} &=k![t^ku^q]\sum_{p=0}^\infty u^p\sum_{l=0}^\infty \frac{p^l}{l!}t^l\sum_{j=0}^{l+1}\binom{l+1}{j}(-1)^ju^j\\ &=[u^q]\sum_{p=0}^\infty u^p p^k\sum_{j=0}^{k+1}\binom{k+1}{j}(-1)^ju^j\tag{4}\\ &=\sum_{p=0}^q[u^{q-p}]p^k\sum_{j=0}^{k+1}\binom{k+1}{j}(-1)^ju^j\tag{5}\\ &=\sum_{p=0}^q[u^{p}](q-p)^k\sum_{j=0}^{k+1}\binom{k+1}{j}(-1)^ju^j\tag{6}\\ &\,\,\color{blue}{=\sum_{p=0}^{q-1}(q-p)^k\binom{k+1}{p}(-1)^p}\tag{7} \end{align*}

Comment:

• In (4) we select the coefficient of $t^k$.

• In (5) we use the rule $[u^{p-q}]A(u)=[u^p]u^qA(u)$. We also set the upper index of the outer sum to $q$, since other terms do not contribute.

• In (6) we change the order of summation: $p\to q-p$.

• In (7) we select the coefficient of $u^p$.

The identity (7) is stated in Concrete Mathematics as formula (6.38). The sum in (7) is pretty close to the wanted sum (1) besides the upper index $k+1$ which should be $k$. In order to derive (1) we do some

Telescoping:

We obtain from (7) \begin{align*} \left\langle k \atop q-1 \right\rangle&=\sum_{p=0}^{q-1}(q-p)^k\binom{k+1}{p}(-1)^p\\ &=\sum_{p=0}^{q-1}(q-p)^k\binom{k}{p}(-1)^p+\sum_{p=1}^{q-1}(q-p)^k\binom{k}{p-1}(-1)^p\\ &=\underbrace{\sum_{p=0}^{q-1}(q-p)^k\binom{k}{p}(-1)^p}_{a_{k,q}}-\sum_{p=0}^{q-2}(q-1-p)^k\binom{k}{p}(-1)^p\\ &=a_{k,q}-a_{k,q-1}\\ \end{align*} It follows via telescoping \begin{align*} \sum_{p=1}^{q-1}\left\langle k \atop p \right\rangle &=\sum_{p=1}^{q-1}\left(a_{k,p+1}-a_{k,p}\right)\\ &=\sum_{p=2}^{q}a_{k,p}-\sum_{p=1}^{q-1}a_{k,p}\\ &=a_{k,q}-a_{k,1}\\ \end{align*} and since \begin{align*} a_{k,1}=\sum_{p=0}^0(1-p)^k\binom{k}{p}(-1)^p=1=\left\langle k \atop 0 \right\rangle \end{align*} we derive \begin{align*} \color{blue}{\sum_{p=0}^{q-1}\left\langle k \atop p \right\rangle} = a_{k,q} \color{blue}{= \sum_{p=0}^{q-1}(q-p)^k\binom{k}{p}(-1)^p} \end{align*} and the claim (1) follows.

Answer 3

This answer is a(nother) supplement to @MarkoRiedel's great derivation. This time we look at some details of his proof of \begin{align*} \color{blue}{\sum_{p=0}^{q-1} \left\langle k \atop p \right\rangle = \sum_{p=0}^{q-1} (-1)^p {k\choose p} (q-p)^k}\tag{1} \end{align*} which is the crucial part in his answer. The most important aspect is the usage of multidimensional residues and how to find a proper substitution for simplification. We use the classic Integral Representation and the Computation of Combinatorial Sums by G. P. Egorychev. We cite and use substitution formulas of multi-dimensional residues and obtain this way Markos derivation. I also use his notation in order to ease comparison.

---

First part:

We start with the right-hand side of (1) and obtain \begin{align*} \color{blue}{\sum_{p=0}^{q-1}}&\color{blue}{(-1)^p \binom{k}{p}(q-p)^k}\\ &=\sum_{p=0}^\infty (-1)^p\binom{k}{p}(q-p)^k[[p\leq q-1]]\tag{2}\\ &=[w^{q-1}]\frac{1}{1-w}\sum_{p=0}^\infty(-1)^p\binom{k}{p}(q-p)^kw^p\tag{3}\\ &=[w^{q-1}]\frac{1}{1-w}\sum_{p=0}^\infty(-1)^p\binom{k}{p}k![z^k]e^{(q-p)z}w^p\tag{4}\\ &=k![z^k][w^{q-1}]\frac{e^{qz}}{1-w}\sum_{p=0}^\infty (-1)^p\binom{k}{p}\left(e^{-z}\right)^pw^p\\ &\,\,\color{blue}{=k![z^k][w^{q-1}]\frac{e^{qz}}{1-w}\left(1-\frac{w}{e^{z}}\right)^k}\tag{5}\\ \end{align*} In (5) we have a representation with two-dimensional residues (note $[z^k]A(z)=res_{z=0}\frac{A(z)}{z^{k+1}}$) which can be considerably simplified using a proper substitution. This substitution was nicely used by Marko, but how to come to it might not be that obvious. We'll have a look at it in the Intermezzo section where we will see how to automagically derive the appropriate substitution next to the comments below.

Comments:

• In (2) we use the Iverson brackets in order to get rid of the upper limit $q-1$ of the sum.

• In (3) we use an equivalent to the Iverson brackets the identity \begin{align*} \color{blue}{\sum_{p=0}^n a_p=\sum_{p=0}^\infty a_p[[p\leq n]]=[w^n]\frac{1}{1-w}\sum_{p=0}^\infty a_p w^p} \end{align*} which is valid, since \begin{align*} \color{blue}{[w^n]}&\color{blue}{\frac{1}{1-w}\sum_{p=0}^\infty a_p w^p} =[w^n]\sum_{l=0}^\infty w^l\sum_{p=0}^\infty a_p w^p\\ &=\sum_{l=0}^n[w^{n-l}]\sum_{p=0}^\infty a_pw^p=\sum_{l=0}^n[w^{l}]\sum_{p=0}^\infty a_pw^p\\ &\,\,\color{blue}{=\sum_{l=0}^n a_l} \end{align*}

• In (4) we use the coefficient of operator $[z^k]$ and the identity $a^k=k![z^k]e^{az}$.

• In (5) we apply the binomial theorem.

Intermezzo: Change of variables under the res sign

In order to find a substitution which simplifies (5) we use Rule 5 (change of variables under the res sign) from Egorychev's classic, which is stated as transformation formula for $n$-dimensional residues. Here we state it as two-dimensional identity which readily fits our needs. We have as special case $n=2$ of Rule 5: \begin{align*} &[z^{k_1}w^{k_2}]\left(A(z,w)\,\prod_{j=1}^2 f_{j}^{k_j}(z,w)\right)\\ &\ \ =[u^{k_1}v^{k_2}] \left(\left.\left[A(z,w)\left|\frac{\partial(z,w)}{\partial{(u,v)}}\right| \prod_{j=1}^2 f_{j}^{-1}(z,w)\right] \right|_{(z,w)=g(u,v)}\right)\tag{6} \end{align*} where we use the substitution: \begin{align*} \color{blue}{u=u(z,w)=\frac{z}{f_1(z,w)}\qquad\qquad v=v(z,w)=\frac{w}{f_2(z,w)}}\tag{7} \end{align*}

In (6) we have $A(z,w)$ a bivariate generating function, $f_j(z,w), j=1,2$ bivariate generating functions with constant term $\ne 0$ and $(z,w)=g(u,v)=(g_1(u,v), g_2(u,v))$ is the (unique) solution of (7).

In the current situation (5) we have \begin{align*} A(z,w)=\frac{e^z}{1-w}\qquad f_1^{k_1}(z,w)=\left(1-\frac{w}{e^z}\right)^k\qquad f_2^{k_2}(z,w)=\left(e^{z}\right)^{q-1} \end{align*} and use according to (7) the substitution \begin{align*} u(z,w)=\frac{z}{1-\frac{w}{e^z}}\qquad\qquad v(z,w)=\frac{w}{e^z}\tag{8} \end{align*} We put $v=w/e^z$ in $u(z,w)$ of (8) and obtain \begin{align*} u&=\frac{z}{1-v}\qquad \to\qquad \color{blue}{z=u(1-v)}\tag{9} \end{align*} We put $z=u(1-v)$ in $v(z,w)$ of (8) and obtain \begin{align*} v=\frac{w}{e^{u(1-v)}}\qquad \to\qquad \color{blue}{w=ve^{u(1-v)}}\tag{10} \end{align*} et voilà we have automagically found the substitution which was used in Marko's proof. :-)

Calculation of the Jacobian gives \begin{align*} \left|\frac{\partial(u,v)}{\partial{(z,w)}}\right|^{-1}&=\left|\frac{\partial(z,w)}{\partial{(u,v)}}\right| =\begin{vmatrix} \frac{\partial z}{\partial u}&\frac{\partial z}{\partial v}\\ \frac{\partial w}{\partial u}&\frac{\partial w}{\partial v}\\ \end{vmatrix}\\ &=\begin{vmatrix} 1-v&-u\\ (1-v)ve^{u(1-v)}&e^{u(1-v)}-uve^{u(1-v)}\\ \end{vmatrix}\\ &=e^{u(1-v)}\begin{vmatrix} 1-v&-u\\ (1-v)v&1-uv\\ \end{vmatrix}\\ &=(1-v)e^{u(1-v)}\tag{11} \end{align*}

Second part:

We can now continue with the expression (7). We apply the substitution rule (6) by using the substitution (7) and obtain from (6) with (9) - (11):

\begin{align*} \color{blue}{k![z^k]}&\color{blue}{[w^{q-1}]\frac{e^{z}}{1-w}\left(1-\frac{w}{e^{z}}\right)^ke^{(q-1)z}}\\ &=k![u^{k}][v^{q-1}] \left\{\left[\frac{e^z}{1-w}\left|\frac{\partial(z,w)}{\partial{(u,v)}}\right| \left.\left(1-\frac{w}{e^z}\right)^{-1}e^{-z} \right]\right|_{(z,w)=g(u,v)}\right\}\\ &=k![u^{k}][v^{q-1}] \left\{\frac{1}{1-ve^{u(1-v)}}\,(1-v)e^{u(1-v)}\,\frac{1}{1-v}\right\}\\ &=k![u^k][v^{q-1}]\frac{1}{e^{(v-1)u}-v}\\ &=k![u^k][v^{q-1}]\frac{1}{1-v}\frac{1-v}{e^{(v-1)u}-v}\\ &=k![u^k][v^{q-1}]\sum_{p=0}^\infty v^p\frac{1-v}{e^{(v-1)u}-v}\\ &=k![u^k]\sum_{p=0}^{q-1}[v^{q-1-p}]\frac{1-v}{e^{(v-1)u}-v}\\ &=k![u^k]\sum_{p=0}^{q-1}[v^{p}]\frac{1-v}{e^{(v-1)u}-v}\\ &\,\,\color{blue}{=\sum_{p=0}^{q-1} \left\langle k \atop p \right\rangle } \end{align*} and the claim follows.