How to prove that $\sum_{k=0}^{\frac{n}{2}} C(n,2k) 3^{n-2k} = 2^{n-1}(2^n+1)$?

Question

anonymous · Answer

@KingGeorge Would you mind giving a hand here?

kinggeorge · Answer

Presumably $n$ is even, so let's first rewrite the sum as$$\sum_{k=0}^n\binom{2n}{2k}3^{2n-2k}$$and see if that helps.

kinggeorge · Answer

I'm just going to jot down whatever I can think of, and maybe I'll get somewhere.$$(1+3)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}3^{2n}=4^{2n}$$

kinggeorge · Answer

$$2^{2n-1}(2^{2n}+1)=2^{4n-1}+2^{2n-1}=\frac{4^{2n}}{2}+\frac{4^n}{2}$$

kinggeorge · Answer

We also have the identity$$(-3+1)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}(-3)^{2n-k}=(-2)^{2n}=2^{2n}$$

kinggeorge · Answer

And $$(3^2+1)^n=\sum_{k=0}^n\binom{n}{k}3^{2n-2k}=10^n=2^n5^n$$

kinggeorge · Answer

Ah. I think I finally got something. Consider this$$\begin{aligned}
(-3+1)^{2n}+(3+1)^{2n}&=\sum_{k=0}^{2n}\binom{2n}{k}(-3)^{2n-k}+\sum_{k=0}^{2n}\binom{2n}{k}(3)^{2n-k} \
&=\sum_{k=0}^{2n}\binom{2n}{k}\left(3^{2n-k}+(-3)^{2n-k}\right)\
&=\sum_{k=0}^{2n}\binom{2n}{2k}2\cdot3^{2n-2k}\
&=(-2)^{2n}+4^{2n}=2^{2n}+4^{2n}.
\end{aligned}$$
In the last sum I wrote, we know that $\binom{2n}{2k}=0$ for any $k>n$, and we can pull the 2 out to get$$2^{2n}+2^{4n}=2\sum_{k=0}^n\binom{2n}{2k}3^{2n-2k}$$and so when we divide by 2, it follows that$$\sum_{k=0}^n\binom{2n}{2k}3^{2n-2k}=2^{2n-1}+2^{4n-1}=2^{2n-1}(2^n+1).$$