Sum of Diagonal in Pascals triangle with power of 2

Question

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.

Answer 1

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*}

Comment:

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

Answer 2

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

$$\binom{n+i}{i}2^{-(n+i+1)}$$

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:

$$\sum_{i=0}^{n}\binom{n+i}{i}2^{-(n+i+1)}$$

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

$$2\sum_{i=0}^{n}\binom{n+i}{i}2^{-(n+i+1)}=1$$

or

$$\sum_{i=0}^{n}\binom{n+i}{i}2^{-(n+i)}=1$$

as required.