Alternating sign Vandermonde convolution like quantity

Question

I am interested in proving that the numbers $A_{n,m}$ are non-negative:

$$A_{n,m}:= \sum_{n_1=0}^{2n-1} \sum_{m_1=0}^{2m-1} (-1)^{m_1+n_1} \binom{2n-1-n_1}{2m-1-m_1} \binom{n_1}{m_1}$$

where $m,n$ are integers with $1\leq m \leq n$.

I have calculated the first few and this seems to be the case. I can also write closed formulas for $A_{n,n}, A_{n,1}$, but I am not sure what to do for the general quantity.

Does anyone have any insight on this?

Thanks!

Edit: my question is if $A_{n,m} \geq 0$ for all integers $1\leq m \leq n$. (I can only show this is true for m=1 and m=n)

Answer 1

Let us be a little more general. Define $$ B_{n,m}=\sum_{n_1=0}^{n-1}\sum_{m_1=0}^{m-1}\binom{n_1}{m_1}\binom{n-n_1-1}{m-m_1-1} $$ Note that $A_{n,m}=B_{2n,2m}$, so your function is a specialization of mine. I will prove that $$ B_{n,m}=\begin{cases} \displaystyle\binom{n}{m-1} & \text{if $n-m$ is even}, \\ 0 & \text{if $n-m$ is odd}. \end{cases} $$ In particular, $B_{n,m}\ge 0$ always.

---

Consider lattice paths from $(0,0)$ to $(m,n-m)$, where each step is one unit up or one unit to the right. The number of such paths is $\binom{n}{m}$. More specifically, how many lattice paths contain the horizontal edge joining $(m_1,n_1-m_1)$ to $(m_1,n_1-m_1+1)$? There are $\binom{n_1}{m_1}$ ways to choose a path from $(0,0)$ to $(m_1,n_1-m_1)$, and then there are $\binom{n-n_1-1}{m-m_1-1}$ ways to choose a path froM $(m_1,n_1-m_1+1)$ to $(m,n-m)$. Therefore, there are $$ \binom{n_1}{m_1}\binom{n-n_1-1}{m-m_1-1} $$ paths which include the horizontal edge $(m_1,n_1-m_1)\to (m_1,n_1-m_1+1)$. This suggests that these lattice paths are useful to computing $B_{n,m}$.

Let $S$ be the set of lattice paths from $(0,0)$ to $(m,n-m)$ where one of the horizontal edges is marked. This means that $|S|=\binom{n}{m}\times m$, because there are $\binom{m}{n}$ paths, and there are $m$ ways to choose a horizontal edge to mark. Then, call a path "even" if the marked edge has an even $y$-coordinate, and call a path "odd" if the $y$-coordinate of the marked edge is odd. Your summation is precisely equal to the number of even marked paths in $S$, minus the number of odd marked paths. This is because there are $\binom{n_1}{m_1}\binom{n-n_1-1}{m-m_1-1}$ paths where the marked edge is at $(m_1,n_1-m_1)$, and these come with a sign of $(-1)^{m_1+n_1}=(-1)^{n_1-m_1}$.

We will define a sign-reversing involution on the set of marked paths; every odd marked path will be paired with a distinct even marked path, while some even paths will remain unpaired. These pairs of odd and even paths cancel each other out, so the value of the summation equals the number of unpaired paths.

Given an odd path, here is how to find the even path it is paired with. Start at the marked horizontal edge, and backtrack until you find the first vertical edge. We will replace the portion of the path between this vertical edge and the marked edge, as shown below, where the marked edge is red. That is, instead of doing a vertical step, then several horizontal steps, and then a marked horizontal step, you do a marked horizontal step, then several horizontal steps, and then a vertical step.

$$ \uparrow\,\to\,\to\,\to\,\to\,\color{red}\to \qquad\text{becomes}\qquad \color{red}\to\,\to\,\to\,\to\,\to\,\uparrow $$ Similarly, given an even path, we do the above procedure in reverse. You instead march forward until you find the first vertical edge, then reverse the portion of the path between the marked edge and that vertical edge. These two procedures are inverses of each other, so this is a partial involution.

The only way to have an unpaired even path is when the marked edge is at the very top, so you cannot march forward to find another vertical edge. This can only occur when the height of the grid, $n-m$, is even. Therefore, the summation is zero when $n-m$ is odd, while the summation equals to the number of paths where one of the top edges is marked when $n-m$ is even.

There is a simple combinatorial argument which proves there are $\binom{n}{m-1}$ paths where the marked edge is on top. Namely, given a marked path from $(0,0)$ to $(m,n-m)$, replace the marked edge with a vertical edge. The result is an arbitrary path from $(0,0)$ to $(m-1,n-m+1)$, of which there are $\binom{n}{m-1}$. Conversely, given a path from $(0,0)$ to $(m-1,n-m+1)$, replacing the topmost vertical step with a marked horizontal step establishes the inverse mapping.

Answer 2

Counting lattice paths as in Mike's answer amounts to proving convolution formulas on binomial coefficients. You might want to apply them directly:

1. Gathering the terms according to $\ell:=n_1-m_1\in\{0,\ldots,2n-2m\}$: \begin{align} A_{n,m}&= \sum_{\substack{0\le n_1\le 2n-1\\0\le m_1\le 2m-1\\0\le n_1-m_1\le 2n-2m}}(-1)^{m_1+n_1} \binom{2n-1-n_1}{2m-1-m_1}\binom{n_1}{m_1}\\[.4em] &=\sum_{\ell=0}^{2n-2m}\:\sum_{m_1=0}^{2m-1}(-1)^{\ell+2m_1}\binom{2n-1-\ell-m_1}{2m-1-m_1}\binom{\ell+m_1}{m_1}\\[.4em] &=\sum_{\ell=0}^{2n-2m}(-1)^\ell\sum_{m_1=0}^{2m-1}\binom{2n-1-\ell-m_1}{2m-1-m_1}\binom{\ell+m_1}{m_1}. \end{align}
2. One checks that $$\sum_{m_1=0}^{2m-1}\binom{2n-1-\ell-m_1}{2m-1-m_1}\binom{\ell+m_1}{m_1}=\binom{2n}{2m-1}$$ by applying the Rothe-Hagen identity with $x=\ell+1$, $y=2n-2m+1-\ell$, $z=1$ (and with $2m-1$ in place of $n$).
3. Therefore $$A_{n,m}=\sum_{\ell=0}^{2n-2m}(-1)^\ell\binom{2n}{2m-1}=\binom{2n}{2m-1}\sum_{\ell=0}^{2n-2m}(-1)^\ell=\binom{2n}{2m-1}.$$

Answer 3

We will show that with $1\le m\le n$

$$\sum_{n_1=0}^{2n-1} \sum_{m_1=0}^{2m-1} (-1)^{n_1+m_1} {2n-1-n_1\choose 2m-1-m_1} {n_1\choose m_1} = {2n\choose 2m-1}.$$

We get for the LHS

$$[z^{2m-1}] (1+z)^{2n-1} \sum_{n_1=0}^{2n-1} (-1)^{n_1} (1+z)^{-n_1} \sum_{m_1\ge 0} (-1)^{m_1} z^{m_1} {n_1\choose m_1}.$$

Here we have extended to infinity due to the coefficient extractor. Continuing,

$$[z^{2m-1}] (1+z)^{2n-1} \sum_{n_1=0}^{2n-1} (-1)^{n_1} (1+z)^{-n_1} (1-z)^{n_1} \\ = [z^{2m-1}] (1+z)^{2n-1} \frac{1-(-1)^{2n} (1-z)^{2n} (1+z)^{-2n}} {1+(1-z)/(1+z)} \\ = \frac{1}{2} [z^{2m-1}] (1+z)^{2n} (1- (1-z)^{2n} (1+z)^{-2n}) \\ = \frac{1}{2} {2n\choose 2m-1} - \frac{1}{2} {2n\choose 2m-1} (-1)^{2m-1} = {2n\choose 2m-1}.$$

This is the claim.