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