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}$

Question

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.

Answer 1

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}