Another combinatorics problem: $\sum\limits_{k = 0}^n (-1)^k \binom{2n-k}k2^{2n-2k}=2n+1$ I am dealing with problem 10F in the textbook A Course in Combinatorics by J. H. van Lint and R. M. Wilson. 
Problem 10F: Prove directly the equality 
$\sum\limits_{k = 0}^n {{{\left( { - 1} \right)}^k}\left( {\begin{array}{*{20}{c}}
{2n - k}\\k\end{array}} \right){2^{2n - 2k}} = } 2n + 1$.
Sketch of the proof: Evaluate 
$\sum\limits_{n = 0}^\infty  {\sum\limits_{k = 0}^n {{{\left( { - 1} \right)}^k}\left( {\begin{array}{*{20}{c}}{2n - k}\\k\end{array}} \right){2^{2n - 2k}}{x^{2n}}} } $. To do this, use Hint 1. Then, use Hint 2.
Hint 1: $\sum\limits_{j = 0}^\infty  {\left( {\begin{array}{*{20}{c}}{a + j}\\j
\end{array}} \right){x^j} = {{\left( {1 - x} \right)}^{ - a - 1}}} ,\,\,a \in {\mathbb{Z}^ + }$.
Hint 2:
${\sum\limits_{i = 0}^\infty  {\left( {2i + 1} \right){x^{2i}} = \left( {\frac{x}{{1 - {x^2}}}} \right)} ^\prime }$. 
Attempt: It is enough to show that 
$\sum\limits_{n = 0}^\infty  {\sum\limits_{k = 0}^n {{{\left( { - 1} \right)}^k}\left( {\begin{array}{*{20}{c}}
{2n - k}\\
k
\end{array}} \right){2^{2n - 2k}}{x^{2n}}} }  = {\left( {\frac{x}{{1 - {x^2}}}} \right)^\prime }$. But I can not use Hint 1. 

Finally got it.  First, note that we can take the inner sum to be $\sum_{k=0}^\infty$ since $\binom{2n-k}{k} = 0$ when $k > n$.  Next, observe that
$$
\binom{2n-k}{k} = \binom{2(n-k) + k}{k} = \binom{2j + k}{k}
$$
where $j = n - k$.  Then
\begin{align*}
\sum_{n \geq 0} \sum_{k \geq 0} (-1)^k \binom{2n - k}{k}2^{2(n-k)} x^{2n} &= \sum_{j \geq 0} \sum_{k \geq 0}(-1)^k \binom{2j + k}{k} 2^{2j} x^{2(j+k)}\\
&= \sum_{j \geq 0} (2x)^{2j} \sum_{k \geq 0} \binom{2j + k}{k} (-x^2)^k \, .
\end{align*}
By Hint 1, the inner sum is $\frac{1}{(1+x^2)^{2j+1}}$, so we find
\begin{align*}
\sum_{j \geq 0} (2x)^{2j} \sum_{k \geq 0} \binom{2j + k}{k} (-x^2)^k &= \sum_{j \geq 0} (2x)^{2j} \frac{1}{(1+x^2)^{2j+1}} = \frac{1}{1+x^2}\sum_{j \geq 0} \left(\frac{(2x)^2}{(1 + x^2)^2}\right)^j\\
&=\frac{1}{1+x^2} \frac{1}{1 - \frac{(2x)^2}{(1 + x^2)^2}} = \frac{1 + x^2}{(1 + x^2)^2 - (2x)^2}\\
&= \frac{1+x^2}{(1 + x^2 - 2x)(1 + x^2 + 2x)} = \frac{1+x^2}{(1 - x)^2(1 +x)^2} = \frac{1+x^2}{(1 - x^2)^2} \, .
\end{align*}
You can easily check using the quotient rule that this last function is indeed $\frac{d}{dx} \frac{x}{1 - x^2}$.  The result then follows from Hint 2.
