25
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ Nice answer. Verified. (+1) $\endgroup$ – Markus Scheuer Aug 25 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$ – Harmonic Sun Aug 25 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$ – Marko Riedel Aug 25 at 16:50

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.