# How to prove $\sum\limits_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$?

How do I prove the following identity directly?

$$\sum_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$$

I thought about using the binomial theorem for $(x+a)^n$, but got stuck, because I realized that my $x$ and $a$ in this case are dynamic variables. Any hints? Don't give me the answer; I really want to think through this on my own, but a nudge in the correct direction would be awesome. Thanks!

1. This identity is known as "Abel's Identity". It can be proved by generalizing:

$$\sum_{k} \binom{n}{k} (k+s-n)^{k} (r+n-k)^{n-k-1} = \frac{(r+s)^n}{r}$$ (By plugging $s=n-1,r=1$ we get the original identity.) A nicer way to write it is: $$\sum_{k} \binom{n}{k} (s-k)^{n-k} (r+k)^{k-1} = \frac{(r+s)^n}{r}$$ Sometimes an additional parameter is added: $$\sum_{k} \binom{n}{k} (s-tk)^{n-k} (r+tk)^{k-1} = \frac{(r+s)^n}{r}$$ This generalized identity is much easier to prove.

1. One more hint: To prove the generalized identity, one can expand $(s-k)^{n-k}$ by the binomial theorem, and change order of summation.
• I really like the hint! (+1) – Sungjin Kim Apr 6 '13 at 18:39

Don't give me the answer I really want to think through this on my own, but a nudge in the correct direction would be awesome.

As yee wish; it's yer question after all.

There are the following exponential generating functions:

\begin{align*} \frac{-z}{W(-z)(1+W(-z))}&=\sum_{k=0}^\infty\frac{(k-1)^k}{k!}z^k\\ \frac{-W(-z)}{z}&=\sum_{k=0}^\infty\frac{(k+1)^{k-1}}{k!}z^k \end{align*}

where $W(z)$ is the Lambert function. (Sometimes, these EGFs are instead expressed in terms of the "tree function" $T(z)=-W(-z)$.) The Maclaurin series for $-W(-z)$ looks like this:

$$-W(-z)=\sum_{k=1}^\infty \frac{k^{k-1}}{k!} z^k$$

which you will have to prove, perhaps by composing two appropriate series.

Now, the OP's identity can be recast as a convolution:

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

Switching to the generating function view, the convolution on the left has the generating function

$$\left(\frac{-z}{W(-z)(1+W(-z))}\right)\left(\frac{-W(-z)}{z}\right)=\frac1{1+W(-z)}$$

which means

$$\frac1{1+W(-z)}=1+\sum_{k=1}^\infty\frac{k^k}{k!}z^k$$

Now to prove the validity of this identity, you could start by deriving the formula (and the corresponding series) for the derivative of the Lambert function. Recall the fundamental relation $W(z)\exp(W(z))=z$; use implicit differentiation to derive an expression $W^\prime(z)$ which can then be manipulated to look like $\dfrac1{1+W(-z)}$. Again, the details are left up to you.

A nice proof uses the Lagrange-Bürman inversion formula. Start defining: $$C(z) = z e^{C(z)}$$ which gives the expansion: $$e^{\alpha C(z)} = \alpha \sum_{n \ge 0} \frac{(\alpha + n)^{n - 1} z^n}{n!}$$ Then you have: $$e^{(\alpha + \beta) C(z)} = e^{\alpha C(z)} \cdot e^{\beta C(z)}$$ Expanding and comparing both sides gives Abel's binomial theorem: $$(\alpha + \beta) (\alpha + \beta + n)^{n - 1} = \sum_{0 \le k \le n} \binom{n}{k} (\alpha + k)^{k - 1} (\beta + n - k)^{n - k - 1}$$

As an additional observation I would like to point out that the series expansion of $$e^{\alpha T(z)}$$ where $$T(z) = z \times e^{T(z)}$$ can also be computed with the Cauchy Residue Theorem, which gives a variant of Lagrange Inversion.

We seek to compute $$[z^n] e^{\alpha T(z)} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} e^{\alpha T(z)} \; dz.$$

Put $w=T(z)$ in the functional equation for $T(z)$ to get $$z = w e^{-w} \quad \text{and} \quad dz = e^{-w} - w e^{-w} = (1-w) e^{-w}.$$

Substitute this into the integral to obtain $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{e^{w(n+1)}}{w^{n+1}} e^{\alpha w} e^{-w} (1-w) \; dw.$$ This is $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{e^{w(n+\alpha)}}{w^{n+1}} (1-w) \; dw.$$ Now we can read off the residue at $w=0$ to get $$\frac{(n+\alpha)^n}{n!} - \frac{(n+\alpha)^{n-1}}{(n-1)!} = (n+\alpha) \frac{(n+\alpha)^{n-1}}{n!} - n \frac{(n+\alpha)^{n-1}}{n!} = \alpha \frac{(n+\alpha)^{n-1}}{n!}$$ as quoted in the answer by @vonbrand above.

How you tried induction? First consider, the base case $n=0$. Then show that if it holds for $n$ then this implies that it holds for $n+1$. Another way could be to write $n = (n-k+1)+(k+1)$, and then do the expansion of $n^n$, i.e going the other way.

• Not sure if its that simple. For the first approach, the inductive step looks quite difficult. For the second way, notice that the index dummy variable and your $k$ are really very different entities. – Macavity Mar 31 '13 at 9:31

long ago, I see this problem was solved by $WZ$ methods.

the same problem we have $$\displaystyle\sum_{k=1}^{n-1}C_{n}^{k}k^{k-1}(n-k)^{n-k-1}=2n^{n-2}(n-1)$$

• When you say WZ method do you mean Wilf-Zeilberger Pair? – user0987654321 Mar 31 '13 at 16:53