I would like to prove the following identity:
$$\sum_{m\geq 0} (-1)^{i-m}{m+k \choose m} {i-1 \choose m-1}{m+k+1 \choose j} = \sum_{m\geq 0} {m+k \choose k}{k+1 \choose i-m}{k+1 \choose j-m}$$
for fixed $i,j \geq 1$, $k\geq 0$. If it helps, I have a combinatorial interpretation of the RHS: it counts the number of arrangements of $i$ $a$'s, $j$ $b$'s, and $k$ $c$'s so that the substrings "aa", "bb" cannot occur (there is no restriction on the c's.) This I can show, although I have not found a direct combinatorial proof. If it's helpful I can give my proof for the right-hand side; I derived it from the so-called Carlitz-Scoville-Vaughan theorem which I found out about recently on Math Overflow.
It is related to this question; I have a proof for it, contingent on proving this binomial identity. I "stumbled" across this through some very optimistic guessing, but I'm not sure how to prove it. I thought of using WZ theory, but as far as I know that only applies to identities with one parameter, not more general ones - but I'd be very happy if an algorithmic verification was possible.
Other possibilities: Interpret the left-hand side as an inclusion-exclusion argument, or a determinantal formula. Or, find a recurrence that both sides satisfy.