TITLE: Proving combinatorial identity $\sum_{k=0}^{n}(-1)^k \binom{2n-k}k 2^{2n-2k} = 2n+1$ "directly"
QUESTION [7 upvotes]: 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.

REPLY [2 votes]: 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.$
{"set_name": "stack_exchange", "score": 7, "question_id": 747102}