13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? What methods are you supposed to use (induction, combinatorics, graph theory...)? $\endgroup$ – Crostul Apr 7 '16 at 7:17
  • $\begingroup$ Is the first factor in the sum $\binom{q}{\alpha}$ or $\binom{\alpha}{q}$ ? $\endgroup$ – Jean Marie Apr 7 '16 at 15:31
  • $\begingroup$ @JeanMarie it's as it appears $\endgroup$ – Jeze Ken Apr 7 '16 at 16:50
  • $\begingroup$ This identity is equivallent to Abel's binomial theorem. $\endgroup$ – Nemo Apr 8 '16 at 14:15
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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!$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.