How to prove that $\sum_{k=0}^n{(-1)^k{4n-2k\choose 2n}{2n\choose k}}=2^{2n}$?

Question

$$\sum_{k=0}^n{\left( -1 \right) ^k\left( \begin{array}{c} 4n-2k\\ 2n\\\end{array} \right) \left( \begin{array}{c} 2n\\ k\\\end{array} \right)}=2^{2n}$$

I know the correctness of this formula, but how can I prove it?

Thanks for your help.

Answer 1

Prove that$$\sum_{k=0}^n{\left( -1 \right) ^k\left( \begin{array}{c} 4n-2k\\ 2n\\\end{array} \right) \left( \begin{array}{c} 2n\\ k\\\end{array} \right)}=2^{2n}$$

Consider the following binomial expansion \begin{align*} (x^2-1)^{2n}&=\sum_{k=0}^{2n}(-1)^kx^{4n-2k}{2n\choose k} \end{align*} Put $x=1$ after differentiating both sides $2n$ times with respect to $x$ and you are done! (Stop reading and try it yourself for a "confidence-booster") \begin{align*} 2x(2n)(x^2-1)^{2n-1}&=\sum_k(-1)^k(4n-2k)x^{4n-2k-1}{2n\choose k}\\ 2(2n)(x^2-1)^{2n-1}+4x^2(2n)(2n-1)(x^2-1)^{2n-2}&=\sum_{k}(-1)^k(4n-2k)x^{4n-2k-1}{2n\choose k}\\ \end{align*} Let's neglect terms like the leftmost one in the above expression, for we are eventually going to put $x=1$ and since $2n-k>2n-k-1$. So, \begin{align*} \cdots+2^2x^2(2n)(2n-1)(x^2-1)^{2n-2}&=\sum_k(-1)^k(4n-2k)x^{4n-2k-1}{2n\choose k}\\ \cdots+2^3x^3(2n)(2n-1)(2n-2)(x^2-1)^{2n-3}&=\sum_k(-1)^k(4n-2k)(4n-2k-1)x^{4n-2k-2}{2n\choose k}\\ \end{align*} and so on so that at last \begin{align*} 2^{2n}x^{2n}(2n)!(x^2-1)^0&=\sum_k(-1)^k(4n-2k)(4n-2k-1)\cdots(2n-2k+1)x^{2n-2k}{2n\choose k}\\ \end{align*} Now, what is the greatest value $k$ can take so that the latter terms aren't zero due to differentiation $\rightarrow2n-2k=0\Rightarrow k=n$. So, after putting $x=1$, we get \begin{align*} 2^{2n}(2n)!&=\sum_{k=0}^{n}(-1)^k(4n-2k)(4n-2k-1)\cdots(2n-2k+1){2n\choose k}\\ 2^{2n}&=\sum_{k=0}^n{\left( -1 \right) ^k\left( \begin{array}{c} 4n-2k\\ 2n\\\end{array} \right) \left( \begin{array}{c} 2n\\ k\\\end{array} \right)} \end{align*}

Answer 2

Using the binomial series $\sum_{k=0}^\infty\binom{2n+k}{2n}z^k=(1-z)^{-2n-1}$, we have $$f(z):=\sum_{k=0}^\infty\binom{2n+2k}{2n}z^{2k}=\frac12\big((1-z)^{-2n-1}+(1+z)^{-2n-1}\big),$$ so that $\binom{4n-2k}{2n}=[z^{2n-2k}]f(z)$ using the "coefficient-of" notation.

Since $(-1)^k\binom{2n}{k}=[z^{2k}](1-z^2)^{2n}$, we can see a coefficient of a product: \begin{align*} \sum_{k=0}^n(-1)^k\binom{2n}{k}\binom{4n-2k}{2n}&=[z^{2n}]\big((1-z^2)^{2n}f(z)\big) \\&=\frac12[z^{2n}]\left(\frac{(1+z)^{2n}}{1-z}+\frac{(1-z)^{2n}}{1+z}\right) \\&=[z^{2n}]\frac{(1+z)^{2n}}{1-z}\qquad\color{gray}{\text{[symmetry]}} \\&=[z^{2n}]\left(\frac{(1+z)^{2n}-2^{2n}}{1-z}+\frac{2^{2n}}{1-z}\right)=2^{2n}, \end{align*} because the last parenthesized expression is the sum of a polynomial of degree $2n-1$ (which then doesn't contribute to the coefficient of $z^{2n}$) and an ordinary geometric series $2^{2n}\sum_{k=0}^{\infty}z^k$.

Answer 3

We seek to show that $$\sum_{k=0}^n (-1)^k {4n-2k\choose 2n} {2n\choose k} = 2^{2n}.$$ The LHS is $$\sum_{k=0}^n (-1)^k {4n-2k\choose 2n-2k} {2n\choose k} \\ = [z^{2n}] (1+z)^{4n} \sum_{k=0}^n (-1)^k z^{2k} (1+z)^{-2k} {2n\choose k}.$$

The coefficient extractor enforces the range ($[z^{2n}] z^{2k} (1+z)^{4n-2k}= 0$ when $k\gt n$ because $z^{2k} (1+z)^{4n-2k} = z^{2k}+\cdots$) and we get $$[z^{2n}] (1+z)^{4n} \sum_{k\ge 0} (-1)^k z^{2k} (1+z)^{-2k} {2n\choose k} \\ = [z^{2n}] (1+z)^{4n} \left(1-\frac{z^2}{(1+z)^2}\right)^{2n} = [z^{2n}] (1+2z)^{2n} = 2^{2n}.$$

Answer 4

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\bbox[10px,#ffd]{\sum_{k = 0}^{n}\pars{-1}^{k}{4n - 2k \choose 2n} {2n \choose k}} = \sum_{k = 0}^{\infty}{2n \choose k}\pars{-1}^{k}{4n - 2k \choose 2n - 2k} \\[5mm] = &\ \sum_{k = 0}^{\infty}{2n \choose k}\pars{-1}^{k}{-2n - 1 \choose 2n - 2k} = \sum_{k = 0}^{\infty}{2n \choose k}\pars{-1}^{k} \bracks{z^{2n - 2k}}\pars{1 + z}^{-2n - 1} \\[5mm] = &\ \bracks{z^{2n}}\pars{1 + z}^{-2n - 1} \sum_{k = 0}^{\infty}{2n \choose k}\pars{-z^{2}}^{k} \\[5mm] = &\ \bracks{z^{2n}}\pars{1 + z}^{-2n - 1}\ \underbrace{\pars{1 - z^{2}}^{2n}}_{\ds{\pars{1 - z}^{2n}\pars{1 + z}^{2n}}} \\[5mm] = &\ \bracks{z^{2n}}\pars{1 - z}^{2n}\pars{1 + z}^{-1} = \sum_{i = 0}^{2n}{n \choose i}\pars{-1}^{i} \sum_{j = 0}^{\infty}\pars{-1}^{j}\bracks{i + j = 2n} \\[5mm] = &\ \sum_{i = 0}^{2n}{n \choose i}\pars{-1}^{i} \pars{-1}^{2n - i}\bracks{2n - i \geq 0} =\ \sum_{i = 0}^{2n}{n \choose i} = \bbx{\large 2^{2n}} \end{align}