# 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?

• Isn't it this (wolframalpha.com/share/…) what you wanted to put in Wolfram Alpha? – user119256 Jan 9 '14 at 19:25
• I can't copy your link. Here is the input for Wolfram|Alpha: Sum[(-1)^s*x^(2s)*Binom(m+s,s),{s,0,m}]. – soul-of-kitchen Jan 9 '14 at 19:27
• Why your Binom part has Binom(m+s,s) instead of Binom(m+s+1,2s)? And $(-1)^{s}$ instead of $(-1)^{m-s}$? – user119256 Jan 9 '14 at 19:29
• @karene, I see now. You put original sum to the wolfram. It looks simplier, but I do not know how to prove that the sum of the original sequence is equal to $-2n-3$. – soul-of-kitchen Jan 9 '14 at 19:34
• @soul-of-kitchen There are many ways to prove this, but since it is homework, the reasonable first step would be to ask what methods you have recently learned. – Phira Jan 11 '14 at 0:07

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

• Generating function with coefficients $S_n=\sum_{s=0}^{n}{(-1)}^{n-s-1}4^s\binom{n+s}{2s}$ is following: $-\frac{x+1}{{(x-1)}^2}$. But how it will help me to find exact value of $S_n$? – soul-of-kitchen Jan 11 '14 at 10:14
• @soul-of-kitchen Excellent, now you just have to re-expand $(1-x)^{-2}$ with binomial coefficients (or simply know/lookup the particular expansion). – Phira Jan 11 '14 at 10:31
• @soul-of-kitchen Alternatively, since you know the desired result, you can try to get the generating function for ${(-1)}^m(2m+1)$ and compare. – Phira Jan 11 '14 at 10:32
• Well, I know generating function, because I know that $S_n=\sum_{s=0}^{n+1}{(-1)}^{n-s}4^sC_{n+s+1}^{2s}=-2n-3$, but I can not prove that $S_n=-2n-3$. – soul-of-kitchen Jan 11 '14 at 11:27
• @soul-of-kitchen Write down the generating function of the sequence with only $(-1)^m$, and of the sequence $m(-1)^m$ (interpret it as a derivative). Deduce the generating function of the right-hand side of your identity. – Phira Jan 11 '14 at 22:13

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