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.

Solution 1:

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} \;\underset{w}{\mathrm{res}}\; \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} \;\underset{w}{\mathrm{res}}\; \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 \;\underset{w}{\mathrm{res}}\; \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 \;\underset{w}{\mathrm{res}}\; \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 \;\underset{w}{\mathrm{res}}\; \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.