5
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Where does this identity come from? $\endgroup$
    – Yemon Choi
    Commented Dec 4, 2016 at 23:58
  • 2
    $\begingroup$ 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)$ $\endgroup$
    – Matt Majic
    Commented Dec 5, 2016 at 0:23

4 Answers 4

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Right, with the same generatingfunctionological explanation: $(1+t)^x (1+t)^y = (1+t)^{x+y}$. $\endgroup$
    – Noam D. Elkies
    Commented Dec 5, 2016 at 4:32
  • $\begingroup$ @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.' $\endgroup$
    – Fedor Petrov
    Commented Dec 5, 2016 at 5:54
  • 1
    $\begingroup$ I suppose you can also use a (formal) differential equation to prove this. $\endgroup$
    – Noam D. Elkies
    Commented Dec 5, 2016 at 14:25
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Presumably "well-known", but easier to redo than to track down in the literature. $\endgroup$
    – Noam D. Elkies
    Commented Dec 5, 2016 at 3:07
7
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .