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
 A: The method used here is that of the generating function. Let $S_{n}$ be the series to be summed
\begin{align}
S_{n} = \sum_{k=0}^{n} \binom{n+k}{2k} \ 2^{n-k}.
\end{align}
The generating function and its reduction are as follows.
\begin{align}
\sum_{n=0}^{\infty} S_{n} \frac{t^{n}}{2^{n}} &= \sum_{n=0}^{\infty} \sum_{k=0}^{n} \binom{n+k}{2k} \ 2^{n-k} \ \frac{t^{n}}{2^{n}} \\
&= \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} \binom{n+2k}{2k} \ 2^{-k} t^{n+k} \\
&= \sum_{k=0}^{\infty} \frac{t^{k}}{2^{k}} \cdot \sum_{n=0}^{\infty} \frac{(2k+1)_{n} t^{n}}{n!} \\
&= \sum_{k=0}^{\infty} \frac{t^{k}}{2^{k}} \cdot (1-t)^{-2k-1} \\
&= \frac{1}{1-t} \sum_{k=0}^{\infty} \left( \frac{t}{2(1-t)^{2}} \right)^{k} 
= \frac{1-t}{1 - (5/2)t + t^{2}}. 
\end{align}
Now,
\begin{align}
\frac{1-t}{1 - (5/2)t + t^{2}} &= \frac{1-t}{(1/2-t)(2-t)} = \frac{2}{3} \left[ \frac{1}{1-2t} + \frac{1}{2(1-t/2)} \right] \\
&= \sum_{n=0}^{\infty} \left[ \frac{2^{2n+1}+1}{3 \cdot 2^{n}} \right] \ t^{n}
\end{align}
and
\begin{align}
\sum_{n=0}^{\infty} S_{n} \frac{t^{n}}{2^{n}} = \sum_{n=0}^{\infty} \left[ \frac{2^{2n+1}+1}{3 \cdot 2^{n}} \right] \ t^{n}
\end{align}
which yields
\begin{align}
\sum_{k=0}^{n} \binom{n+k}{2k} \ 2^{n-k} = \frac{2^{2n+1}+1}{3}. 
\end{align}
A: 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.
