Intuitive proof of $\sum_{k=1}^{n} \binom{n}{k} k^{k-1} (n-k)^{n-k} = n^n$

This is a nice variant of Abel's identity which is sometimes considered as deep generalisation of the binomial theorem. This formulation can be found e.g. in the classic Advanced Combinatorics by Louis Comtet in section 3.1. The identity is stated there in the form \begin{align*} \sum_{k=0}^n\binom{n}{k}x(x-kz)^{k-1}(y+kz)^{n-k}=(x+y)^{n}\tag{1} \end{align*} valid for all x,y,z in a commutative ring. If we put $z=0$ we recover the binomial identity.

In a comment to OPs question @ArtW refers to a paper by Wengchang Chu which presents an instructive, elementary proof which is the basis of this answer.

Proof of Abel's identity

In fact it is more convenient to prove a generalised version of OPs claim. In a second step we then show that OPs formula is a particular variant of the general identity. We prove the identity (1) in the special case $z=-1$ which is appropriate for us and show:

The following is valid \begin{align*} \sum_{k=0}^n\binom{n}{k}x(x+k)^{k-1}(y-k)^{n-k}=(x+y)^n\tag{2} \end{align*}

We obtain \begin{align*} \sum_{k=0}^n&\binom{n}{k}x(x+k)^{k-1}(y-k)^{n-k}\\ &=\sum_{k=0}^n\binom{n}{k}x(x+k)^{k-1}((x+y)-(x+k))^{n-k}\tag{3}\\ &=\sum_{k=0}^n\binom{n}{k}x(x+k)^{k-1}\sum_{j=0}^{n-k}\binom{n-k}{j}(-1)^j(x+k)^j(x+y)^{n-k-j}\tag{4}\\ &=\sum_{k=0}^n\binom{n}{k}x(x+k)^{k-1}\sum_{j=k}^{n}\binom{n-k}{j-k}(-1)^{j-k}(x+k)^{j-k}(x+y)^{n-j}\tag{5}\\ &=\sum_{k=0}^n\sum_{j=k}^{n}\binom{n}{k}x(x+y)^{n-j}\binom{n-k}{j-k}(-1)^{j-k}(x+k)^{j-1}\tag{6}\\ &=\sum_{j=0}^n\binom{n}{j}x(x+y)^{n-j}\sum_{k=0}^{j}\binom{j}{k}(-1)^{j-k}(x+k)^{j-1}\tag{7}\\ &=(x+y)^n\tag{8} \end{align*} and (2) follows.

Comment:

• In (3) we replace $y-k$ with $(x+y)-(x+k)$ without changing anything, since we are adding zero only.

• In (4) we apply the binomial theorem to $$((x+y)-(x+k))^{n-k}$$

• In (5) we shift the index $j$ by $k$ in the inner sum

• In (6) we collect the factors of $(x+k)$ and exchange inner and outer sum by respecting \begin{align*} \sum_{k=0}^n\sum_{j=k}^n a_{j,k}=\sum_{0\leq k\leq j\leq n} a_{j,k}=\sum_{j=0}^n\sum_{k=0}^ja_{j,k} \end{align*}

• In (7) we use the identity \begin{align*} \binom{n}{k}\binom{n-k}{j-k}=\binom{n}{j}\binom{j}{k} \end{align*}
• In (8) we observe that the inner sum is a polynomial in $k$ of degree $j-1$. We also note that the difference operator $\Delta$ \begin{align*} \Delta f(x)=f(x+1)-f(x) \end{align*} when applied to a polynomial reduces the degree by one. Since the inner sum of (8) is the Delta operator applied $j$ times to the polynomial $(x+k)^{j-1}$ (see the referred Wiki page for this) and the degree of the polynomial is less than $j$, it vanishes whenever $j>0$ . \begin{align*} \Delta^{j}(x+k)^{j-1}=\sum_{k=0}^j\binom{j}{k}(-1)^{j-k}(x+k)^{j-1}=0\qquad\qquad j>0 \end{align*} So, we have only to consider $j=0$ in (7) resulting in $(x+y)^n$.

Deriving OPs formula

We can write Abel's identity (2) in case $x\ne 0$ in the form \begin{align*} \sum_{k=1}^n\binom{n}{k}(x+k)^{k-1}(y-k)^{n-k}=\frac{(x+y)^n-y^n}{x} \end{align*}

Letting $x\rightarrow 0$ we obtain \begin{align*} \sum_{k=1}^n\binom{n}{k}k^{k-1}(y-k)^{n-k}=ny^{n-1} \end{align*}

Finally putting $y=n$ we obtain \begin{align*} \sum_{k=1}^n\binom{n}{k}k^{k-1}(n-k)^{n-k}=n^n \end{align*} and OPs claim follows.

Note: Abel's identity comes in many different shapes. A nice collection can be found in this paper by Stanislav Sykora. OPs identity is listed as (13) in the paper. Amusingly and indicating the beauty of the formula he states in a footnote that precisely this identity was the reason for his recherche. He also presents a copy of the original proof by Abel from 1826.

Hint. This may be seen as a particular case of Abel-Hurwitz binomial identity, see a probabilistic explanation here. Combinatorial proofs are given in references $[8,11,19,21]$ of this paper. See also this paper.

There is a combinatorial proof of this as well. $n^n=n\cdot n\cdot n^{n-2}$ counts the number of doubly rooted labeled trees on the set $N:=\{1,2,\dots,n\}$. We describe a bijection which takes a doubly rooted tree $(T,u,v)$ to a pair $\Big((T_1,r),(T_2,s,t)\Big)$, where

• $(T_1,r)$ is a rooted tree on a nonempty subset $K$ of $N$,

• $(T_2,s,t)$ is a doubly rooted tree on $N\setminus K$. The only exception is when $N\setminus K$ is empty, in which case $T_2$ is the empty tree and has no roots.

This bijection proves the desired equality, since

• $k:=|K|$ can be any number between $1$ and $n$,
• there are $\binom{n}k$ ways to choose $K$,
• there are $k^{k-1}$ to choose a labeled rooted tree on $K$,
• there are $(n-k)^{n-k}$ ways to choose a labeled doubly rooted tree on $N\setminus K$. This works even when $N\setminus K$ is empty, as $0^0=1$, and there is one empty tree.

Here is bijection. Given the doubly rooted tree $(T,u,v)$, there are two cases.

1. If $u=v$, then $K=N$, $T_1=T$, $r=u=v$, and $T_2$ is empty.

2. Otherwise, let $w$ be the vertex adjacent to $u$ on the path from $u$ to $v$ in $T$. If you remove the edge $(u,w)$, then $T$ splits into two trees $T_1$ and $T_2$, where $u\in T_1$ and $w,v\in T_2$. We let $u$ be the root of $T_1$, and let $v$ and $w$ be the roots of $T_2$.