Prove $\sum_{q=\alpha}^p \binom{q}{\alpha} \binom{p}{q}\frac{(-1)^q(-q)^p}{q^\alpha}=\frac{p!}{\alpha!}.$

Question

How to prove

$\displaystyle \sum_{q=\alpha}^p \binom{q}{\alpha} \binom{p}{q}\frac{(-1)^q(-q)^p}{q^\alpha}=\frac{p!}{\alpha!}$

for $1 \leq \alpha \leq p$?

EDIT: This is a result that I derived after playing around with the (given) fact that

$\displaystyle\sum_{q=1}^p\sum_{j=1}^q q^{p-2}(1+h/q)^{j-1}\prod_{i=1,i\neq q}^p\frac{1}{q-i}=\sum_{q=1}^p[(1+h/q)^q-1]\frac{(-1)^{p-q}q^{p}}{q!(p-q)!}=\sum_{q=1}^p \frac{h^q}{q!}$

and grouping the coefficients of each $h^\alpha$ in both sides.

I have tried some values of $\alpha$ and $p$ and it works, so the formula seems to be true. I just don't know how to proceed to prove this result.

Answer 1

Suppose we seek to verify that

$$(-1)^p \sum_{q= r}^p {p\choose q} {q\choose r} (-1)^q q^{p- r} = \frac{p!}{ r!}.$$

We use the integral representation

$${q\choose r} = {q\choose q- r} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{q}}{z^{q- r+1}} \; dz$$

which is zero when $q\lt r$ (pole vanishes) so we may extend $q$ back to zero.

We also use the integral

$$q^{p- r} = \frac{(p- r)!}{2\pi i} \int_{|w|=\gamma} \frac{\exp(qw)}{w^{p- r+1}} \; dw.$$

We thus obtain for the sum

$$\frac{(-1)^p (p- r)!}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{p- r+1}} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} z^{ r-1} \sum_{q=0}^p {p\choose q} (-1)^q \frac{(1+z)^q}{z^q} \exp(qw) \; dz\; dw \\ = \frac{(-1)^p (p- r)!}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{p- r+1}} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} z^{ r-1} \left(1-\frac{1+z}{z}\exp(w)\right)^p \; dz\; dw \\ = \frac{(-1)^p (p- r)!}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{p- r+1}} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{p- r+1}} (-\exp(w)+z(1-\exp(w)))^p \; dz\; dw \\ = \frac{(p- r)!}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{p- r+1}} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{p- r+1}} (\exp(w)+z(\exp(w)-1))^p \; dz\; dw.$$

We extract the residue on the inner integral to obtain

$$\frac{(p- r)!}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{p- r+1}} {p\choose p- r} \exp( r w) (\exp(w)-1)^{p- r} \; dw \\ = \frac{p!}{ r!} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{p- r+1}} \exp( r w) (\exp(w)-1)^{p- r} \; dw.$$

It remains to compute $$[w^{p- r}]\exp( r w) (\exp(w)-1)^{p- r}.$$

Observe that $\exp(w)-1$ starts at $w$ so $(\exp(w)-1)^{p- r}$ starts at $w^{p- r}$ and hence only the constant coefficient from $\exp( r w)$ contributes, the value being one, which finally yields

$$\frac{p!}{ r!}.$$

Answer 2

For my own convenience I’m going to replace your $\alpha,p$, and $q$ with $m,n$, and $k$, respectively. Fix $n$, and let

$$f(m)=\sum_k\binom{k}m\binom{n}k(-1)^{n+k}k^{n-m}=\sum_k(-1)^{n-k}\binom{n}kk^{n-m}\frac{k^{\underline{m}}}{m!}\;,$$

where $x^{\underline{m}}=x(x-1)\ldots(x-m+1)$ is a falling factorial. Now

$$\begin{align*} \frac1{m+1}f(m)&=\sum_k(-1)^{n-k}\binom{n}kk^{n-m}\frac{k^{\underline{m}}}{(m+1)!}\\ &=\sum_k(-1)^{n-k}\binom{n}kk^{n-m-1}\frac{k\cdot k^{\underline{m}}}{(m+1)!}\\ &=\sum_k(-1)^{n-k}\binom{n}kk^{n-m-1}\frac{\big((k-m)+m\big)\cdot k^{\underline{m}}}{(m+1)!}\\ &=\sum_k(-1)^{n-k}\binom{n}kk^{n-m-1}\frac{k^{\underline{m+1}}+m\cdot k^{\underline{m}}}{(m+1)!}\\ &=f(m+1)+\sum_k(-1)^{n-k}\binom{n}kk^{n-m-1}\frac{m\cdot k^{\underline{m}}}{(m+1)!}\\ &=f(m+1)+\frac{m}{(m+1)!}\sum_k(-1)^{n-k}\binom{n}kk^{n-m-1}k^{\underline{m}}\;. \end{align*}$$

Now $k^{n-m-1}k^{\underline{m}}$ is a polynomial in $k$ of degree $n-1$, say

$$k^{n-m-1}k^{\underline{m}}=\sum_{i=0}^{n-1}c_ik^i\;,$$

so

$$\begin{align*} \frac1{m+1}f(m)&=f(m+1)+\frac{m}{(m+1)!}\sum_k(-1)^{n-k}\binom{n}k\sum_{i=0}^{n-1}c_ik^i\\ &=f(m+1)+\frac{m}{(m+1)!}\sum_{i=0}^{n-1}c_k\sum_k(-1)^{n-k}\binom{n}kk^i\\ &=f(m+1)+\frac{m}{(m+1)!}\sum_{i=0}^{n-1}c_k{i\brace n}n!\\ &=f(m+1)\;, \end{align*}$$

since the Stirling number of the second kind ${i\brace n}=0$ for $i<n$.

Now

$$f(0)=\sum_k\binom{n}k(-1)^{n-k}k^n={n\brace n}n!=n!\;,$$

so by an easy induction we have

$$f(m)=\frac{n!}{m!}$$

for $0\le m\le n$.

I actually started from the observation that if in fact $f(m)=\frac{n!}{m!}$, then $f$ would have to satisfy the equation

$$\frac1{m+1}f(m)=f(m+1)$$

and worked from there.

Answer 3

Let $n:=p-\alpha$ and $r:=q-\alpha$. Then, from the identity $\displaystyle\binom{q}{\alpha}\,\binom{p}{q}=\binom{p}{\alpha}\,\binom{p-\alpha}{q-\alpha}$, the equality $\displaystyle\sum_{q=\alpha}^p\,\binom{q}{\alpha}\,\binom{p}{q}\,\frac{(-1)^q(-q)^p}{q^\alpha}=\frac{p!}{\alpha!}$ holds if and only if $$(-1)^n\,n!=\sum_{r=0}^n\,(-1)^r\,\binom{n}{r}\,(\alpha+r)^n\,.\tag{*}$$ For $j=0,1,2,\ldots,n$, the coefficient of $\alpha^j$ on the right-hand side is given by $$t_j:=\sum_{r=0}^n\,(-1)^r\,\binom{n}{r}\,r^{n-j}\,,$$ where $0^0$ is set to be $1$. Therefore, it suffices to show that $t_1=t_2=\ldots=t_n=0$ and $t_0=(-1)^n\,n!$.

This can be done, using induction on $j$ that $t_{n-j}=0$ if $j=0,1,\ldots,n-1$ and $t_n=(-1)^n\,n!$. For $j=0$, the claim is trivial as $t_n=(1-1)^n$ which is $0$ if $n>0$, and which is $1$ if $n=0$. Assume now that $n,j>0$ and $t_{n-j+1}=t_{n-j+2}=\ldots=t_{n}=0$. Note that there are integers $d_1,d_2,\ldots,d_j$ such that $$r^{j}=j!\,\binom{r}{j}+d_{1}\,\binom{r}{j-1}+\ldots+d_j\,\binom{r}{0}$$ for all $r\in\mathbb{Z}$. Thus, $$t_{n-j}=j!\,\sum_{r=0}^n\,(-1)^r\,\binom{n}{r}\,\binom{r}{j}+\sum_{i=1}^j\,d_i\,t_{n-j+i}\,.$$ By the induction hypothesis, $\displaystyle t_{n-j}=j!\,\sum_{r=0}^n\,(-1)^r\,\binom{n}{r}\,\binom{r}{j}$. Consequently, $$t_{n-j}=j!\,\sum_{r=0}^n\,(-1)^r\,\binom{n}{j}\,\binom{n-j}{r-j}=(-1)^j\,j!\,\binom{n}{j}\,\sum_{r=j}^n\,(-1)^{r-j}\,\binom{n-j}{r-j}\,.$$ Ergo, $$t_{n-j}=(-1)^j\,j!\,\binom{n}{j}\,\sum_{\mu=0}^{n-j}\,(-1)^\mu\,\binom{n-j}{\mu}=(-1)^j\,j!\,\binom{n}{j}\,(1-1)^{n-j}$$ which is $0$ if $j<n$, and is $(-1)^n\,n!$ if $j=n$. The induction is now complete.

We have shown that (*) holds for any nonnegative integer $\alpha$, whence the original identity is also true. Note that the identity (*) holds in $\mathbb{Z}[\alpha]$, where $\alpha$ is treated as a variable.

P.S.: We don't need the fact that the $d_i$'s are integers. It is sufficient to show that the $d_i$'s are rational numbers. Simply observe that $\mathbb{Q}[x]$ is spanned by polynomials of the form $\binom{x}{i}$ for $i=0,1,2,\ldots$. Then, $x^j\in\mathbb{Q}[x]$ is linear combination over $\mathbb{Q}$ of $\binom{x}{i}$ for $i=0,1,\ldots,j$. However, it can be easily shown that $x^j$ is indeed a linear combination over $\mathbb{Z}$ of $\binom{x}{i}$ for $i=0,1,\ldots,j$.

---

Alternatively, observe that $\displaystyle s_j:=\sum_{r=0}^n\,(-1)^{n-r}\,\binom{n}{r}\,r^j=(-1)^n\,t_{n-j}$ is the number of surjections from $\{1,2,\ldots,j\}$ to $\{1,2,\ldots,n\}$, using the Principle of Inclusion and Exclusion. Clearly, if $j=0,1,\ldots,n-1$, $(-1)^n\,t_{n-j}=s_j=0$ because such surjections do not exist, whereas $s_n=(-1)^n\,t_0$ is the number of permutations on $\{1,2,\ldots,n\}$, which is precisely $n!$.