Another combinatorics problem: $\sum\limits_{k = 0}^n (-1)^k \binom{2n-k}k2^{2n-2k}=2n+1$

Question

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.

Answer 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.