# Calculate $\sum_{k=l}^{2n} \binom{2n+k}{2k} \frac{(2k-1)!!}{(k-l)!} (-1)^k$ [closed]

I'm trying to proof that $$\sum_{k=l}^{2n} \binom{2n+k}{2k} \frac{(2k-1)!!}{(k-l)!} (-1)^k = \begin{cases} 0 \quad {\rm if} \, \, l \, \,{\rm odd} \\ \frac{(-1)^{n-l/2}(2n+l)!}{4^n \left(n-\frac{l}{2}\right)! \left(n+\frac{l}{2}\right)!} \quad {\rm if} \, \, l \, \,{\rm even} \end{cases}$$ where $$()!$$ is factorial and $$()!!$$ double-factorial. Any idea?

edit: Before down-voting it would be more helpful to state what information is missing, but that is probably too much to ask...

some background: The question arose when I tried to solve Prove that $\sum_{k=0}^{2n} \binom {2n+k}{k} \binom{2n}{k} \frac{(-1)^k}{2^k} \frac{1}{k+1} = 0.$

So the objective was proving that $$\sum\limits_{ {0 \le } k { \le 2n} } {\binom{2n+k}{2n} \binom{2n}{k} {{\left( \frac{t-1}{2} \right)^{k} }}} = P_{2n}(t)$$ which I now tackled differently. But I was wondering why the straight forward way was so difficult. That is I used the binomial theorem for the inner power $$(t-1)^k=(-1)^k\sum_{l=0}^k \binom{k}{l} (-t)^l$$ and then interchanged summation order to obtain $$\sum_{l=0}^{2n} \frac{(-t)^l}{l!} \sum_{k=l}^{2n} \binom{2n+k}{2k} \frac{(2k-1)!!}{(k-l)!} (-1)^k = P_{2n}(t)$$ after some manipulations with the binomial coefficients. So by comparison with the textbook Legendre-form $$P_{2n}(t)=\sum_{l=0}^{n} \frac{t^{2l}}{(2l)!} \frac{(-1)^{n-l}(2n+2l)!}{4^n(n+l)!(n-l)!}$$ I concluded the above relation.

## closed as off-topic by Davide Giraudo, KReiser, Paul Frost, Lee David Chung Lin, NamasteDec 28 '18 at 17:37

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Davide Giraudo, KReiser, Paul Frost, Lee David Chung Lin, Namaste
If this question can be reworded to fit the rules in the help center, please edit the question.

• I have not down-voted, but perhaps is because you haven't include any information, like how did you encounter this problem? Or how did you obtain the answer? – Zacky Dec 25 '18 at 21:43

We seek to evaluate

$$\sum_{k=q}^{2n} {2n+k\choose 2k} \frac{(2k-1)!}{(k-1)! \times 2^{k-1}} \frac{1}{(k-q)!} (-1)^k \\ = \sum_{k=q}^{2n} {2n+k\choose 2k} \frac{(2k)!}{k! \times 2^{k}} \frac{1}{(k-q)!} (-1)^k .$$

This is

$$q! \sum_{k=q}^{2n} {2n+k\choose 2k} \frac{(2k)!}{k! \times k! \times 2^{k}} \frac{k!}{q!\times(k-q)!} \frac{(-1)^k}{2^k} \\ = q! \sum_{k=q}^{2n} {2n+k\choose 2k} {2k\choose k} {k\choose q} \frac{(-1)^k}{2^k}.$$

Observe that

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

and furthermore

$${2n\choose k} {k\choose q} = \frac{(2n)!}{(2n-k)! \times q! \times (k-q)!} = {2n\choose q} {2n-q\choose k-q}.$$

We get for the sum

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

This becomes

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

Now we may extend $$k$$ beyond $$2n-q$$ because of the coefficient extractor $$[z^{2n-q}]$$ (no contribution) and get

$${2n\choose q} q! \frac{(-1)^q}{2^q} [z^{2n-q}] (1+z)^{2n-q} \sum_{k\ge 0} {2n+q+k\choose 2n} \frac{(-1)^k}{2^k} z^k \\ = {2n\choose q} q! \frac{(-1)^q}{2^q} [z^{2n-q}] (1+z)^{2n-q} [w^{2n}] (1+w)^{2n+q} \sum_{k\ge 0} (1+w)^k \frac{(-1)^k}{2^k} z^k \\ = {2n\choose q} q! \frac{(-1)^q}{2^q} [z^{2n-q}] (1+z)^{2n-q} [w^{2n}] (1+w)^{2n+q} \frac{1}{1+z(1+w)/2}.$$

Re-write this as

$${2n\choose q} q! \frac{(-1)^q}{2^q} [w^{2n}] (1+w)^{2n+q} \mathrm{Res}_{z=0} \frac{1}{z^{2n-q+1}} (1+z)^{2n-q} \frac{1}{1+z(1+w)/2}.$$

Working with the residue we apply the substitution $$z/(1+z) = v$$ or $$z=v/(1-v)$$ to get

$$\mathrm{Res}_{v=0} \frac{1}{v^{2n-q}} \frac{1-v}{v} \frac{1}{1+(v/(1-v))(1+w)/2} \frac{1}{(1-v)^2} \\ = \mathrm{Res}_{v=0} \frac{1}{v^{2n-q+1}} \frac{1}{1-v+v(1+w)/2} \\ = \mathrm{Res}_{v=0} \frac{1}{v^{2n-q+1}} \frac{1}{1-v(1-w)/2} = \frac{1}{2^{2n-q}} (1-w)^{2n-q}.$$

Substitute into the remaining coefficient extractor to get

$${2n\choose q} q! \frac{(-1)^q}{2^q} [w^{2n}] (1+w)^{2n+q} \frac{1}{2^{2n-q}} (1-w)^{2n-q} \\ = {2n\choose q} q! \frac{(-1)^q}{2^{2n}} \sum_{p=0}^{2n-q} (-1)^p {2n-q\choose p} {2n+q\choose 2n-p}.$$

Now

$${2n\choose q} {2n-q\choose p} = \frac{(2n)!}{q!\times p! \times (2n-q-p)!} = {2n\choose p} {2n-p\choose q}$$

and

$${2n-p\choose q} {2n+q\choose 2n-p} = \frac{(2n+q)!}{q! \times (2n-p-q)! \times (p+q)!} = {2n+q\choose q} {2n\choose p+q}.$$

This yields

$${2n+q\choose q} q! \frac{(-1)^q}{2^{2n}} \sum_{p=0}^{2n-q} (-1)^p {2n\choose p} {2n\choose p+q} \\ = {2n+q\choose q} q! \frac{(-1)^q}{2^{2n}} \sum_{p=0}^{2n-q} (-1)^p {2n\choose p} [z^{2n-p-q}] (1+z)^{2n} \\ = {2n+q\choose q} q! \frac{(-1)^q}{2^{2n}} [z^{2n-q}] (1+z)^{2n} \sum_{p=0}^{2n-q} (-1)^p {2n\choose p} z^p.$$

Now we may extend $$p$$ beyond $$2n-q$$ because of the coeffcient extractor $$[z^{2n-q}]$$ in front. We find

$${2n+q\choose q} q! \frac{(-1)^q}{2^{2n}} [z^{2n-q}] (1+z)^{2n} \sum_{p\ge 0} (-1)^p {2n\choose p} z^p \\ = {2n+q\choose q} q! \frac{(-1)^q}{2^{2n}} [z^{2n-q}] (1+z)^{2n} (1-z)^{2n} \\ = {2n+q\choose q} q! \frac{(-1)^q}{2^{2n}} [z^{2n-q}] (1-z^2)^{2n}.$$

Concluding we immediately obtain zero when $$q$$ is odd, and otherwise we find

$${2n+q\choose q} q! \frac{(-1)^q}{2^{2n}} [z^{2(n-q/2)}] (1-z^2)^{2n} \\ = {2n+q\choose q} q! \frac{(-1)^q}{2^{2n}} [z^{n-q/2}] (1-z)^{2n}.$$

This is

$${2n+q\choose q} q! \frac{(-1)^q}{2^{2n}} (-1)^{n-q/2} {2n\choose n-q/2}$$

or alternatively $$\bbox[5px,border:2px solid #00A000]{ \frac{(-1)^{n+q/2}}{2^{2n}} \frac{(2n+q)!}{(n-q/2)! \times (n+q/2)!}.}$$

• Thanks very much, I really appreciate and start to like that coefficient extractor method ;) – Diger Dec 25 '18 at 22:26
• @Diger Thank you for the kind remark. You might want to add some context if it was useful to you, so it gets re-opened. – Marko Riedel Dec 29 '18 at 18:51