<s>[INST] Prove $\sum_{m=i}^{n}2^{n-m}\binom{m}{i}=\binom{n+1}{i+1}+\ldots+\binom{n+1}{n+1}=\sum_{m=i}^{n}\binom{n+1}{m+1}$ without induction I would like to prove the following: $$\sum_{m=i}^{n}2^{n-m}\binom{m}{i} = \binom{n+1}{i+1}+\binom{n+1}{i+2}+\ldots+\binom{n+1}{n+1} = \sum_{m=i}^{n}\binom{n+1}{m+1}$$
which is quite easy to prove by induction. I'm looking for an algebraic or combinatoric approach. This shouldn't be very complicated from a combinatoric point of view, since the right hand side is the number of different subsets of the set $\{1, 2,  \ldots, n+1\}$ with at least $i+1$ elements. Also on the left hand side $2$ appears, which arises when one counts the total number of subsets. But I struggle to find a method to count this number to make it look like the left hand side; what do you suggest?
 [/INST] Here is an algebraic proof. We get for the RHS
$$\sum_{m=q}^n {n+1\choose m+1} =
\sum_{m=q}^n {n+1\choose n-m}
= [z^n] \sum_{m=q}^n z^m (1+z)^{n+1}.$$
Here the coefficient extractor enforces the range and we get
$$[z^n] (1+z)^{n+1} \sum_{m\ge q} z^m
= [z^n] (1+z)^{n+1} \frac{z^q}{1-z}.$$
This is
$$\mathrm{Res}_{z=0} \frac{1}{z^{n+1}} (1+z)^{n+1}
\frac{z^q}{1-z}.$$
Letting $z/(1+z) = w$ we get $z=w/(1-w)$ and $dz = 1/(1-w)^2 \; dw$
so this becomes
$$\mathrm{Res}_{w=0} \frac{1}{w^{n+1}} 
\frac{w^q}{(1-w)^q} \frac{1}{1-w/(1-w)}
\frac{1}{(1-w)^2}
\\ = \mathrm{Res}_{w=0} \frac{1}{w^{n-q+1}}
\frac{1}{(1-w)^{q+1}} \frac{1}{1-2w}.$$
We get at last
$$[w^{n-q}] \frac{1}{(1-w)^{q+1}} \frac{1}{1-2w}
= \sum_{m=0}^{n-q} [w^m] \frac{1}{(1-w)^{q+1}}
[w^{n-q-m}] \frac{1}{1-2w}
\\ = \sum_{m=q}^{n} [w^{m-q}] \frac{1}{(1-w)^{q+1}}
[w^{n-m}] \frac{1}{1-2w}
\\ = \sum_{m=q}^{n} {m-q+q\choose q} 2^{n-m}
= \sum_{m=q}^n 2^{n-m} {m\choose q}.$$
This is the claim.
</s>