Find the sum of the series. I need to find the following sum:
$$\sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s}$$
First I tried to simplify this:
$$\begin{split}
\sum_{s=0}^{n+1}{(-1)}^{n-s}4^s\binom{n+s+1}{2s}
 &= {(-1)}^n\sum_{s=0}^{n+1}{(-1)}^{s}2^{2s}\binom{n+s+1}{2s} \\
 &= \left[{(-1)}^{m-1}\sum_{s=0}^m{(-1)}^{s}x^{2s}\binom{m+s}{2s}\right](2)
\end{split}
$$
Now I reduced the problem to the following:
"Find generating function for the following sequence"
$$\sum_{s=0}^m{(-1)}^{s}x^{2s}\binom{m+s}{2s}$$
Does anyone have any ideas how to solve this problem? Because if you put it to the Wolfram|Alpha result is terryfing and I hope that generating function produced by wolfram is too generalized (for any values of x and m).
UPD: I put the wrong sequece to Wolfram|Alpha, here is the correct one.
So, Wolphram|Alpha says now, that:
$$\sum_{s=0}^m{(-1)}^{s}x^{2s}\binom{m+s}{2s} = \frac{2\cos\left((2m+1)\arcsin\left(\frac2x\right)\right)}{\sqrt{4-x^2}}$$
Unfortunately, it is undefined for $x=2$. While when we set $x=2$ for initial query (Sum[(-1)^s*2^(2s)*Binom(m+s,2s),{s,0,m}]) the answer is following:
$$\sum_{s=0}^m{(-1)}^{s}2^{2s}\binom{m+s}{2s} = {(-1)}^m(2m+1)$$
And I still wondering, how to prove that?
 A: If you want to apply generating functions, you should not usually replace a random constant in the sum with a variable (although in this particular case this works, too). You should call the whole sum $S_n$ and look at the generating function with coefficients $S_n$.
A: Suppose we seek to evaluate
$$\sum_{q=0}^{n+1} (-1)^{n-q} 4^q {n+q+1\choose 2q}
= (-1)^n \sum_{q=0}^{n+1} (-1)^{q} 4^q {n+q+1\choose n+1-q}.$$
We use the integral
$${n+q+1\choose n+1-q} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n+q+1}}{z^{n-q+2}} \; dz.$$
This has the property that it is zero when $q\gt n+1$ so we may extend
$q$ to infinity to get
$$\frac{(-1)^n}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n+1}}{z^{n+2}} 
\sum_{q\ge 0} (-1)^{q} 4^q (1+z)^q z^q\; dz.$$
This yields
$$\frac{(-1)^n}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n+1}}{z^{n+2}} 
\frac{1}{1+4(1+z)z} \; dz
\\ = \frac{(-1)^n}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n+1}}{z^{n+2}} 
\frac{1}{(2z+1)^2} \; dz.$$
Extracting the residue we get
$$(-1)^n \sum_{q=0}^{n+1} {n+1\choose n+1-q} \times 
(-1)^q \times (q+1) \times 2^q
\\ = (-1)^n \sum_{q=0}^{n+1} {n+1\choose q} \times 
(-1)^q \times (q+1) \times 2^q.$$
Now observe that
$$(x(1+x)^n)' = \sum_{r=0}^n {n\choose r} (r+1) x^r
= (1+x)^n + nx (1+x)^{n-1}.$$
This gives two components for the sum, the first is
$$(-1)^n (-1)^{n+1} = -1,$$
and the second is
$$(-1)^n \times (n+1) \times (-2) \times (-1)^{n}$$
for a final answer of
$$-1- 2(n+1) = -2n-3.$$
