Is $\sum_{k=0}^{r}\binom{r}{k}(r-k-1)^{r-k}(k-1)^{k-1}+(r-2)^r=0$ right?

Question

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.

Answer 1

One may recall Abel's identity:

$$\sum_{k=0}^n \binom{n}{k} (s-k)^{n-k} (\nu+k)^{k-1} = \frac{(\nu+s)^n}\nu, \qquad \nu\neq0.\tag1$$

A short WZ-style proof of $(1)$ may be found here or here (Shalosh B. Ekhad and John E. Majewicz).

Then just apply $(1)$ with $s=r-1$, $\nu=-1$ to get your initial identity.

Answer 2

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.