Prove that for all positive integers n, the following identity holds: $\sum_{k=0}^n \binom {2n}{2k} 2^{2k-2n} = \frac{3^{2n}+1}{2}$

Question

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

How do I prove this using combinatorial proof? Is it: first choose $2k$ object out of $2n$ objects? What do I say about the $2^{2k-2n}$ part?

Answer 1

Note to OP: the factor $2^{2k-2n}$ should be $2^{2n-2k}$.

By binomial Series: $$(1+x)^{2n}=\sum_{k=0}^{2n} {2n \choose k} x^k~~~~`(1)$$ anf $$(1-x)^{2n}=\sum_{k=0}^{2n} {2n \choose k} (-x)^k~~~~~(1)$$ we add (1) and (2) to get: $$\sum_{k=0}^{n} {2n \choose 2k} x^{2k}=\frac{(1+x)^{2n}+(1-x)^{2n}}{2}$$ By putting $x=2$, We get $$\sum_{k=0}^{n} {2n \choose 2k} 2^{2k}=\frac{3^n+1}{2}$$ $$\implies \sum_{k=0}^{2n} {2n \choose 2k} 2^{2k}=\frac{3^n+1}{2}$$ Change $2k$ to $2n-2k$ to get $$\implies \sum_{k=0}^{2n} {2n \choose 2k} 2^{2n-2k}=\frac{3^n+1}{2}$$ $$\implies \sum_{k=0}^{n} {2n \choose 2k} 2^{2n-2k}=\frac{3^n+1}{2}$$

Answer 2

Note the binomial theorem can be proven, and interpreted, combinatorially, such as shown in Combinatorics/Binomial Theorem. Using this, and interpreting the binomial theorem results combinatorically, you can get

$$3^{2n} = (2+1)^{2n} = \sum_{k=0}^{2n}\binom{2n}{k}(2^{2n-k})(1^{k}) \tag{1}\label{eq1A}$$

$$1 = 1^{2n} = (2-1)^{2n} = \sum_{k=0}^{2n}\binom{2n}{k}(2^{2n-k})((-1)^{k}) \tag{2}\label{eq2A}$$

Adding \eqref{eq1A} and \eqref{eq2A}, the terms with even $k$ are doubled and the terms with odd $k$ cancel out, so if you then divide by $2$, you get

$$\sum_{k=0}^{n}\binom{2n}{2k}2^{2n-2k} = \frac{3^{2n}+1}{2} \tag{3}\label{eq3A}$$