Simplifying Summation by Extracting Coefficient?

Question

I am looking to solve:

Show that $$\sum_{n \ge 0} \sum_{k \ge 0} {n\choose k} {2k \choose k} y^k x^n = \frac{1}{\sqrt{(1-x)(1-x(1+4y))}}$$

and then use that to show that

$$\sum_{k \ge 0} {n \choose k} {2k \choose k} (-2)^{-k} = \begin{cases}{n \choose n/2}2^{-n}, & \text{if }n \ge 0\text{ is even} \\ 0, & \text{if }n \ge 0\text{ is odd}\end{cases}$$

---

Working the problem myself, I can pull out certain things but it doesn't lead me towards the correct answer.

For example, I know that $\sum_{k \ge 0} {a \choose k} x^k = (1+x)^a$, so I could potentially use that by pulling out $\sum_{k \ge 0} {n \choose k} y^k = (1+y)^n$, or alternatively by pulling out $\sum_{k \ge 0} {2k \choose k} y^k = (1+y)^{2k}$.

Similarly, I know that $\sum_{n \ge 0} x^n = (1-x)^{-1}$, so I could potentially pull that out as well.

However, with whatever combination of factors I pull out, I am left with something that looks far off from $\frac{1}{\sqrt{(1-x)(1-x(1+4y))}}$.

As for the second part, I am not sure if I am supposed to extract the coefficient of $x^n$. If I set $k=n$, I get $$[x^n]\sum_{k \ge 0} {n \choose k} {2k \choose k} (-2)^{-k} = {n \choose n} {2n \choose n} (-2)^{-n} = {2n \choose n}(-2)^{-n}.$$ This is the wrong binomial coefficient, combined with an extra negative sign by the $2$, and no indication of any need for $n$ being even or odd.

Any thoughts?

Answer 1

For the first part: To prove the identity $$\sum_{n\ge0}\sum_{k\ge0}{n\choose k}{2k\choose k}y^kx^n=\frac1{\sqrt{(1-x)(1-x(1+4y))}}\tag1 $$ you should try swapping the order of summation. After swapping, the inner sum over $n$ will be $$ \sum_{n\ge0}{n\choose k}x^n $$ which you can evaluate using the identity $$\sum_{n\ge k}{n\choose k}x^n=\frac{x^k}{(1-x)^{k+1}}.\tag2$$ (Remember that $n \choose k$ equals zero when $n<k$.) Having simplified the inner sum, you need to evaluate the outer sum over $k$. For this you will need the identity $$\sum\limits_{m=0}^{\infty}{2m \choose m}t^m=(1-4t)^{-1/2}\tag3$$ (note that your formula for $\sum_{k\ge0}{2k\choose k}y^k$ is incorrect).

For the second part: Yes, you are supposed to extract the coefficient of $x^n$. By choosing $y=-\frac12$ in the LHS of (1) you will obtain something that looks like the LHS of the identity you wish to prove: $$\sum_{k\ge0}{n\choose k}{2k\choose k}(-2)^{-k}= \begin{cases} {n\choose n/2}2^{-n}&\text{if $n\ge0$ is even}\\ 0&\text{if $n\ge0$ is odd} \end{cases}\tag4 $$ To get the RHS of (4), plug $y=-\frac12$ into the RHS of (1), and expand as a power series in $x$. To perform this expansion, identity (3) can be used again.

Answer 2

Here is a different evaluation of the sum by way of enrichment. We seek to show that for $n\ge 0$

$$\sum_{k=0}^n {n\choose k} {2k\choose k} \frac{(-1)^k}{2^k} = \begin{cases} {n\choose n/2} \frac{1}{2^n}, & n \quad\text{even} \\ 0 & n \quad\text{odd}. \end{cases}$$

We get for the LHS

$$\sum_{k=0}^n {n\choose k} \frac{(-1)^k}{2^k} \;\underset{z}{\mathrm{res}}\; \frac{(1+z)^{2k}}{z^{k+1}} \\ = \;\underset{z}{\mathrm{res}}\; \frac{1}{z} \sum_{k=0}^n {n\choose k} \frac{(-1)^k}{2^k} \frac{(1+z)^{2k}}{z^{k}} \\ = \;\underset{z}{\mathrm{res}}\; \frac{1}{z} \left(1-\frac{(1+z)^2}{2z}\right)^n = \frac{1}{2^n} \;\underset{z}{\mathrm{res}}\; \frac{1}{z^{n+1}} (-1-z^2)^n \\ = \frac{(-1)^n}{2^n} [z^n] (1+z^2)^n.$$

This is zero for $n$ odd by inspection. We have for $n$ even i.e. $n=2m$

$$\frac{(-1)^{2m}}{2^{2m}} [z^{2m}] (1+z^2)^{2m} = \frac{1}{2^{2m}} [z^m] (1+z)^{2m} = \frac{1}{2^{2m}} {2m\choose m}$$

as claimed.