Looking for a combinatorial proof of $\sum_{k=0}^n \binom{n}{k} *2^k=\frac{3^n+(-1)^n}{2}$ where the sum over even numbers

Question

I am looking for a combinatorial proof of $\sum_{k=0}^n \binom{n}{k} *2^k=\frac{3^n+(-1)^n}{2}$ where the sum over even numbers. This is simple via recursive series or algebraically using the binomial theorem but I have no idea how to prove it combinatorically.

Answer 1

Both expression count the number of sequences of $n$ digits all equal to $0,1$ or $2$ such that the number of nonzero digits is even.

Left hand side

The summation index $k$ represents the number of nonzero digits, $\binom{n}k$ is the choice of digits, and $2^k$ describes how to choose which are $1$ and which are $2$.

Right hand side

Let's divide almost all of the $3^n$ sequences of ternary digits into pairs where exactly one sequence in each pair has an even number of nonzero digits. Namely, the "mate" of every sequence is given by finding the first digit which is either $0$ or $1$ and replacing it with $1$ or $0$.

Every sequence except for the sequence of all $2$'s is given a mate; of the other $3^n-1$ sequences, exactly half of them have an even number of nonzero digits, for $(3^n-1)/2$ such sequences. The remaining sequence of all $2$s contributes towards this count only if $n$ is even, leading to $(1+(-1)^n)/2$. Adding these together gives $(3^n+(-1)^n)/2$.