I need to find the following sum:

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"

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?

  • $\begingroup$ Isn't it this (wolframalpha.com/share/…) what you wanted to put in Wolfram Alpha? $\endgroup$ – user119256 Jan 9 '14 at 19:25
  • $\begingroup$ 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}]. $\endgroup$ – soul-of-kitchen Jan 9 '14 at 19:27
  • $\begingroup$ Why your Binom part has Binom(m+s,s) instead of Binom(m+s+1,2s)? And $(-1)^{s}$ instead of $(-1)^{m-s}$? $\endgroup$ – user119256 Jan 9 '14 at 19:29
  • $\begingroup$ @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$. $\endgroup$ – soul-of-kitchen Jan 9 '14 at 19:34
  • $\begingroup$ @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. $\endgroup$ – 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$.

  • $\begingroup$ 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$? $\endgroup$ – soul-of-kitchen Jan 11 '14 at 10:14
  • 1
    $\begingroup$ @soul-of-kitchen Excellent, now you just have to re-expand $(1-x)^{-2}$ with binomial coefficients (or simply know/lookup the particular expansion). $\endgroup$ – Phira Jan 11 '14 at 10:31
  • $\begingroup$ @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. $\endgroup$ – Phira Jan 11 '14 at 10:32
  • $\begingroup$ 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$. $\endgroup$ – soul-of-kitchen Jan 11 '14 at 11:27
  • $\begingroup$ @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. $\endgroup$ – 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.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.