Let $n\geq m\geq0$ be two integers. The below binomial identity is provable by other means:
$$\sum\_{j=0}^m(-1)^j\binom{n+1}j2^{m-j}
=\sum\_{j=0}^m(-1)^j\binom{n-m+j}j.$$



> 
> **QUESTION.** Can you provide a combinatorial proof for the above identity? I would be thrilled to see as many as possible.
> 
> 
> 


**POSTSCRIPT.** I enjoyed the two solutions by Ira & Fedor. Still, more alternating proofs are welcome.



Seeking a combinatorial proof for a binomial identity
I think I can, if you permit me to multiply it by $2^{n+1-m}$. Then we want to prove $$P:=\sum\_{j=0}^m(-1)^j\binom{n+1}j2^{n+1-j}
=2^{n+1-m}\sum\_{j=0}^m(-1)^j\binom{n-m+j}j=:Q.$$
Denote $X=\{1,2,\ldots,n+1\}$, then
$$
P=\sum\_{B\subset A\subset X,|B|\leqslant m} (-1)^{|B|}.
$$
Fix $A$, denote $a=\max(A)$, and partition possible $B$'s onto pairs of the form $\{C,C\sqcup a\}$, where $C\subset A\setminus \{a\}$. All $B$'s are partitioned onto pairs except those for which $|B|=m$ and $a\notin B$. The sum in each pair 0, therefore
$$
P=1+(-1)^m|B\subset A\subset X,|B|=m,\max(A)\notin B|.
$$
Extra 1 comes from the case $B=A=\emptyset$, for which $\max(A)$ does not exist.


Now about $Q$. Consider $B\subset X$, $|B|=m$, and denote by $m-j+1$ the minimal element of $\overline{B}:=X\setminus B$. For fixed $j$, there exist exactly ${n-m+j\choose j}$ such sets $B$. Each of them has $2^{n+1-m}$ oversets $A$. Therefore
$$
Q=\sum\_{B\subset A\subset X,|B|=m} (-1)^{\min(\overline{B})+m+1}.
$$
Consider the "dominos" $\{1,2\}$, $\{3,4\}$, $\ldots$, and take the first domino which is not contained in $B$. If it contains exactly 1 element from $B$, we may switch this element to the other element of the same domino, and $\min(\overline{B})$ changes its parity. This cancellation in the sum for $Q$ lefts only those $B$'s for which FNFDE (the first not-full domino is empty). Therefore
$$
Q=(-1)^m|B\subset A\subset X,|B|=m,FNFDE|.
$$
So $P=Q$ reduces to
$$
(-1)^m+|B\subset A\subset X,|B|=m,\max(A)\notin B|=|B\subset A\subset X,|B|=m,FNFDE|.
$$
Subtracting the common part, we should prove that
$$
(-1)^m+|B\subset A\subset X,|B|=m,\max(A)\notin B,\,\text{not}\, FNFDE|=\\
|B\subset A\subset X,|B|=m,\max(A)\in B,FNFDE|.
$$
Fix the first not full domino $\{s,s+1\}$ and $a=\max(A)$. If $a\leqslant s+1$, there is unique possibility which gives $(-1)^m$. Otherwise, if we fix also $B\_0:=B\setminus \{s,s+1,a\}$ (it is some set of size $m-1$), and $A\_0:=A\setminus \{s,s+1\}$ such that $B\_0\subset A\_0$, there exist exactly 4 ways to complete the choice of the pair $(B\_0,A\_0)$ to $(B,A)$ both for the condition $\{\max(A)\notin B,\,\text{not}\, FNFDE\}$ (choose which of $\{s,s+1\}$ belongs to $B$ where another guy from the domino belongs to $A$); and for the condition $\{\max(A)\in B,FNFDE\}$ (choose which of $s,s+1$ belongs to $a$). This proves the result.


