Evaluating Combination Sum $\sum{n+k\choose 2k} 2^{n-k}$ Evaluate $$\sum_{k=0}^n{n+k\choose 2k} 2^{n-k}$$
So im not really sure how to begin with this. I would imagine we start with dividing out $2^{n}$, but not really sure much past that

Let's rewrite our sum $S(2n)$ as $\sum_l\binom{2n-l}l2^l$.
Recall that $\binom{2n-l}l$ is the number of tilings of a rectangle $1\times 2n$ by $l$ dominoes and $2n-2l$ squares (we choose which of $2n-l$ tiles are dominoes). So $S(2n)$ counts the number of tiling of a rectangle $1\times 2n$ by squares and two kinds of dominoes.
So obviously $S(N)=S(N-1)+2S(N-2)$ (cf. Fibonacci numbers). This linear recurrence can be solved using standard methods.
