# Is this similar to a known combinatorial identity?

(Apologies if this is too obscure.)

In joint work with Izzet Coskun we came across the following kind of combinatorial identity, but we weren't able to prove it, or to identify what kind of identity it is. (We looked in some references, but to the outsider it can be difficult to distinguish one insanely complicated sum of binomial coeffficients from another...)

The identity looks like the following. Say $n$ is a fixed natural number, and $i \leq n$ is an even natural number. (There is an analogous formula when $i$ is odd.) Then

\begin{align} \sum_{m=2}^{\frac{i}{2}} (x-1) \left(x-2\right)^{2m-3} \ \sum_{j=0}^{i-2m} \binom{n-1-j}{i-2m-j} 2^{j+2} \sum_{l=0}^j (-1)^l \binom{n+1}{l} \, x^{i-2m-l} & \\\\ + \sum_{j=0}^{i-2} \binom{n-1-j}{i-2-j} 2^{j+1} \sum_{l=0}^j (-1)^l \binom{n+1}{l} \, x^{i-2-l} &\\\\ + \sum_{j=0}^{i-2} \binom{n-1-j}{i-2-j} 2^{j-1} \sum_{l=0}^j (-1)^l \binom{n+1}{l} (i-2-l) \, x^{i-l-1} & \\\\ - \sum_{j=0}^{i} \binom{n-1-j}{i-j} 2^{j-1} \sum_{l=0}^j (-1)^l \binom{n+1}{l} (i-l) \, x^{i-l-1} & \\\\ \qquad =C_i \left(x-2 \right)^{i-1} \end{align}

where $C_i$ is some constant that can be read off fairly easily by looking at the coefficient of $x^{i-1}$ on the left-hand side. (There are various rewritings one could do to the left-hand side, but it's not clear how much this helps.)

Given that there are various irregularities in the last three terms on the left-hand side, it seems unlikely that the whole thing can be reduced to a simple form. But it would nevertheless be very useful to know if this looks similar to any known combinatorial identities.

Maybe a simpler warmup question would be: how to see that the sum of the last three terms on the left-hand side is divisible by $x-2$? That might help get going with an inductive argument.

Any ideas would be much appreciated!

-
Is the upper index $i$ and the binomial choosing $i-j$ in the last term on the left correct? It seems that taking $x=2$, the second term cancels with the $-2$ part of the $(i-2-l)$ part of the third term, and leaves something remarkably close to the final term, but not equal to it. –  Zack Wolske Jun 4 '13 at 22:41
For example, if I haven't made any mistakes, then taking $n=i$ makes all the binomial coefficients of the final term on the left $0$, and taking $i=2$ makes the first summation empty and leaves the others with just one term each, $2x^{i−2}$ and $(i-2)x^{i−1}/2$. So when $n=i=x=2$, the left side is $2$. If the upper index and binomial coefficient in the final term are changed to be in line with the other terms, then everything cancels, and $(x−2)$ divides the left side. –  Zack Wolske Jun 4 '13 at 23:00
Doesn't the Wilf-Zeilberger technique work for this ? See math.rutgers.edu/~zeilberg/programsAB.html for Maple the packages, and math.upenn.edu/~wilf/AeqB.html for the book. –  David Lehavi Jun 5 '13 at 1:23
Dear Zack: I think the discrepancy in our answers comes from what the binomial coefficient (-1 choose 0) means; sorry if I was being a bit sloppy here. Anyway, for my purposes I want to define this to be 1, even if that is nonstandard. I think with that convention, the formula I wrote really does work out. (I checked it by computer for enough cases to satisfy myself, although others might be more exacting.) Anyway, thanks for your input! –  Artie Prendergast-Smith Jun 5 '13 at 20:46
Dear David: I'm not so familiar with the Wilf--Zeilberger machinery, but it does seem applicable here. For the record, the Mathematica package gosper.m available from the site you link is capable of simplifying parts of these expressions, but so far it does not see capable of digesting the whole thing... –  Artie Prendergast-Smith Jun 5 '13 at 20:48

Here is a solution to your warm up problem. It uses a few known elementary identities, and some short inductions for identities I didn't recognize. I also changed your notation slightly from $l$ to $k$ in the internal summations.

Setting $x=2$, the first term vanishes, and we combine the second and third terms as $(B)$ and take the last term as $(A)$.

\begin{align} &\sum_{j=0}^i \binom{n-1-j}{i-j} 2^{j-1} \sum_{k=0}^j (-1)^k \binom{n+1}{k} 2^{i-k-1}(i-k) \tag{A} \\ &\sum_{j=0}^{i-2} \binom{n-1-j}{i-2-j} 2^{j-1} \sum_{k=0}^j (-1)^k \binom{n+1}{k} \left( 2^{i-k} + 2^{i-k-1}(i-2-k)\right) \tag{B} \end{align} Fortunately for us, both are equal to $i\cdot2^{i-2}$ when $i$ is even, and do not depend on $n$. First, we focus on $(A)$. Switch the order of summation to get

$$\sum_{k=0}^i (-1)^k \binom{n+1}{k} 2^{i-2}(i-k) \sum_{j=k}^i \binom{n-1-j}{i-j} 2^{j-k} \tag{A}$$

Then reindex the internal summation, and repeatedly apply the hockey stick identity to show $$\sum_{j=0}^{i-k}\binom{n-1-k-j}{i-k-j}2^j = \sum_{j=0}^{i-k}\binom{n-k}{j}$$

I found it easier to write out by changing variables $a=i-k-j$, $b=i-k$ and $c=n-i-1$, then simplifying $\sum_{a=0}^b \binom{c+a}{c}2^{b-a}$.

$(A)$ naturally splits at the point $i-k$, and since we want to show that the whole thing is $i\cdot2^{i-2}$, we can break it into two pieces and show

\begin{align} \sum_{k=1}^i (-1)^k k\binom{n+1}{k}\sum_{j=0}^{i-k} \binom{n-k}{j} &=0 \tag{A1}\\ \sum_{k=0}^i (-1)^k \binom{n+1}{k} \sum_{j=0}^{i-k} \binom{n-k}{j} &=1 \tag{A2} \end{align}

We can simplify $(A1)$ slightly by incorporating $k$ into the binomial, and ignoring the $n+1$ term that comes out. Switching the order of summations again, we write

$$Q(n,i) = \sum_{j=0}^{i-1} \sum_{k=1}^{i-j} (-1)^k \binom{n}{k-1} \binom{n-k}{j}$$

We will induct on $n$ and $i$ to show that $Q(n,i)=0$ for $i$ even, and $-1$ for $i$ odd. The base cases are easy to check, especially if taking $i=0$ and $i=1$. But first, we need an auxillary identity, which we will also use in $(A2)$.

$$P(n,i) = \sum_{j=0}^{i} (-1)^{i-j}\binom{n}{j} \binom{n-1-j}{i-j}$$ We claim that $P(n,i)=1$ for all $n$ and $i$. This is certainly true for $i=0$. We split $\binom{n}{j}$ into two to get an induction:

\begin{align} P(n,i) &= \sum_{j=0}^{i} (-1)^{i-j}\binom{n-1}{j} \binom{n-1-j}{i-j} + \sum_{j=1}^{i} (-1)^{i-j}\binom{n-1}{j-1} \binom{n-1-j}{i-j} \\ &= \sum_{j=0}^{i} (-1)^{i-j}\binom{n-1}{i} \binom{i}{j} + \sum_{j=1}^{i} (-1)^{i-j}\binom{n-1}{j-1} \binom{n-1-j}{i-j} \\ &= \binom{n-1}{i}\sum_{j=0}^{i} (-1)^{i-j}\binom{i}{j} + \sum_{j=0}^{i-1} (-1)^{i-1-j}\binom{n-1}{j} \binom{(n-1)-1-j}{(i-1)-j} \\ &= 0 + P(n-1,i-1) \end{align}

Now we give a similar proof for $Q$. In the fourth to fifth lines, we used the alternating sum of binomial coefficients up to some number. You might be able to give a direct proof if your generatingfunctionology is strong, since these look like convolutions of simple functions, but these proofs seemed easy enough that I didn't bother trying.

\begin{align} Q(n,i) &= \sum_{j=0}^{i-1} \sum_{k=1}^{i-j} (-1)^k \binom{n}{k-1} \binom{n-k}{j} \\ &= \sum_{j=0}^{i-1} \sum_{k=1}^{i-j} (-1)^k \binom{n-1}{k-1} \binom{n-k}{j} + \sum_{j=0}^{i-2} \sum_{k=2}^{i-j} (-1)^k \binom{n-1}{k-2} \binom{n-k}{j} \\ &= \sum_{j=0}^{i-1} \sum_{k=1}^{i-j} (-1)^k \binom{n-1}{j} \binom{n-1-j}{k-1} + \sum_{j=0}^{i-2} \sum_{k=2}^{i-j} (-1)^k \binom{n-1}{k-2} \binom{n-k}{j} \\ &= \sum_{j=0}^{i-1} \binom{n-1}{j} \sum_{k=0}^{i-1-j} (-1)^{k+1} \binom{n-1-j}{k} + \sum_{j=0}^{i-2} \sum_{k=1}^{i-1-j} (-1)^{k+1} \binom{n-1}{k-1} \binom{n-1-k}{j} \\ &= \sum_{j=0}^{i-1} \binom{n-1}{j} (-1)^{i-1-j+1} \binom{n-2-j}{i-1-j} - Q(n-1, i-1) \\ &= -P(n-1,i-1) - Q(n-1, i-1) \end{align}

Now, since our equation $(A1)$ was just $(n+1)Q(n,i)$, and $i$ is even, it's $0$. A similar treatment yields $(A2)$, again using the alternating binomial sum identity near the end:

\begin{align} &\,\sum_{k=0}^i (-1)^k \binom{n+1}{k} \sum_{j=0}^{i-k} \binom{n-k}{j} \\ &= \sum_{j=0}^i \sum_{k=0}^{i-j} (-1)^k \binom{n+1}{k} \binom{n-k}{j} \\ &= \sum_{j=0}^i \sum_{k=0}^{i-j} (-1)^k \binom{n}{k} \binom{n-k}{j} + \sum_{j=0}^i \sum_{k=0}^{i-j} (-1)^k \binom{n}{k-1} \binom{n-k}{j} \\ &= \sum_{j=0}^i \sum_{k=0}^{i-j} (-1)^k \binom{n}{j} \binom{n-j}{k} + Q(n,i) \\ &= \sum_{j=0}^i \binom{n}{j} \sum_{k=0}^{i-j} (-1)^k \binom{n-j}{k} \\ &= \sum_{j=0}^i \binom{n}{j} (-1)^{i-j} \binom{n-1-j}{i-j} \\ &= P(n,i) \end{align}

So we have shown that $(A) = i\cdot2^{i-2}$ for $i$ even. Let's use this for $(B)$, since $i-2$ is also even, we have:

$$\sum_{j=0}^{i-2} \binom{n-1-j}{i-2-j} 2^{j-1} \sum_{k=0}^j (-1)^k \binom{n+1}{k} 2^{i-k-3}(i-2-k) = (i-2)2^{i-4}$$ After multiplying both sides by $2^2$, the only place the left side differs from $(B)$ is the extra $-2$ in $(i-2-k)$, and the right side is $2^{i-1}$ smaller than we would like. So we show that

$$\sum_{j=0}^{i-2} \binom{n-1-j}{i-2-j} 2^{j-1} \sum_{k=0}^j (-1)^k \binom{n+1}{k} 2^{i-k} = 2^{i-1}$$ Dividing out the factor of $2^{i-1}$ and switching the order of summation, we get

$$\sum_{k=0}^{i-2} (-1)^k \binom{n+1}{k} \sum_{j=k}^{i-2} \binom{n-1-j}{i-2-j}2^{j-k}$$ Of course we recognize our hockey stick identity from earlier, so this simplifies to the case of $(A2)$

$$\sum_{k=0}^{i-2} (-1)^k \binom{n+1}{k} \sum_{j=0}^{i-2-k} \binom{n-k}{j} =1$$

-
"The hockey stick identity"? –  Gerry Myerson Jul 12 '13 at 2:41
I wondered if it was only known as that in Canada, but I looked it up and found some results, so I used it. $\sum_{j=0}^i \binom{n+j}{j} = \binom{n+i+1}{i}$, because the relevant terms in Pascal's triangle look like a hockey stick. –  Zack Wolske Jul 12 '13 at 3:32
Wow, thanks! As per D. Lehavi's suggestion I tried to use Wilf--Zeilberger-based computer programs to solve the problem; I failed, but an expert --- Christoph Koutschan --- was able to do this successfully. It's satisfying to see things worked out by hand, though! –  Artie Prendergast-Smith Jul 12 '13 at 14:20

It turns out that this identity is tractable using the Wilf-Zeilberger machinery, as suggested by David Lehavi in comments to the question. Christoph Koutschan was able to prove the identity using the Mathematica package $\mathtt{HolonomicFunctions}$ which he developed in his thesis: