$\begingroup$

Give a combinatorial proof that $\displaystyle\sum_{i=0}^n {n+i\choose i}\frac{1}{2^i} = 2^n$.

I'm not sure if Pascal's identity is useful here. Or perhaps there is a way involving binary strings? $2^n$ is the number of binary strings of length $n$, so if there was some way to decompose these strings into disjoint sets $B_i$ with cardinality ${n+i\choose i}\frac{1}{2^i}$, a proof using that method might work. ${n+i\choose i}$ is the number of binary strings of length $n+i$ with exactly $i$ ones, since one can choose $i$ of the $n+i$ positions to be ones in ${n+i\choose i}$ ways and make the rest zeroes in one way. Then we divide by the number of binary strings of length $i$, though I'm not sure how to deduce the combinatorial significance of this. I'm most likely thinking of this the wrong way.

Answers