# Seeking a combinatorial proof for a binomial identity

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.

• Is there an obvious combinatorial interpretation of the "completed" version of the equation (with $m = n + 1$)? The left-hand side should be $1$ in that case. – user44191 Jun 22 at 23:45
• These numbers are, up to sign, sequences A035317, A108561, A059259, A080242, A112555, A220074, and A279006 in the OEIS. – Ira Gessel Jun 23 at 0:49
• As a response to user44191's comment: When $m = n$ both sides are [$n$ is even] (Iverson notation.) Multiply by two and add the 'missing term' $(-1)^{m+1}$ to both sides. The left-hand side is then the inclusion-exclusion count of subsets of $\{1,\ldots,m,m+1\}$ not containing any of $1, \ldots, m+1$, and the right-hand side is $2\sum_{j=0}^{m} (-1)^j + (-1)^{m+1}$, so both sides are $1$. I admit even this special case proof is not entirely combinatorial. – Mark Wildon Jun 25 at 9:27

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.

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.

• Thank you for your generous analysis. – T. Amdeberhan Jun 29 at 16:14