(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!
Best Answer
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
\begin{equation} \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} \end{equation}
Then reindex the internal summation, and repeatedly apply the hockey stick identity to show \begin{equation} \sum_{j=0}^{i-k}\binom{n-1-k-j}{i-k-j}2^j = \sum_{j=0}^{i-k}\binom{n-k}{j} \end{equation}
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
\begin{equation} Q(n,i) = \sum_{j=0}^{i-1} \sum_{k=1}^{i-j} (-1)^k \binom{n}{k-1} \binom{n-k}{j} \end{equation}
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)$.
\begin{equation} P(n,i) = \sum_{j=0}^{i} (-1)^{i-j}\binom{n}{j} \binom{n-1-j}{i-j} \end{equation} 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:
\begin{equation} \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} \end{equation} 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
\begin{equation} \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} \end{equation} Dividing out the factor of $2^{i-1}$ and switching the order of summation, we get
\begin{equation} \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} \end{equation} Of course we recognize our hockey stick identity from earlier, so this simplifies to the case of $(A2)$
\begin{equation} \sum_{k=0}^{i-2} (-1)^k \binom{n+1}{k} \sum_{j=0}^{i-2-k} \binom{n-k}{j} =1 \end{equation}