Seeking a combinatorial proof for a binomial identity

Here are some observations, though not quite a combinatorial proof of the identity in question.

Let $A(m,n)$ be the value of the sums. Let $B(m,n)=(-1)^m A(m, m+n)$. Then $B(m,n)$ is nonnegative for all $m$ and $n$ (and is zero only if $m$ is odd and $n=0$).

It's not too hard to give a combinatorial interpretation to $B(m,n)$. It's easy to show that $B(m,n)$ has the simple generating function $$ \beta(x,y) = \sum_{m,n=0}^\infty B(m,n) x^m y^n = \frac{1}{(1+x)(1-x-y)}. $$ It follows that $B(m,n)$ satisfies the Pascal-like recurrence $$B(m,n)=B(m-1, n) + B(m,n-1)$$ for $m\ge0$ and $n>0$ with initial values $B(-1,n)=0$, $B(m,0)=1$ for $m$ even and $B(m,0)=0$ for $m$ odd. We can see that $B(m,n)$ is nonnegative by writing the generating function as $$ \beta(x,y)=\frac{1-x}{(1-x^2)(1-x-y)}=\frac{1}{1-x^2}\left(1+\frac{y}{1-x-y}\right), $$ or more simply, $$\sum_{m=0}^\infty \sum_{n=1}^\infty B(m,n) x^m y^n = \frac{y}{(1-x^2)(1-x-y)},$$ which gives the simpler formula $$B(m,n) = \sum_{0\le i\le m/2} \binom{m+n-2i-1}{n-1}$$ for $n>0$. From these generating functions we see that that $B(m,n)$ is the number of lattice paths from $(0,0)$ to $(m,n)$, with unit east and north steps, that start with an even number of east steps.

The OP's second sum gives $$ B(m,n) = \sum_{j=0}^m (-1)^{m-j}\binom{n+j}{j}=\sum_{j=0}^m (-1)^j \binom{n+m-j}{m-j}. $$ This comes from expanding $\beta(x,y)$ as $$\frac{1-x+x^2-x^3+\cdots}{1-x-y}$$ and is easy to interpret combinatorially: $\binom{n+m-j}{m-j}$ is the number of paths from $(j,0)$ to $(m,n)$, or equivalently the number of paths from $(0,0)$ to $(m,n)$ that start with $j$ east steps (possibly followed by more east steps), or in other words, the number of paths from $(0,0)$ to $(m,n)$ that pass through $(j,0)$. Then for $j$ even, $\binom{n+m-j}{m-j}-\binom{n+m-j-1}{m-j-1}$ counts paths from $(0,0)$ to $(m,n)$ that start with $j$ east steps followed by a north step. Add this over all even $j\le m$ gives all the paths counted by $B(m,n)$.

The identity in question (with $n$ replaced $m+n$ and the order of the summations reversed) may be written as $$ \sum_{i=0}^m (-2)^i\binom{m+n+1}{m-i} =\sum_{j=0}^m (-1)^j \binom{m+n-j}{m-j}. $$ This is the case $t=-2$ of the identity $$ \sum_{i=0}^m t^i\binom{m+n+1}{m-i}= \sum_{j=0}^m (1+t)^j\binom{m+n-j}{m-j}. \tag{1} $$ We can give a combinatorial interpretation of $(1)$, but I don't see that setting $t=-2$ has a simple combinatorial interpretation (though what I described above is a combinatorial interpretation of setting $t=-2$ in the right side). The combinatorial interpretation of $(1)$ is made clearer by looking at the generating function for $(1)$, which is $$\frac{1}{(1-(1+t)x)(1-x-y)}.$$ The right side of $(1)$ is obtained by expanding this in the most straightforward way; the left side is obtained by expanding it as $$ \frac{1}{(1-x)^2} \frac{1}{1-tx/(1-x)}\frac{1}{1-y/(1-x)}= \sum_{i,n}\frac{(tx)^i y^n}{(1-x)^{i+n+2}}. $$

To interpret the right side of $(1)$, we consider paths from $(0,0)$ to $(m,n)$, which are “cut” at some point $(j,0)$ on the $x$-axis (so they must start with at least $j$ east steps) and some subset of the first $j$ (east) steps are “marked” and weighted by $t$. It is clear that the contributions from the paths cut at $(j,0)$ is $(1+t)^j\binom{m+n-j}{m-j}$: each of the first $j$ (east) steps contributes 1 or $t$, and $\binom{m+n-j}{m-j}$ counts paths from $(j,0)$ to $(m,n)$. For the left side, given such a cut and marked path, with $i$ marked east steps, we change each marked east step to a north step and insert an additional north step after the $j$th step, obtaining a path with $m-i$ east steps and $n+i+1$ north steps, and these are counted by $\binom{m+n+1}{m-i}$. It is easy to see that this transformation is bijective—to go back we change the first $i$ north steps to marked east steps, set $j$ to the number of steps before the $(i+1)$st north step, and delete the $(i+1)$st north step.

It may be noted that $(1)$ is a special case of a $_2F_1$ linear transformation; a generalization can be obtained easily be expanding $$\frac{1}{(1-(1+t)x)^a (1-x-y)^b}$$ in the same two ways.

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.