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?
 A: Interestingly, this has a very similar idea to what I have answered today, let's thank again the very very useful Pascal's Identity:
$${n + k \choose 2k} = {n - 1 + k\choose 2k} + {n - 1 + k \choose 2k - 1}.$$
Let
$$S_n=\sum_{k = 0}^n (-4)^k {n + k\choose 2k}$$
and $$T_n = \sum_{k = 0}^n (-4)^k {n -1+ k\choose 2k-1}.$$
Using Pascal's identity we have
\begin{align*}\sum_{k = 0}^n (-4)^k {n + k\choose 2k} &= \sum_{k = 0}^n (-4)^k {n - 1 +k\choose 2k} + \sum_{k = 0}^n (-4)^k {n - 1+k\choose 2k - 1}\\
S_n&= S_{n - 1} + T_n \tag{1}
\end{align*}
and
\begin{align*}\sum_{k = 0}^{n + 1} (-4)^k {n + k\choose 2k-1} &= \sum_{k = 0}^{n+1} (-4)^k {n - 1 +k\choose 2k-1} + (-4)\sum_{k = 0}^{n+1} (-4)^{k-1} {n - 1+k\choose 2k - 2}\\
T_{n+1}&= T_n -4S_n \tag{2}
\end{align*}
From $(1)$ and $(2)$ we got the recurrence relation $S_{n+1} + 2S_n + S_{n - 1}=0$ with initial condition $S_0 = 1$ and $S_1 = -3$. This gives us the solution $$S_n = (-1)^n(2n +1).$$
You can then, if you're interested, use this method to find a formula of a more general sum: $$\sum_{k = 0}^n x^k{n + k\choose 2k}.$$
A: Suppose we seek to evaluate
$$\sum_{k=0}^n (-1)^k 2^{2k} {n+k\choose 2k}.$$
This is
$$\sum_{k=0}^n (-1)^k 2^{2k} {n+k\choose n-k}
\\ = [z^n] (1+z)^n \sum_{k=0}^n (-1)^k 2^{2k} z^k (1+z)^k.$$
The coefficient extractor enforces the upper range and we find
$$[z^n] (1+z)^n \sum_{k\ge 0} (-1)^k 2^{2k} z^k (1+z)^k
\\ = [z^n] (1+z)^n \frac{1}{1+4z(1+z)}
= [z^n] (1+z)^n \frac{1}{(1+2z)^2}.$$
This is
$$\underset{z}{\mathrm{res}}\;
\frac{1}{z^{n+1}} (1+z)^n \frac{1}{(1+2z)^2}.$$
Now put $z/(1+z)=w$ so that $z=w/(1-w)$ and $dz = 1/(1-w)^2\; dw$ to
obtain
$$\underset{w}{\mathrm{res}}\;
\frac{1}{w^{n}} \frac{1-w}{w} \frac{(1-w)^2}{(1+w)^2}
\frac{1}{(1-w)^2}
= \underset{w}{\mathrm{res}}\;
\frac{1-w}{w^{n+1}} \frac{1}{(1+w)^2}.$$
This is
$$(-1)^n (n+1) - (-1)^{n-1} n$$
or
$$\bbox[5px,border:2px solid #00A000]{
(-1)^n (2n+1).}$$
A: 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$.
