<s>[INST] Sum of binomial coefficient with 'skips' 
Find
$$\sum_{k=0}^{n}
{(-4)}^k{n+k\choose2k}$$

I have dealt with such summations with variable $n$ in ${n \choose k}$ before, but never have seen one in which some $k$'s were skipped (like $1,3,5$...).
Can someone please give me a hint as to how to proceed?
 [/INST] Snake oil:
\begin{align}
\sum_{n=0}^\infty\left(\sum_{k=0}^n (-4)^k \binom{n+k}{2k}\right)z^n
&= \sum_{k=0}^\infty (-4)^k \sum_{n=k}^\infty \binom{n+k}{2k} z^n \\
&= \sum_{k=0}^\infty (-4z)^k \sum_{n=0}^\infty \binom{n+2k}{2k} z^n \\
&= \sum_{k=0}^\infty (-4z)^k \frac{1}{(1-z)^{2k+1}} \\
&= \frac{1}{1-z}\sum_{k=0}^\infty \left(\frac{-4z}{(1-z)^2}\right)^k \\
&= \frac{1}{1-z}\cdot\frac{1}{1-\frac{-4z}{(1-z)^2}} \\
&= \frac{1-z}{(1+z)^2} \\
&= (1-z)\sum_{n=0}^\infty (n+1)(-z)^n \\
&= \sum_{n=0}^\infty (n+1)(-1)^n z^n - \sum_{n=0}^\infty (n+1)(-1)^n z^{n+1} \\
&= \sum_{n=0}^\infty (n+1)(-1)^n z^n -\sum_{n=1}^\infty n(-1)^{n-1} z^n \\
&= \sum_{n=0}^\infty (2n+1)(-1)^n z^n \\
\end{align}
So
$$\sum_{k=0}^n (-4)^k \binom{n+k}{2k} = (2n+1)(-1)^n$$
for $n \ge 0$.
</s>