Is $(n+2)^n=(n+1)\sum_{k=0}^n\binom{n}{k}\frac{(k+1)^{k-1}(n-k)^{n-k}}{n+1-k}$? As far as I can tell using Mathematica, the following identity seems to hold:
$$(n+2)^n=(n+1)\sum_{k=0}^n\binom{n}{k}\frac{(k+1)^{k-1}(n-k)^{n-k}}{n+1-k},$$
where we define $0^0=1$. However, I am having trouble proving it. I thought that this looked familiar and found the formulas (5.64) and (5.65) in Graham, Knuth, and Patashnik's "Concrete Mathematics", which are
$$\sum_{k=0}^n\binom{n}{k}(tk+r)^k(tn-tk+s)^{n-k}\frac{r}{tk+r}=(tn+r+s)^n$$
and
$$\sum_{k=0}^n\binom{n}{k}(tk+r)^k(tn-tk+s)^{n-k}\frac{r}{tk+r}\frac{s}{tn-tk+s}=(tn+r+s)^n\frac{r+s}{tn+r+s},$$
but these seem to just barely not work for my purpose. Does anyone know a proof of this result (or perhaps a counterexample)? I suspect I will have to do some playing with generating functions.
 A: I think I have found a solution using the principal branch of the Lambert W function. The Lagrange inversion theorem can be used to show that
$$W_0^p(x)=\sum_{n=p}^\infty\frac{-p(-n)^{n-p-1}}{(n-p)!}x^n,$$
so that by shifting the index, we have
$$\left(\frac{-W_0(-x)}{x}\right)^p=\sum_{n=0}^\infty\frac{p(n+p)^{n-1}}{n!}x^n.$$
Then by taking $p=\pm1$ and multiplying the two cases, we get
$$\left(\sum_{n=0}^\infty(n+1)^{n-1}\frac{x^n}{n!}\right)\left(\sum_{n=0}^\infty(n-1)^{n-1}\frac{x^n}{n!}\right)=-1.$$
Now, the LHS is
$$\left(\sum_{n=0}^\infty(n+1)^{n-1}\frac{x^n}{n!}\right)\left(\sum_{n=0}^\infty(n-1)^{n-1}\frac{x^n}{n!}\right)=\sum_{n=0}^\infty\sum_{k=0}^n\binom{n}{k}(k-1)^{k-1}(n-k+1)^{n-k-1}\frac{x^n}{n!}.$$
Thus, for $n>0$, we have
$$\sum_{k=0}^n\binom{n}{k}(k-1)^{k-1}(n-k+1)^{n-k-1}=0.$$
Then on the one hand, we have
$$\sum_{k=0}^{n+1}\binom{n+1}{k}(k-1)^{k-1}(n-k+2)^{n-k}=0,$$
while on the other hand,
$$\sum_{k=0}^{n+1}\binom{n+1}{k}(k-1)^{k-1}(n-k+2)^{n-k}=-(n+2)^n+\sum_{k=0}^n\binom{n+1}{k+1}(k)^{k}(n-k+1)^{n-k-1}.$$
Thus,
\begin{equation}(n+2)^n=\sum_{k=0}^n\binom{n+1}{k+1}k^{k}(n-k+1)^{n-k-1}\\
=(n+1)\sum_{k=0}^n\binom{n}{k}\frac{k^{k}(n-k+1)^{n-k-1}}{k+1}\\
=(n+1)\sum_{k=0}^n\binom{n}{k}\frac{(n-k)^{n-k}(k+1)^{k-1}}{n+1-k}.\end{equation}
A: You can actually do this by applying the first formula that you quoted from Concrete Mathematics three times with $r=t=1$, that is,
$$
\sum_{k=0}^n\binom{n}{k}(k+1)^{k-1}(n-k+s)^{n-k}=(n+1+s)^n\;.\tag1
$$
Split your sum like this:
\begin{eqnarray}
\sum_{k=0}^n\binom nk\frac{(k+1)^{k-1}(n-k)^{n-k}}{n-k+1}
&=&
\sum_{k=0}^n\binom nk\frac{(k+1)^{k-1}(n-k)^{n-k}}{n-k+1}((n-k+1)-(n-k))
\\
&=&
\sum_{k=0}^n\binom nk(k+1)^{k-1}(n-k)^{n-k}-\sum_{k=0}^n\binom nk\frac{(k+1)^{k-1}(n-k)^{n-k+1}}{n-k+1}\;.
\end{eqnarray}
The first sum is just $(1)$ with $s=0$, so that’s $(n+1)^n$. In the second sum, insert $s$ and differentiate with respect to it to get rid of the unwanted factors:
\begin{eqnarray}
\frac{\partial}{\partial s}\sum_{k=0}^n\binom nk\frac{(k+1)^{k-1}(n-k+s)^{n-k+1}}{n-k+1}
&=&
\sum_{k=0}^n\binom nk(k+1)^{k-1}(n-k+s)^{n-k}
\\
&=&
(n+1+s)^n
\;,
\end{eqnarray}
again applying $(1)$. This result is readily integrated, so all we need is a value of the sum at some particular value of $s$. Substitute $s=1$ and again apply $(1)$ to obtain
\begin{eqnarray}
\sum_{k=0}^n\binom nk\frac{(k+1)^{k-1}(n-k+1)^{n-k+1}}{n-k+1}
&=&
\sum_{k=0}^n\binom nk(k+1)^{k-1}(n-k+1)^{n-k}
\\
&=&(n+2)^n\;.
\end{eqnarray}
Thus, putting it all together,
\begin{eqnarray}
\sum_{k=0}^n\binom nk\frac{(k+1)^{k-1}(n-k)^{n-k}}{n-k+1}
&=&
(n+1)^n-(n+2)^n-\int_1^0\mathrm ds(n+1+s)^n
\\
&=&
(n+1)^n-(n+2)^n-\left[\frac{(n+1+s)^{n+1}}{n+1}\right]_1^0
\\
&=&(n+1)^n-(n+2)^n-(n+1)^n+\frac{(n+2)^{n+1}}{n+1}
\\
&=&\frac{(n+2)^n}{n+1}\;.
\end{eqnarray}
A: We seek to prove that
$$(n+2)^n = (n+1) \sum_{k=0}^n {n\choose k} 
\frac{(k+1)^{k-1} (n-k)^{n-k}}{n+1-k}.$$
Observe that the RHS  is
$$\sum_{k=0}^n {n+1\choose k} 
(k+1)^{k-1} (n-k)^{n-k}
\\ = (n+2)^n +
\sum_{k=0}^{n+1} {n+1\choose k} 
(k+1)^{k-1} (n-k)^{n-k}
\\ = (n+2)^n +
\sum_{k=0}^{n+1} {n+1\choose k} 
(k+1)^{k-1} (n+1-k-1)^{n+1-k-1}.$$
We are therefore tasked with showing that the sum is zero.
Introduce the tree function $T(z)$  from combinatorics where $T(z) = z
\exp  T(z)$ and  $T(z) =  - W_0(-z).$  Note that  we have  by Cayley's
theorem that $T(z)  = \sum_{n\ge 1} n^{n-1}  \frac{z^n}{n!}.$ Note also
that  the functional equation is derived from the combinatorial class
equation
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\mathcal{T} = \mathcal{Z} \times \textsc{SET}(\mathcal{T}).$$
which might be useful in a purely combinatorial proof.
Observe that
$$P(z) = \frac{T(z)}{z} = \sum_{n\ge 1} n^{n-1} \frac{z^{n-1}}{n!}
= \sum_{n\ge 1} n^{n-2} \frac{z^{n-1}}{(n-1)!}
\\ = \sum_{n\ge 0} (n+1)^{n-1} \frac{z^n}{n!}$$
Next introduce
$$Q(z) = \frac{z}{T(z)}.$$
We have for the coefficients that
$$n! [z^n] Q(z) =
n! \;\underset{z}{\mathrm{res}}\;
\frac{1}{z^{n+1}} \frac{z}{T(z)}
= n! \;\underset{z}{\mathrm{res}}\;
\frac{1}{z^n} \frac{1}{T(z)}.$$
Now put $T(z) = w$ so that $w = z \exp(w)$ or $z = w \exp(-w)$
and $dz = \exp(-w) (1-w) \; dw$ to obtain
$$n! \;\underset{w}{\mathrm{res}}\;
\frac{1}{w^n} \exp(nw) \frac{1}{w} \exp(-w) (1-w)
\\ = n! \;\underset{w}{\mathrm{res}}\;
\frac{1}{w^{n+1}} \exp((n-1)w) (1-w)
= n! \frac{(n-1)^n}{n!}
- n! \frac{(n-1)^{n-1}}{(n-1)!}
\\ = (n-1)^n - n (n-1)^{n-1} = - (n-1)^{n-1}$$
so that in fact
$$Q(z) = - \sum_{n\ge 0} (n-1)^{n-1} \frac{z^n}{n!}.$$
We thus require by convolution of EGFs with $n\ge 0$
the value of
$$- (n+1)! [z^{n+1}] P(z) Q(z)$$
which is
$$ - (n+1)! [z^{n+1}] 1 = 0$$
and we have the claim.
Remark. Here we have used the fact that when we
multiply two  exponential  generating functions  of the  sequences
$\{p_n\}$ and $\{q_n\}$ we get that
$$ P(z) Q(z) = \sum_{n\ge 0} p_n \frac{z^n}{n!}
\sum_{n\ge 0} q_n \frac{z^n}{n!}
= \sum_{n\ge 0}
\sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} p_k q_{n-k} z^n\\
= \sum_{n\ge 0}
\sum_{k=0}^n \frac{n!}{k!(n-k)!} p_k q_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0}
\left(\sum_{k=0}^n {n\choose k} p_k q_{n-k}\right)\frac{z^n}{n!}.$$
