sum of binomial series with alternate terms 
Evaluation of series $\displaystyle \sum^{n}_{k=0}(-4)^k\binom{n+k}{2k}$

what I tried:
from Binomial Identity
$$\binom{n+k}{2k}=\binom{n+k-1}{2k}+\binom{n+k-1}{2k-1}$$
series is $$\sum^{n}_{k=0}(-4)^k\binom{n+k-1}{2k}+\sum^{n}_{k=0}(-4)^k\binom{n+k-1}{2k-1}$$
let $\displaystyle S_{1}=\sum^{n}_{k=0}\binom{n+k-1}{2k}=\binom{n-1}{0}-4\binom{n}{2}+4^2\binom{n+1}{4}+\cdots +(-4)^n\binom{2n-1}{2n}$
let $\displaystyle S_{2}=\sum^{n}_{k=0}\binom{n+k-1}{2k}=\binom{n-1}{-1}-4\binom{n}{1}+4^2\binom{n+1}{3}+\cdots +(-4)^n\binom{2n-1}{2n-1}$
Help me please
did not know to simplify $S_{1}$ and $S_{2}$
 A: With the following the purpose was to use slightly different functions
from what we saw in the answer by @MarkusScheuer. Start from
$$\sum_{k=0}^n (-4)^k {n+k\choose 2k}
= \sum_{k=0}^n (-4)^k [z^{n-k}] \frac{1}{(1-z)^{2k+1}}
\\ = [z^n] \frac{1}{1-z}
\sum_{k=0}^n (-4)^k \frac{z^k}{(1-z)^{2k}}.$$
Here the coefficient extractor enforces the range and we get
$$[z^n] \frac{1}{1-z}
\sum_{k\ge 0} (-4)^k \frac{z^k}{(1-z)^{2k}}
= [z^n] \frac{1}{1-z} \frac{1}{1+4z/(1-z)^2}
\\ = [z^n] \frac{1-z}{(1-z)^2+4z}
= [z^n] \frac{1-z}{(1+z)^2}
\\ = [z^n] \frac{1}{(1+z)^2} - [z^{n-1}] \frac{1}{(1+z)^2}
\\ = (-1)^n (n+1) - (-1)^{n-1} n = (-1)^n (2n+1).$$
A: I couldn't see a slick way to do this, but I computed a few terms and guessed that the sum is $(-1)^n(2n+1).$  In trying to prove this by induction, I ran into the sum $\sum_{k=0}^n(-4)^k\binom{n+k}{2k-1}$, just as you did.  Again, I did experiments, and guessed the sum.  This led me to the proposition
Let $$S_n=\sum_{k=0}^n(-4)^k\binom{n+k}{2k}\\ 
T_n=\sum_{k=0}^n(-4)^k\binom{n+k}{2k-1}$$
Then $$\begin{align}
S_n&=(-1)^n(2n+1)\\
T_n&=(-1)^n(4^{n+1}-4n-4)
\end{align}$$
This is easily proved by induction, provided you prove both formulas at once.  That is, show they are both true for $n=1$, assume they are both true for some $n$, and then prove they both hold for $n+1$.
A: Let 
$$S_n=\displaystyle \sum^{n}_{k=0}(-4)^k\binom{n+k}{2k}\tag{*}$$
This issue can be connected in a natural way to Chebyshev polynomials of the second kind, with explicit expression see Wikipedia article.
$$U_n(x)=\sum_{k=0}^n(-2)^k\binom{n+k+1}{2k+1}(1-x)^k\tag{1}$$
If we take $x=-1$ in (1), 
$$U_n(-1)=\sum_{k=0}^n(-4)^k\binom{n+k+1}{2k+1}=(-1)^n (n+1),\tag{2}$$
the second expression for $U_n(-1)$  being a known property (see Remark below).
Now, let us write the same expression as (2), but for $n-1$ instead of $n$ :
$$U_{n-1}(-1)=\sum_{k=0}^{n-1}(-4)^k\binom{n+k}{2k+1}=(-1)^{n-1} (n)\tag{3}$$
Subtracting (3) from (2), 
$$\sum_{k=0}^{n-1}(-4)^k\underbrace{\left(\binom{n+k+1}{2k+1}-\binom{n+k}{2k+1}\right)}_{\binom{n+k}{2k}}+(-4)^n=\underbrace{(-1)^n (n+1) - (-1)^{n-1} (n)}_{(-1)^n (2n+1)}\tag{4}$$
(we have used the classical recurrence relationship between binomial coefficients)
It is finished there because (4) expresses the fact that $S_n$ (given by (*)) is :

$$S_n=(-1)^n (2n+1)$$

Remark : Why do we have $U_n(-1)=(-1)^n (n+1)$ ?
It can be easily seen by setting $x=-1$ into the generating function of the $U_n$s :
$$\sum_{n=0}^{\infty}U_n(x)t^n=\dfrac{1}{1-2tx+t^2}$$
giving
$$\dfrac{1}{(1+t)^2}=1-2t+3t^2-4t^3+\cdots$$
A: We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$. This way we can write for instance
\begin{align*}
[z^k](1+z)^n=\binom{n}{k}\tag{1}
\end{align*}

We obtain
  \begin{align*}
\color{blue}{\sum_{k=0}^n}\color{blue}{(-4)^k\binom{n+k}{2k}}&=\sum_{k=0}^n(-4)^k\binom{n+k}{n-k}\\
&=\sum_{k=0}^n(-4)^k[z^{n-k}](1+z)^{n+k}\tag{2}\\
&=[z^n](1+z)^n\sum_{k=0}^n(-4z(1+z))^k\tag{3}\\
&=[z^n](1+z)^n\frac{1-(-4z(1+z))^{n+1}}{1+4z(1+z)}\tag{4}\\
&=[z^n](1+z)^n\frac{1}{1+4z(1+z)}\tag{5}\\
&=[z^n]\frac{(1+z)^n}{(1+2z)^2}\\
&=[z^n](1+z)^n\sum_{j=0}^\infty\binom{-2}{j}(2z)^j\tag{6}\\
&=[z^n](1+z)^n\sum_{j=0}^\infty(j+1)(-2z)^j\tag{7}\\
&=\sum_{j=0}^n(j+1)(-2)^j[z^{n-j}](1+z)^n\\
&=\sum_{j=0}^n(j+1)(-2)^j\binom{n}{n-j}\tag{8}\\
&=\sum_{j=1}^n\binom{n}{j}j(-2)^j+\sum_{j=0}^n\binom{n}{j}(-2)^j\\
&=n\sum_{j=1}^n\binom{n-1}{j-1}(-2)^j+(1+(-2))^n\tag{9}\\
&=n\sum_{j=0}^{n-1}\binom{n-1}{j}(-2)^{j+1}+(-1)^n\tag{10}\\
&=(-2n)(1+(-2))^{n-1}+(-1)^n\\
&\,\,\color{blue}{=(-1)^n(2n+1)}
\end{align*}

Comment:


*

*In (2) we apply the coefficient of operator according to (1).

*In (3) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

*In (4) we apply the finite geometric series formula.

*In (5) we skip the term which does not contribute to $[z^n]$.

*In (6) we apply the binomial series expansion.

*In (7) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

*In (8) we select the coefficient of $z^{n-j}$.

*In (9) we apply the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

*In (10) we shift the index to start with $j=0$.
