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

Question

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?

Answer 1

Hint: Consider organizing the subsets by what the $(i+1)$th element is.

Answer 2

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.