How can it be shown that : $$\sum_{r=0}^n\binom {-n-1}r\left(-\frac 12\right)^r=\sum_{r=n+ 1}^\infty\binom {-n-1}r\left(-\frac 12\right)^r=2^n$$ ?

This is confirmed by wolframalpha here and here.

We know that

$$\sum_{r=0}^\infty\binom {-n-1}r\left(-\frac 12\right)^r=\left(1-\frac 12\right)^{-n-1}=2^{n+1}$$ which can be easily confirmed by binomial expansion, but does not seem helpful for solving the above.

Addendum: An algebraic approach would be preferred.

Addendum 2: I arrived at this whilst trying to solve this other question here.

  • $\begingroup$ There are "two different types" of binomial theorems. One is more generalized, and the other is the standard you learn in class. The generalized one is called Newton's generalized binomial theorem.$$(a+b)^n=\sum\limits_{k\geq0}\binom nka^{n-k}b^k$$ $\endgroup$ – Frank Aug 28 '17 at 13:29
  • $\begingroup$ @Frank - Yes that's right. You mean Newton. $\endgroup$ – hypergeometric Aug 28 '17 at 13:30
  • $\begingroup$ Yes I changed it. $\endgroup$ – Frank Aug 28 '17 at 13:52
  • 1
    $\begingroup$ Maybe helpful: math.stackexchange.com/questions/95236/… $\endgroup$ – user940 Aug 28 '17 at 14:22

Use the equation ${-n-1\choose r}=(-1)^r{r+n\choose n}$ to rewrite your negative binomial coefficient, and rearrange the desired expression to $$\sum_{r=0}^n{r+n\choose n}\left({1\over 2}\right)^{r+n}=1,$$ or $$\sum_{k=n}^{2n}{k\choose n}\left({1\over 2}\right)^{k}=1.$$

Now consider a probability exercise.

Toss a fair coin until you get either $n+1$ heads or $n+1$ tails, and let $N$ be the number coin tosses needed to achieve this. We get $N=k+1$ by either $n$ heads in the first $k$ tosses followed by a head, or $n$ tails in the first $k$ tosses followed by a tail.

Therefore for $k\leq n\leq 2n$,
$$\mathbb{P}(N=k+1)=2{k\choose n}\left({1\over2}\right)^{k}\left({1\over2}\right) = {k\choose n}\left({1\over2}\right)^{k}.$$ Since these exhaust all possible values for $N$, the probabilities add up to one.

  • $\begingroup$ Thanks for your answer (+1) (and for the edit). I'd like to know if there's an algebraic approach to the solution. $\endgroup$ – hypergeometric Aug 28 '17 at 14:10
  • 1
    $\begingroup$ This is equation (5.20) in Concrete Mathematics by Graham, Knuth, and Patashnik. They do not use probability to derive the result. $\endgroup$ – user940 Aug 28 '17 at 14:20
  • $\begingroup$ Interesting. I arrived at this whilst trying to solve this other question here. $\endgroup$ – hypergeometric Aug 28 '17 at 14:27
  • $\begingroup$ Equation 5.20 in Concrete Mathematics is a very useful reference indeed. $\endgroup$ – hypergeometric Aug 29 '17 at 15:22

We can use Induction. The base case is simple. Assume it's true for $n-1$, then $$ \begin{align} &\sum_{k=0}^n\binom{-n-1}{k}\left(-\frac12\right)^k\\ &=\sum_{k=0}^n\binom{n+k}{k}\left(\frac12\right)^k\tag{1}\\ &=\binom{2n}{n}\left(\frac12\right)^n+\sum_{k=0}^{n-1}\left[\binom{n+k-1}{k-1}+\binom{n+k-1}{k}\right]\left(\frac12\right)^k\tag{2}\\ &=\binom{2n}{n}\left(\frac12\right)^n+\sum_{k=0}^{n-1}\binom{n+k-1}{k-1}\left(\frac12\right)^k+2^{n-1}\tag{3}\\ &=\binom{2n}{n}\left(\frac12\right)^n+\frac12\sum_{k=0}^{n-2}\binom{n+k}{k}\left(\frac12\right)^k+2^{n-1}\tag{4}\\ &=\frac12\sum_{k=0}^n\binom{n+k}{k}\left(\frac12\right)^k+2^{n-1}\tag{5}\\[9pt] &=2^n\tag{6} \end{align} $$ Explanation:
$(1)$: convert to positive binomial coefficient
$(2)$: use Pascal's relation
$(3)$: use inductive hypothesis
$(4)$: reindex
$(5)$: $\binom{2n}{n}\left(\frac12\right)^n=\frac12\binom{2n}{n}\left(\frac12\right)^n+\frac12\binom{2n-1}{n-1}\left(\frac12\right)^{n-1}$
$(6)$: subtract $(1)$ from $2$ times $(5)$

  • $\begingroup$ Thanks for your solution (+1). $\endgroup$ – hypergeometric Aug 28 '17 at 17:32
  • $\begingroup$ $\texttt{Mathematica}$ $$ yields the wrong answer $\color{red}{0}$. $\endgroup$ – Felix Marin Apr 14 '18 at 14:58

Here is an answer based upon generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write e.g. \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

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


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

  • In (2) we change the order of summation $r \rightarrow n-r$.

  • In (3) we apply the coefficient of operator. We also set the limit to $\infty$ without changing anything since we are adding zeros only.

  • In (4) we do a rearrangement and apply the formula $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

  • In (5) we apply the geometric series expansion.

  • In (6) we do some simplifications.

  • In (7) we do the Cauchy multiplication with the geometric series $\frac{1}{1-x}$ and restrict the upper limit of the sum with $n$ since other terms do not contribute to $[z^n]$.

  • In (8) we select the coefficient of $z^k$.

  • In (9) we apply the binomial theorem.

  • $\begingroup$ Thanks for your solution (+1). $\endgroup$ – hypergeometric Aug 29 '17 at 15:21
  • $\begingroup$ @hypergeometric: You're welcome! :-) $\endgroup$ – Markus Scheuer Aug 29 '17 at 15:27

Here's another approach:

$$\begin{align} \sum_{r=0}^n \binom {-n-1}r\left(-\frac 12\right)^r &=\sum_{r=0}^n\binom {r+n}n2^{-r}\\ &=\frac 1{2^n} \sum_{r=0}^n \binom {r+n}r2^{n-r}\\ &=\frac 1{2^n}\sum_{r=0}^n \binom {r+n}n\sum_{j=0}^{n-r}\binom {n-r}j\\ &=\frac 1{2^n}\sum_{l=0}^n\binom {2n-l}{n-l}\sum_{j=0}^l\binom lj &&(l=n-r)\\ &=\frac 1{2^n}\sum_{j=0}^n\sum_{l=j}^n\binom {2n-l}{n-l}\binom lj\\ &=\frac 1{2^n}\sum_{j=0}^n\binom {2n+1}{n+j+1} &&(*)\\ &=\frac 1{2^n}\cdot \frac 12 \sum_{j=0}^{2n+1}\binom {2n+1}j &&\text{(by symmetry)}\\ &=\frac 1{2^{n+1}}\cdot 2^{2n+1}\\ &=2^n\;\;\color{red}\blacksquare\\\\ ^* \scriptsize \text {using } \sum_r \binom {a+r}c\binom {b+r}d &\scriptsize =\binom {a+b+1}{c+d+1} \end{align}$$

It follows that

$$\begin{align} \sum_{r=n+1}^\infty\binom {-n-1}r\left(-\frac 12\right)^r &=\sum_{r=0}^\infty\binom {-n-1}r\left(-\frac 12\right)^r-\sum_{r=0}^n\binom {-n-1}r\left(-\frac 12\right)^r\\ &=\left(1-\frac 12\right)^{-n-1}-2^n\\ &=2^{n+1}-2^n\\ &=2^n\;\;\color{red}\blacksquare \end{align}$$ Hence $$\sum_{r=0}^n\binom {-n-1}r\left(-\frac 12\right)^r=\sum_{r=n+1}^\infty\binom {-n-1}r\left(-\frac 12\right)^r=2^n$$


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.