# Binomial ID $\sum_{k=m}^p(-1)^{k+m}\binom{k}{m}\binom{n+p+1}{n+k+1}=\binom{n+p-m}{n}$

Could I get some help with proving this identity?

$$\sum_{k=m}^p(-1)^{k+m}\binom{k}{m}\binom{n+p+1}{n+k+1}=\binom{n+p-m}{n}.$$

It has been checked in Matlab for various small $n,m$ and $p$. I have a proof for $m=0$ that involves Pascal's rule to split it into two sums that mostly cancel, but this does not work for all $m$. I have looked at induction on various letters (and looked at simultaneous induction on multiple letters) without any success.

I would appreciate any help, algebraic or combinatoric.

• Where does this identity come from? – Yemon Choi Dec 4 '16 at 23:58
• They are the coefficients of an expansion of a solution to Laplace's equation in terms of solid spherical harmonics. The $n$ and $m$ are the separation constants that occur in for example the spherical harmonics $P_n^m(\cos\theta)\exp(im\phi)$ – Matt Majic Dec 5 '16 at 0:23

Such identities are often reduced to the Chu--Vandermonde's identity $\sum_{i+j=\ell} \binom{x}i\binom{y}j=\binom{x+y}\ell$ by using reflection formulae $\binom{x}k=\binom{x}{x-k}$, $\binom{x}k=(-1)^k\binom{k-x-1}k$.

In your case you may write $$\sum_{k=m}^p(-1)^{k+m}\binom{k}{m}\binom{n+p+1}{n+k+1}= \sum_{k=m}^p \binom{-m-1}{k-m}\binom{n+p+1}{p-k}= \binom{n+p-m}{p-m}$$ as you need, so it is Chu--Vandermonde for $x=-m-1$, $y=n+p+1$, $\ell=p-m$.

• Right, with the same generatingfunctionological explanation: $(1+t)^x (1+t)^y = (1+t)^{x+y}$. – Noam D. Elkies Dec 5 '16 at 4:32
• @Noam but why formal series $(1+t)^x=\sum \binom{x}{n} t^n$ satisfy this equality? It may be justified by some abstract nonsense like 'this is known for reals or for positive integers, but the coefficients are polynomials in $x,y$, thus it holds formally too.' This argument may be reduced to bit less abstract: 'both parts of CV are polynomials in $x,y$ of degree at most $\ell$, thus it suffices to check that their values agree for integers $x,y\geqslant 0, x+y\leqslant \ell$ (this triangle is an interpolating set for polynomials of degree at most $\ell$) , where identity is just obvious.' – Fedor Petrov Dec 5 '16 at 5:54
• I suppose you can also use a (formal) differential equation to prove this. – Noam D. Elkies Dec 5 '16 at 14:25

It's a generating-function exercise. We have $$\sum_{k=m}^\infty (-1)^{k+m} {k \choose m} x^{k-m} = (1+x)^{-(m+1)},$$ and (with $j=p-k$) $$\sum_{j=0}^\infty {n+p+1 \choose n+(p-j)+1} x^j = \sum_{j=0}^\infty {n+p+1 \choose j} x^j = (1+x)^{n+p+1}.$$ The desired sum is the $x^{p-m}$ coefficient of the product $(1+x)^{n+p-m}$ of these two power series, which is ${n+p-m \choose p-m} = {n+p-m \choose n}$, QED.

• Presumably "well-known", but easier to redo than to track down in the literature. – Noam D. Elkies Dec 5 '16 at 3:07

I wish to explain a modern (high tech) method called the Wilf-Zeilberger (WZ) technique which might help you (and anyone interested) with the present question and many others you encounter in the future. This will save you time from hunting the literature and comparing notes with the milliard hypergeometric formulas.

Zeilberger developed an accompanying algorithm package which is by now part of the symbolic softwares, Maple and Mathematica. In case you have access to Maple, you may download and run a freely available online copy of it from here.

Start with the discrete function $$F(p,k)=(-1)^{k+m}\binom{k}{m}\binom{n+p+1}{n+k+1}\binom{n+p-m}{n}^{-1}.$$ The above-mentioned algorithm furnished the companion function $$G(p,k)=-\frac{F(p,k)(k-m)(n+k+1)}{(p+1-k)(n+p+1-m)}.$$ Check (preferable using a symbolic software) that $$F(p+1,k)-F(p,k)=G(p,k+1)-G(p,k).\tag1$$ Convention: $\binom{a}b=0$ if $b>a$ or $b<0$. Now, sum both sides of (1) over all integers $k$, i.e. $\sum_{-\infty}^{\infty}$. Notice that the RHS of (1) vanishes because $\sum_{k\in\mathbb{Z}}G(p,k+1)=\sum_{k\in\mathbb{Z}}G(p,k)$. If we denote $f(p):=\sum_{k=m}^pF(p,k)=\sum_{\mathbb{Z}}F(p,k)$ then the LHS of (1) implies $$f(p+1)=f(p).$$ But, if $p=0$ then $f(0)=1$ and hence $f(p)=1$ identically. That means (after rewriting) $$\sum_{k=m}^p(-1)^{k+m}\binom{k}{m}\binom{n+p+1}{n+k+1}=\binom{n+p-m}{n}$$ as desired.

Mathematica says: $$(-1)^{2 m} \binom{n+p+1}{m+n+1} \, _2F_1(m+1,m-p;m+n+2;1)$$