How to prove combinatorical sum identity? $$\sum_{k=0}^n 2^{2n+1-2k}\binom{2n+1-k}{k}(-1)^k=2(n+1)$$
According to wolfram, this is true. How would one prove this either algebraically or combinatorically?
 A: We use the coefficient of operator  $[z^n]$     to  denote  the coefficient  of  $z^n$  in  a  series. This  way  we   can  write for instance
\begin{align*}
\binom{n}{k}=[z^k](1+z)^n
\end{align*}

We obtain for $n\geq 0$:
  \begin{align*}
\color{blue}{\sum_{k=0}^n}&\color{blue}{2^{2n+1-2k}\binom{2n+1-k}{k}(-1)^k}\\
&=\sum_{k=0}^n\binom{n+k+1}{n-k}2^{2k+1}(-1)^{n-k}\tag{1}\\
&=\sum_{k=0}^n[z^{n-k}](1+z)^{n+k+1}2^{2k+1}(-1)^{n-k}\tag{2}\\
&=2(-1)^n[z^n](1+z)^{n+1}\sum_{k=0}^\infty (-4z(1+z))^k\tag{3}\\
&=2(-1)^n[z^n]\frac{(1+z)^{n+1}}{1+4z(1+z)}\tag{4}\\
&=2(-1)^n[z^n]\frac{(1+z)^{n+1}}{(1+2z)^2}\\
&=2(-1)^n[z^n]\sum_{j=0}^\infty(j+1)(-2z)^j(1+z)^{n+1}\tag{5}\\
&=2(-1)^n\sum_{j=0}^n(j+1)(-2)^j[z^{n-j}](1+z)^{n+1}\tag{6}\\
&=2(-1)^n\sum_{j=0}^n(j+1)(-2)^j\binom{n+1}{n-j}\tag{7}\\
&=2(-1)^n\sum_{j=0}^n(j+1)(-2)^j\binom{n+1}{j+1}\tag{8}\\
&=2(-1)^n(n+1)\sum_{j=0}^n(-2)^j\binom{n}{j}\tag{9}\\
&=2(-1)^n(n+1)(1-2)^n\tag{10}\\
&\,\,\color{blue}{=2(n+1)}
\end{align*}
and the claim follows.

Comment:


*

*In (1) we change the order of summation: $k\to n-k$.

*In (2) we apply the coefficient of operator.

*In (3) we use the linearity of the coefficient of operator and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$. We also set the upper limit of the series to $\infty$ without changing anything, since we are adding zeros only.

*In (4) we use the geometric series expansion.

*In (5) we use the binomial series expansion.

*In (6) we apply the same rule as in (3) and restrict the upper bound of the series to $n$ since the powers of $z$ are non-negative.

*In (7) we select the coefficient of $z^{n-j}$.

*In (8) we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

*In (9) we use the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

*In (10) we apply the binomial theorem.
