I have verified this identity in Matlab: $$ \sum_{k=m}^n~(-)^{n+k}\frac{2k+1}{n+k+1}\binom{n}{k}\binom{n+k}{k}^{-1}\binom{k}{m}\binom{k+m}{m}=\delta_{nm} $$ Where $n, m$ are positive integers, and where $(-)^p$ means $(-1)^p$. It was found by combining two inverse expansions $$ f_n=\sum_{k=0}^n\frac{2k+1}{n+k+1}\binom{n}{k}\binom{n+k}{k}^{-1}g_k $$ and $$ g_n =\sum_{k=0}^n(-)^{n-k}\binom{n}{k}\binom{n+k}{k}f_k $$ where $f_n$ and $g_n$ are orthogonal polynomials (related to Legendre polynomials) of several variables. Could anyone offer a proof of this? Or recommend any books etc. that might be useful?

  • $\begingroup$ I think it is way easier to prove the orthogonality of Legendre polynomials through Rodrigues' formula, then your combinatorial identity follows. $\endgroup$ Jun 7, 2016 at 15:26
  • $\begingroup$ I do have a proof of those but the proof of the second one is long and shaky. I thought is could be easier to prove the second one using the first one plus the orthogonality identity. $\endgroup$
    – Matt Majic
    Jun 7, 2016 at 23:48

1 Answer 1


Suppose we seek to verify that

$$\sum_{k=m}^n (-1)^{n+k} \frac{2k+1}{n+k+1} {n\choose k} {n+k\choose k}^{-1} {k\choose m} {k+m\choose m} = \delta_{mn}.$$

Here we may assume $n\ge m$, the equality holds trivially otherwise.

Now we have

$${n\choose k}{n+k\choose k}^{-1} = \frac{n!}{k! (n-k)} \frac{k! n!}{(n+k)!} \\ = \frac{n!}{(n-k)} \frac{n!}{(n+k)!} = {2n\choose n+k} {2n\choose n}^{-1}.$$

We get for the sum

$$\sum_{k=m}^n (-1)^{n+k} \frac{2k+1}{n+k+1} {2n\choose n+k} {k\choose m} {k+m\choose m} = \delta_{mn} \times {2n\choose n}.$$

which is

$$\sum_{k=m}^n (-1)^{n+k} (2k+1) {2n+1\choose n+k+1} {k\choose m} {k+m\choose m} \\ = \delta_{mn} \times (2n+1)\times {2n\choose n}.$$


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

Observe that this vanishes when $k\gt n$ so we may extend $k$ upward to infinity.

Furthermore introduce

$${k\choose m} = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{m+1}} (1+w)^k \; dw.$$

Observe once again that the integral vanishes, this time when $0\le k\lt m$ so we may extend $k$ back to zero.

We thus get for the sum

$$(-1)^n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{2n+1} \\ \times \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{m+1}} \sum_{k\ge 0} (-1)^k (2k+1) {k+m\choose m} z^k (1+w)^k \; dw\; dz.$$

The inner sum yields two pieces, the first is

$$\sum_{k\ge 0} (-1)^k {k+m\choose m} z^k (1+w)^k = \frac{1}{(1+z+wz)^{m+1}} \\ = \frac{1}{(1+z)^{m+1}} \frac{1}{(1+wz/(1+z))^{m+1}}.$$

On extracting the residue for the integral in $w$ we obtain

$$(-1)^n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{2n+1} \\ \times \frac{1}{(1+z)^{m+1}} {2m\choose m} (-1)^m \frac{z^m}{(1+z)^m} \; dz \\ = {2m\choose m} (-1)^{n+m} \int_{|z|=\epsilon} \frac{1}{z^{n-m+1}} (1+z)^{2n-2m} \; dz \\ = {2m\choose m} (-1)^{n+m} {2n-2m\choose n-m}.$$

The second piece from the sum is

$$2 \sum_{k\ge 1} (-1)^k k {k+m\choose m} z^k (1+w)^k.$$

Write $$k{k+m\choose m} = \frac{(k+m)!}{(k-1)! m!} = (m+1) \frac{(k+m)!}{(k-1)! (m+1) !} \\ = (m+1){k+m\choose m+1}$$

to get for the sum

$$2(m+1) z(1+w) \sum_{k\ge 1} (-1)^k {k+m\choose m+1} z^{k-1} (1+w)^{k-1} \\ = - 2(m+1)z(1+w) \frac{1}{(1+z+wz)^{m+2}} \\ = - 2(m+1)z(1+w) \frac{1}{(1+z)^{m+2}} \frac{1}{(1+wz/(1+z))^{m+2}}.$$

Here we get two pieces, the first is

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

We have two cases, we get zero when $n=m$ and when $n\gt m$ we have

$$ -2(m+1){2m+1\choose m} (-1)^{n+m} {2n-2m-1\choose n-m-1}.$$

The second piece is

$$- 2(m+1) (-1)^n \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z}{z^{n+1}} (1+z)^{2n+1} \\ \times \frac{1}{(1+z)^{m+2}} {2m\choose m-1} (-1)^{m-1} \frac{z^{m-1}}{(1+z)^{m-1}} \; dz \\ = 2(m+1) {2m\choose m-1} (-1)^{n+m} \int_{|z|=\epsilon} \frac{1}{z^{n-m+1}} (1+z)^{2n-2m} \; dz \\ = 2(m+1) {2m\choose m-1} (-1)^{n+m} {2n-2m\choose n-m}.$$

Therefore when $n=m$ we get

$${2n-2m\choose n-m} (-1)^{m+n} \left(2(m+1){2m\choose m-1} + {2m\choose m}\right).$$

This simplifies to

$$(-1)^{2m} \left(2(m+1){2m\choose m-1} + {2m\choose m}\right) \\ = 2m{2m\choose m} + {2m\choose m} = (2m+1){2m\choose m}.$$

This is precisely the claim we were trying to prove. On the other hand when $n\gt m$ we obtain

$${2n-2m\choose n-m} (-1)^{m+n} \\ \times \left(2(m+1){2m\choose m-1} + {2m\choose m} - 2(m+1){2m+1\choose m} \frac{n-m}{2n-2m}\right).$$

The factor is

$$(2m+1){2m\choose m} - (m+1){2m+1\choose m} = 0.$$

This concludes the argument.

Remark. For $n=m$ we could have evaluated the single term in the initial sum by expanding the four binomial coefficients and assumed $n\gt m$ thereafter.


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.