# A nice Combinatorial Identity

I am trying to show that $$\forall N\in\mathbb{N}$$,

$$\sum\limits_{n=0}^{N}\sum\limits_{k=0}^{N}\frac{\left(-1\right)^{n+k}}{n+k+1}{N\choose n}{N\choose k}{N+n\choose n}{N+k\choose k}=\frac{1}{2N+1}$$

It's backed by numerical verifications, but I can't come up with a proof.

So far, I tried using the generating function of $$\left(\frac{1}{2N+1}\right)_{N\in\mathbb{N}}$$, which is $$\frac{\arctan\left(\sqrt{x}\right)}{\sqrt{x}}$$, by showing that the LHS has the same generating function, but this calculation doesn't seem to lead me anywhere...

Any suggestion ?

Edit: the comment of bof (below this question) actually leads to a very simple proof.

Indeed, from bof's comment we have that the LHS is equal to $$\int_{0}^{1}\left(\sum\limits_{k=0}^{N}(-1)^k{N\choose k}{N+k\choose k}x^k\right)^2dx$$

And we recognize here the shifted Legendre Polynomials $$\widetilde{P_N}(x)=\displaystyle\sum\limits_{k=0}^{N}(-1)^k{N\choose k}{N+k\choose k}x^k$$.

And we know that the shifted Legendre Polynomials form a family of orthogonal polynomials with respect to the inner product $$\langle f|g\rangle=\displaystyle\int_{0}^{1}f(x)g(x)dx$$, and that their squared norm with respect to this product is $$\langle\widetilde{P_n}|\widetilde{P_n}\rangle=\frac{1}{2n+1}$$;

so this basically provides the desired result immediately.

• $$\sum_{n=0}^N\sum_{k=0}^N\frac{(-1)^{n+k}}{n+k+1}\binom Nn\binom Nk\binom{N+n}n\binom{N+k}k$$$$=\int_0^1\sum_{n=0}^N\sum_{k=0}^N(-1)^{n+k}\binom Nn\binom Nk\binom{N+n}n\binom{N+k}kx^{n+k}dx$$$$=\int_0^1\left(\sum_{n=0}^N(-1)^n\binom Nn\binom{N+n}nx^n\right)\left(\sum_{k=0}^N(-1)^k\binom Nk\binom{N+k}kx^k\right)dx$$$$=\int_9^1\left(\sum_{k=0}^N(-1)^k\binom Nk\binom{N+k}kx^k\right)^2dx$$ but I don't know why that integral evaluates to $\frac1{2N+1}$. – bof Aug 25 at 10:58
• @bof : thank you very much, this actually sovled the problem (see my edit). – Harmonic Sun Aug 25 at 16:03
• @HarmonicSun: Good observation. (+1) – Markus Scheuer Aug 25 at 16:05

We seek to verify that

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

Now we have

$${N\choose k} {N+n\choose n} = \frac{(N+n)!}{(N-k)! \times k! \times n!} = {N+n\choose n+k} {n+k\choose k}.$$

We get for the LHS

$$\sum_{n=0}^N \sum_{k=0}^N \frac{(-1)^{n+k}}{n+k+1} {N+n\choose n+k} {N\choose n} {N+k\choose k} {n+k\choose k} \\ = \sum_{n=0}^N \frac{1}{N+n+1} \sum_{k=0}^N (-1)^{n+k} {N+n+1\choose n+k+1} {N\choose n} {N+k\choose k} {n+k\choose k} \\ = \sum_{n=0}^N \frac{1}{N+n+1} {N\choose n} \sum_{k=0}^N (-1)^{n+k} {N+n+1\choose N-k} {N+k\choose k} {n+k\choose k} \\ = \sum_{n=0}^N \frac{1}{N+n+1} [z^N] (1+z)^{N+n+1} {N\choose n} \sum_{k=0}^N (-1)^{n+k} z^k {N+k\choose N} {n+k\choose n}.$$

Now the coefficient extractor controls the range and we continue with

$$\sum_{n=0}^N \frac{1}{N+n+1} [z^N] (1+z)^{N+n+1} {N\choose n} \\ \times \sum_{k\ge 0} (-1)^{n+k} z^k {N+k\choose N} \mathrm{Res}_{w=0} \frac{1}{w^{n+1}} \frac{1}{(1-w)^{k+1}} \\ = \sum_{n=0}^N \frac{1}{N+n+1} [z^N] (1+z)^{N+n+1} {N\choose n} \mathrm{Res}_{w=0} \frac{1}{w^{n+1}} \frac{1}{1-w} \\ \times \sum_{k\ge 0} (-1)^{n+k} z^k {N+k\choose N} \frac{1}{(1-w)^{k}} \\ = \sum_{n=0}^N \frac{(-1)^n}{N+n+1} [z^N] (1+z)^{N+n+1} {N\choose n} \\ \times \mathrm{Res}_{w=0} \frac{1}{w^{n+1}} \frac{1}{1-w} \frac{1}{(1+z/(1-w))^{N+1}} \\ = \sum_{n=0}^N \frac{(-1)^n}{N+n+1} [z^N] (1+z)^{N+n+1} {N\choose n} \\ \times \mathrm{Res}_{w=0} \frac{1}{w^{n+1}} \frac{(1-w)^N}{(1-w+z)^{N+1}} \\ = \sum_{n=0}^N \frac{(-1)^n}{N+n+1} [z^N] (1+z)^{n} {N\choose n} \\ \times \mathrm{Res}_{w=0} \frac{1}{w^{n+1}} \frac{(1-w)^N}{(1-w/(1+z))^{N+1}} \\ = \sum_{n=0}^N \frac{(-1)^n}{N+n+1} [z^N] (1+z)^{n} {N\choose n} \\ \times \sum_{k=0}^n (-1)^k {N\choose k} {n-k+N\choose N} \frac{1}{(1+z)^{n-k}} \\ = \sum_{n=0}^N \frac{(-1)^n}{N+n+1} {N\choose n} \\ \times \sum_{k=0}^n (-1)^k {N\choose k} {n-k+N\choose N} [z^N] (1+z)^k.$$

Now for the coefficient extractor to be non-zero we must have $$k\ge N$$ which happens just once, namely when $$n=N$$ and $$k=N.$$ We get

$$\frac{(-1)^N}{2N+1} {N\choose N} (-1)^N {N\choose N} {N-N+N\choose N}.$$

This expression does indeed simplify to

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2N+1}}$$

as claimed.

• Nice answer. Verified. (+1) – Markus Scheuer Aug 25 at 16:03
• Thank you very much, nice solution ! I invite you to see my edit, based on a comment from bof I have found a much shorter proof though :) – Harmonic Sun Aug 25 at 16:04
• All the better for a varied page. BTW my proof is self-contained and follows from first principles. Thanks also go to @MarkusScheuer for the credit. – Marko Riedel Aug 25 at 16:50