# 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 text book Combinatorics by J. H. Van Lint and R. M. Milson.

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.

#### Solutions Collecting From Web of "Another combinatorics problem: $\sum\limits_{k = 0}^n (-1)^k \binom{2n-k}k2^{2n-2k}=2n+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.