Is $\sum_{k=0}^{r}\binom{r}{k}(r-k-1)^{r-k}(k-1)^{k-1}+(r-2)^r=0$ right? How to prove $$\sum_{k=0}^{r}\binom{r}{k}(r-k-1)^{r-k}(k-1)^{k-1}+(r-2)^r=0$$
I met this function when I tried to give another proof of the known lower bound of Tur\'an functions of complete hypergraphs ( Based on a same construction, instead of using shifting method, I tried to count edges directly )
Here is the question:
Define $a_0=-1$ and $a_1=1$. For all $r\geqslant2$, $a_0,a_1,\cdots,a_r$ satisfy
$$\sum_{k=0}^{r}\binom{r}{k}(r-k-1)^{r-k}a_k+(r-2)^r=0.$$
Prove that $a_k=(k-1)^{k-1}$ for all $k\geqslant2$.
I've tried generating function (exponential form) and Stirling's inversion formula, but they seemed to be wrong directions. And I've verified it for some numbers and they all turned to be right. 

Suppose we seek to evaluate
$$Q_r = \sum_{k=0}^r {r\choose k}
(r-k-1)^{r-k} (k-1)^{k-1}.$$
Concerning the exponential generating function for this quantity
$$Q(z) = \sum_{r\ge 0} Q_r \frac{z^r}{r!}$$
we observe that when  we multiply two exponential generating functions
of the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!}
\sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0}
\sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
= \sum_{n\ge 0}
\sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0}
\left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the  product of  the two generating  functions is  the generating
function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Therefore what  we have  here is a  convolution of the  two generating
functions
$$A(z) = \sum_{r\ge 0} (r-1)^r \frac{z^r}{r!}
\quad\text{and}\quad
B(z) = \sum_{r\ge 0} (r-1)^{r-1} \frac{z^r}{r!}.$$

The species of labelled trees has the specification
$$\mathcal{T} =
\mathcal{Z} \times \mathfrak{P}(\mathcal{T})$$
which gives the functional equation
$$T(z) = z \exp T(z).$$

Now $A(z)$ counts endofunctions with no fixed points
which gives the species
$$\mathfrak{P}(\mathfrak{C}_{\ge 2}(\mathcal{T}))$$
which produces the generating function
$$A(z) = \exp\left(-T(z) + \log\frac{1}{1-T(z)}\right)
= \exp(-T(z)) \frac{1}{1-T(z)}
\\ = \frac{z}{T(z)} \frac{1}{1-T(z)}.$$
Observe that the generating function of unmodified endofunctions
is $$E(z) = \sum_{r\ge 0} r^r \frac{z^r}{r!}
= \exp\left(\log\frac{1}{1-T(z)}\right)
= \frac{1}{1-T(z)}.$$
We need to integrate this to obtain $B(z),$ getting
$$\int \frac{1}{1-T(z)} dz$$
Put $T(z) = w$ to  get $z=w\exp(-w)$ and $dz = (\exp(-w)-w\exp(-w)) \;
dw$ to obtain
$$\int \frac{1}{1-w} (1-w) \exp(-w) \; dw
\\ = - \exp(-w)
= - \frac{1}{w} w \exp(-w)
= - \frac{z}{T(z)}.$$
We get for the value at zero by L'Hopital
$$- \frac{1}{T'(0)} = -1$$
which means that we have the right constant.

Closing in we obtain
$$Q_r
= -\frac{r!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{r+1}}
\frac{z}{T(z)} \frac{z}{T(z)} \frac{1}{1-T(z)} \; dz.$$
Using the same substitution as before this becomes
$$-\frac{r!}{2\pi i}
\int_{|w|=\epsilon} \frac{\exp(w(r+1))}{w^{r+1}}
\exp(-2w) \frac{1}{1-w}
(1-w) \exp(-w) \; dw
\\ = -\frac{r!}{2\pi i}
\int_{|w|=\epsilon} \frac{\exp(w(r-2))}{w^{r+1}}
\; dw
= -(r-2)^r$$
as claimed.

Additional material on endofunctions and the labeled tree function may
be found at this
MSE link
and this
MSE link II.
