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?
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$.