Saturday, October 3, 2015

sequences and series - 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.


Answer



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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...