# Orthogonal combinatoric sum

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?

• I think it is way easier to prove the orthogonality of Legendre polynomials through Rodrigues' formula, then your combinatorial identity follows. – Jack D'Aurizio Jun 7 '16 at 15:26
• 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. – Matt Majic Jun 7 '16 at 23:48

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

Introduce

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