summation - Binomial identity: Clever idea for a short proof?

When answering this question I had to cope with this binomial identity:

The following holds true

\begin{align*}
\sum_{i=0}^k\binom{k}{i}\sum_{j=0}^i\binom{i}{j}(-1)^{k-i}j^{i-j}
=\sum_{i=0}^k\binom{k}{i}\sum_{j=0}^i\binom{i}{j}(-1)^{i-j}j^{k-i}\qquad\qquad k\geq 0
\end{align*}

Although LHS and RHS look very similar, I have troubles to find a short transformation from one side to the other. At the time the proof looks like

\begin{align*}
\sum_{i=0}^k&\binom{k}{i}\sum_{j=0}^i\binom{i}{j}(-1)^{k-i}j^{i-j}\qquad&\\

&=\sum_{i=0}^k\binom{k}{k-i}\sum_{j=0}^{k-i}\binom{k-i}{j}(-1)^{i}j^{k-i-j}\qquad& i\longrightarrow k-i \\
&=\sum_{i=0}^k\binom{k}{k-i}\sum_{j=i}^{k}\binom{k-i}{j-i}(-1)^{i}(j-i)^{k-j}\qquad& j\in[0,k-i]\longrightarrow j\in[i,k] \\
&=\sum_{j=0}^k\sum_{i=0}^{j}\binom{k}{k-i}\binom{k-i}{j-i}(-1)^{i}(j-i)^{k-j}\qquad&\text{exchange sums}\\
&=\sum_{i=0}^k\sum_{j=0}^{i}\binom{k}{k-j}\binom{k-j}{i-j}(-1)^{j}(i-j)^{k-i}\qquad&i\longleftrightarrow j\\
&=\sum_{i=0}^k\sum_{j=0}^{i}\binom{k}{k-i+j}\binom{k-i+j}{j}(-1)^{i-j}j^{k-i}\qquad&j\longrightarrow i-j\\
&=\sum_{i=0}^k\sum_{j=0}^{i}\binom{k}{i}\binom{i}{j}(-1)^{i-j}j^{k-i}\qquad&\\
\end{align*}
and the claim follows.

Since this derivation looks somewhat cumbersome i am wondering if there is a more efficient index transformation possible or another shorter way to prove this identity.

Answer

Let $K$ be a set with $k$ elements. Both sides can be interpreted as counting, with signs, choices of

• a subset $I$ of $K$,


• a subset $J$ of $I$, and


• either a function $K \setminus I \to J$ (on the LHS) or a function $I \setminus J \to J$ (on the RHS).

Picking $I$ and $J$ is equivalent to picking a partition of $K$ into three disjoint subsets, namely $K \setminus I, I \setminus J$, and $J$. The LHS and the RHS are related by switching $K \setminus I$ and $I \setminus J$, which is what your index transformations are accomplishing.