Proof of $\sum_{k=0}^n{ \binom{2k}{k} 2^{2n-2k} } = (2n+1) \binom{2n}{n} = \frac{n+1}{2} \binom{2(n+1)}{n+1}$

Question

I found some combinatorial identities in my old notebooks, but I cannot recall how I derived them. Can anyone help provide the most elementary/elegant proofs for the following identity? Specifically, the connection between the summation and either of the two closed-form expressions.

$$ \sum_{k=0}^n{ \binom{2k}{k} 2^{2n-2k} } = (2n+1) \binom{2n}{n} = \frac{n+1}{2} \binom{2(n+1)}{n+1} $$

Some specific cases written out for some simple visualization: ($n=0$ through $n=3$) $$ \begin{align} \binom{0}{0} 2^{0} &= 1\binom{0}{0} = \frac{1}{2}\binom{2}{1} \\ \binom{0}{0} 2^{2} + \binom{2}{1} 2^{0} &= 3\binom{2}{1} = \frac{2}{2}\binom{4}{2} \\ \binom{0}{0} 2^{4} + \binom{2}{1} 2^{2} + \binom{4}{2} 2^{0} &= 5\binom{4}{2} = \frac{3}{2}\binom{6}{3}\\ \binom{0}{0} 2^{6} + \binom{2}{1} 2^{4} + \binom{4}{2} 2^{2} + \binom{6}{3} 2^{0} &= 7\binom{6}{3} = \frac{4}{2}\binom{8}{4} \end{align} $$

EDIT: I should specify that I have already found an inductive proof, but it is not satisfying to me. I am specifically looking for a bijective/double-counting proof ideally.

Answer 1

A Couple of "Common" Series

We have the Geometric Series $$ \sum_{k=0}^\infty 4^kx^k=\frac1{1-4x}\tag1 $$ and the Generating Function for the Central Binomial Coefficients $$ \sum_{k=0}^\infty\binom{2k}{k}x^k=\frac1{\sqrt{1-4x}}\tag2 $$ Equation $(2)$ is the Generalized Binomial Theorem applied to $\binom{-1/2}{k}=\left(-\frac14\right)^k\binom{2k}{k}$, which is shown in this answer.

---

Using the Cauchy Product

We get the product of the preceding functions by taking half the derivative of $(2)$ and adjusting the index: $$ \sum_{k=0}^\infty\frac{k+1}2\binom{2k+2}{k+1}x^k=\frac1{\sqrt{1-4x}^3}\tag3 $$ The Cauchy Product Formula then says that $$ \begin{align} \sum_{k=0}^n\binom{2k}{k}4^{n-k} &=\frac{n+1}2\binom{2n+2}{n+1}\tag4\\[3pt] &=(2n+1)\binom{2n}{n}\tag5 \end{align} $$

Answer 2

Proving the equality between the two closed form is easier:

$$\begin{align*} (2n+1)\binom{2n}n &=(2n+1)\frac{(2n)!}{n!n!}\\ &= \frac{(2n+1)!}{n!n!}\\ &= \frac{(n+1)^2}{(2n+2)}\cdot\frac{(2n+2)!}{(n+1)!(n+1)!}\\ &= \frac{n+1}{2}\binom{2(n+1)}{n+1} \end{align*}$$

By induction, consider the $n+1$ case of the summation form and the second closed-form,

$$\begin{align*} \sum_{k=0}^{n+1} \binom{2k}{k}2^{2(n+1)-2k} &= 2^2\sum_{k=0}^{n}\binom{2k}{k}2^{2n-2k} + \binom{2(n+1)}{n+1}2^0\\ &= 2^2\cdot \underbrace{\frac{n+1}{2} \binom{2(n+1)}{n+1)}}_{\text{by induction hypothesis}} + \binom{2(n+1)}{n+1}2^0\\ &= [2(n+1)+1]\binom{2(n+1)}{n+1} \end{align*}$$