Sum of Diagonal in Pascals triangle with power of 2 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. 
 A: 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$.
A: 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.
