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.

  • 1
    $\begingroup$ 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. $\endgroup$ – user44191 Jun 22 '20 at 23:45
  • 1
    $\begingroup$ These numbers are, up to sign, sequences A035317, A108561, A059259, A080242, A112555, A220074, and A279006 in the OEIS. $\endgroup$ – Ira Gessel Jun 23 '20 at 0:49
  • $\begingroup$ 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. $\endgroup$ – Mark Wildon Jun 25 '20 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.

  • $\begingroup$ Thank you for your generous analysis. $\endgroup$ – T. Amdeberhan Jun 29 '20 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.