<s>[INST] Show that $\sum\limits_{i=0}^{n/2} {n-i\choose i}2^i = \frac13(2^{n+1}+(-1)^n)$ While doing a combinatorial problem, with $n$ being even, I came up with the expression
$$\sum_{i=0}^{n/2} {n-i\choose i}2^i$$
for which I used wolfram to get a closed form expression of $\dfrac{1}{3}\left(2^{n+1}+(-1)^n\right)$. 
Is there an easy way to obtain this closed-form?
Also, if there are any good references for binomial coefficient identities like these I'd appreciate it. I searched some but did not find any similar to this.
 [/INST] One way is by considering generating functions.
Denoting $\displaystyle a_n = \sum_{k=0}^{n} 2^k{n-k\choose k}$ 
(where, we use the notation $\displaystyle \binom{n}{m} = 0$ for $m > n$)
$\displaystyle \begin{align}
\sum_{n=0}^\infty a_nx^n
&=\sum_{n=0}^\infty x^n\sum_{k=0}^n2^k\binom{n-k}{k} =\sum_{k=0}^\infty\sum_{n=k}^\infty2^kx^n\binom{n-k}{k}=\sum_{k=0}^\infty\sum_{n=0}^\infty2^kx^{n+k}\binom{n}{k}\\
&=\sum_{k=0}^\infty2^kx^k\frac{x^k}{(1-x)^{k+1}}=\frac{1}{1-x}\sum_{k=0}^\infty2^k\left(\frac{x^2}{1-x}\right)^k\\
&=\frac{1}{1-x}\frac{1}{1-\frac{2x^2}{1-x}}\\
&=\frac{1}{1-x-2x^2}\end{align}$
Using partial fractions to decompose: 
$\displaystyle \frac{1}{1-x-2x^2} = \frac{1}{3}\left(\frac{2}{1-2x}+\frac{1}{1+x}\right) = \sum_{n=0}^{\infty} \frac{2^{n+1}+(-1)^n}{3}x^n$
Thus, $\displaystyle a_n = \frac{2^{n+1}+(-1)^n}{3}$
</s>