Proving combinatorial identity $\sum_{k=0}^{n}(-1)^k \binom{2n-k}k 2^{2n-2k} = 2n+1$ "directly"

Question

This is a homework problem. In the first part of the problem, I managed to use a combinatorial problem to prove the following identity:

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

But I actually have problem with the second part of the problem which asked me to prove this identity "directly", probably using some form of generating functions/algebra method.

There was a hint given but I got stuck: The hint says to calculate

$\Sigma_{n=0}^\infty\Sigma_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} x^{2n}$

and that it would be useful to consider the fact that $ \Sigma(2n+1)x^{2n}= \frac{d}{dx}\frac{x}{1-x^2} $ and $(1-x)^{-a-1}=\Sigma_{j=0}^\infty {a+j \choose j}x^j$.

I am able to prove both these "possibly useful facts" in the hint, but I don't see how to calculate the suggested double sum or prove the identity. [I would have thought that the combinatorial proof is harder to find!] [You may assume that I am familiar with the formal treatment of power series.]

Any help would be greatly appreciated.

Answer 1

We want to prove that $$\sum_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} = 2n+1$$

Let's work backwards. The approach via generating functions is to prove it at once for all $n$ instead of a specific $n$; we are done if we can prove that $$\sum_{n=0}^{\infty} \sum_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} x^{2n} = \sum_{n=0}^{\infty} (2n+1) x^{2n} = \frac{d}{dx} \frac{x}{1-x^2}$$

Now obviously to sum the above as written, we need to solve the original problem, so that's no help. Instead, let's interchange the sums, to sum over $k$ instead (and also write $\binom{2n-k}{k}$ as $\binom{2n-k}{2n-2k}$ to get a nicer expression): we want to prove that $$\sum_{k=0}^\infty (-1)^k \sum_{n=k}^{\infty} \binom{2n-k}{2n-2k} 2^{2n-2k} x^{2n} = \frac{d}{dx} \frac{x}{1-x^2}$$

Now let $j = n - k$, so that $n = k + j$, then our inner sum above is $$\sum_{j=0}^{\infty} \binom{k+2j}{2j}2^{2j}x^{2k+2j} = x^{2k}\sum_{j=0}^{\infty} \binom{k+2j}{2j}(2x)^{2j}$$

This sum has only the even-power terms of a sum of the form in the second hint, and picking out only the even-power terms from a power series $f(x)$ gives $\frac{f(x)+f(-x)}{2}$. Thus, the above sum is

$$x^{2k}\left(\frac{(1-2x)^{-k-1} + (1+2x)^{-k-1}}{2} \right)$$

And the whole sum becomes

$$\sum_{k=0}^{\infty} (-1)^k x^{2k} \left(\frac{(1-2x)^{-k-1} + (1+2x)^{-k-1}}{2} \right)$$ $$= \frac12\left(\frac{1}{1-2x}\sum_{k=0}^\infty\left(\frac{-x^2}{1-2x}\right)^k + \frac{1}{1+2x}\sum_{k=0}^\infty \left(\frac{-x^2}{1+2x}\right)^k\right)$$ $$ = \frac12\left(\frac{1}{1-2x}\frac{1}{1-\frac{-x^2}{1-2x}} + \frac{1}{1+2x}\frac{1}{1-\frac{-x^2}{1+2x}}\right)$$ $$ = \frac12\left( \frac{1}{1-2x+x^2} + \frac{1}{1+2x+x^2}\right)$$ $$ = \frac12\left( \frac{1}{(1-x)^2} + \frac{1}{(1+x)^2}\right) \tag 1$$

It remains only to prove that this is the same as $\dfrac{d}{dx} \dfrac{x}{1-x^2}$, which is a simple calculus exercise.

Answer 2

Suppose we are trying to evaluate $$\sum_{k=0}^n {2n-k\choose k} (-1)^k 4^{n-k}.$$

Introduce the integral representation $${2n-k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^{2n-k} \; dz.$$

This gives for the sum the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \sum_{k=0}^n \frac{(-1)^k 4^{n-k}}{z^k (1+z)^k} \; dz \\ = \frac{4^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{1-(-1)^{n+1}/4^{n+1}/z^{n+1}/(1+z)^{n+1}} {1+1/4/z/(1+z)} \; dz \\ = \frac{4^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{4z+4z^2-(-1)^{n+1}/4^n/z^n/(1+z)^n} {1+4z+4z^2} \; dz.$$

Now this has two components. The first component is $$\frac{4^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{4z+4z^2}{(1+2z)^2} \; dz = \frac{4^{n+1}}{2\pi i} \int_{|z|=\epsilon} (1+z)^{2n+1} \frac{1}{(1+2z)^2} \; dz,$$ which is easily seen to be zero.

The second component is $$\frac{4^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{(-1)^n/4^n/z^n/(1+z)^n} {(1+2z)^2} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{(-1)^n/z^n/(1+z)^n} {(1+2z)^2} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{(-1)^n} {(1+2z)^2} \; dz.$$

Extracting coeffcients from this we obtain $$(-1)^n \sum_{q=0}^n {n\choose q} (-1)^{n-q} 2^{n-q} (n-q+1).$$ This becomes $$(-1)^n (n+1) \sum_{q=0}^n {n\choose q} (-1)^{n-q} 2^{n-q} - (-1)^n \sum_{q=0}^n {n\choose q} (-1)^{n-q} 2^{n-q} q.$$ or $$(n+1)- (-1)^n \sum_{q=1}^n {n\choose q} (-1)^{n-q} 2^{n-q} q \\ = (n+1)- (-1)^n \times n\times \sum_{q=1}^n {n-1\choose q-1} (-1)^{n-q} 2^{n-q} \\ = (n+1)- (-1)^n \times n\times \sum_{q=1}^n {n-1\choose q-1} (-1)^{(n-1)-(q-1)} 2^{(n-1)-(q-1)} \\ = (n+1)- (-1)^n \times n\times (-1)^{n-1} = 2n+1.$$

The choice of $\epsilon$ here is such that $\epsilon \lt 1/2.$