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.

  • 7
    $\begingroup$ $$\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}$. $\endgroup$
    – bof
    Aug 25, 2019 at 10:58
  • 2
    $\begingroup$ @bof : thank you very much, this actually sovled the problem (see my edit). $\endgroup$ Aug 25, 2019 at 16:03
  • $\begingroup$ @HarmonicSun: Good observation. (+1) $\endgroup$ Aug 25, 2019 at 16:05

1 Answer 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.

  • $\begingroup$ Nice answer. Verified. (+1) $\endgroup$ Aug 25, 2019 at 16:03
  • 2
    $\begingroup$ 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 :) $\endgroup$ Aug 25, 2019 at 16:04
  • $\begingroup$ 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. $\endgroup$ Aug 25, 2019 at 16:50

You must log in to answer this question.

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