Prove that $$\sum_{i=0}^n {{n+i}\choose {i}} 2^{-(n+i)} = 1 $$ I tried a direct approach and proof by induction, but the dependence of the exponent on $i$ throws me off every time.


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 for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

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


  • In (1) we apply the coefficient of operator.

  • In (2) we use the linearity of the coefficient of operator and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

  • In (3) we apply the finite geometric series formula.

  • In (4) we simplify the denominator and apply again the rule from (2).

  • In (5) we observe that only the first term $\left(\frac{1+z}{2z}\right)^{n+1}$ gives a non-zero contribution to the coefficient of $[z^{-1}]$. We also do some more simplifications and apply again the rule from (2).

  • In (6) we expand the geometric series $\frac{1}{1-z}=1+z+z^2+\cdots$ and select the coefficient of $z^j$ with $0\leq j\leq n$.

  • 1
    $\begingroup$ your coefficient of approach hit again ! $\endgroup$ – G Cab Feb 2 '18 at 16:21
  • $\begingroup$ @GCab: Thanks! :-) $\endgroup$ – Markus Scheuer Feb 2 '18 at 16:21

A nice way to visualise this problem is in terms of monotonic North/East (NE) lattice paths.

If the probability of a North step is $1/2$ and of and East step is $1/2$ then, starting at $O(0,0)$ the probability that a path which leaves the box takes the leg between lattice points $(i,n)$ and $(i,n+1)$ is


This is also the probability a NE lattice path passes between $(n,i)$ and $(n+1,i)$.

The probability that a lattice path leaves the box defined by boundaries

$$\{y=-1/2,\, y=n+1/2,\, x=-1/2,\, x=n+1/2\}\tag{1}$$

is therefore the sum of probabilities that it leaves through boundary $y=n+1/2$ and boundary $x=n+1/2$. These are each:


and since every such NE lattice path must leave the box as defined by $(1)$ the sum of these two probabilities is $1$:




as required.

  • 1
    $\begingroup$ Nice approach. (+1) $\endgroup$ – Markus Scheuer Feb 2 '18 at 16:24
  • $\begingroup$ Thanks Markus! I did it with your method using pen and paper (just to see if I could) but then saw you had already answered (+1 btw). So, for variation, I posted my other approach. I was pleased that you posted, though, because you confirmed for me that I had used your method correctly. Thanks again! :D $\endgroup$ – N. Shales Feb 2 '18 at 16:29
  • 1
    $\begingroup$ You're welcome, and I appreciate your lattice path approach. Sometimes I also like to do so. :-) $\endgroup$ – Markus Scheuer Feb 2 '18 at 16:33

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.