How to prove combinatorical sum identity?

Question

$$\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?

Answer 1

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.