While working on a problem, I needed to prove the following identity:

For all $i,j,m,n \geqslant 0$, \begin{align*} \sum_{k+\ell=m} k! \ell! \binom{n+k-1}{k} \binom{j-i}{k} \binom{n-j+m-1}{\ell} \binom{i}{\ell} = m! \binom{n-i+m-1}{m}\binom{j}{m}. \end{align*}

Computational evidence indicates that this is true, but I haven't been able to prove it. It looks a little like Vandermonde's identity, but I haven't been able to massage it into a form where I can just apply that. Is there a clever way to prove this identity?

  • $\begingroup$ This has hints of Vandermonde (choosing $m$ things can be done by all ways to choose $k$ then $l$ things), and also some stars-and-bars looking terms. Could you tell us where this comes from? Perhaps given the problem setting one might be more inspired to find a combinatorial proof (as opposed to proof by tedious algebraic manipulation). $\endgroup$ – antkam Mar 6 '19 at 16:34
  • 1
    $\begingroup$ I'm working with the so-called Jordan plane, the quotient of the free algebra $k\langle x,y \rangle$ by the relation $yx = xy+y^2$. I wanted to write down the commutator of two monomials (depending on $n$, $i$ and $j$) and the need to prove this identity popped out. $\endgroup$ – lokodiz Mar 6 '19 at 16:50
  • $\begingroup$ Haha, I have no idea what you just said, so I guess that didn't help (at least, not me). Thanks anyway... :) $\endgroup$ – antkam Mar 6 '19 at 18:33

Let \begin{align} F(m,k) &=k! (m-k)! \binom{n+k-1}{k} \binom{j-i}{k} \binom{n-j+m-1}{m-k} \binom{i}{m-k} \\\\ &=\frac{(n+k-1)!}{(n-1)!}\binom{j-i}{k}\frac{(n-j+m-1)!}{(n-j+k-1)!}\binom{i}{m-k} \end{align} denote the summand. Let $$ S_m=\sum_{k=0}^m F(m,k) $$ be the sum to be computed.

Define $G(m,k)$ as follows. The motivation for this definition is as of yet unclear$^{**}$: \begin{align} G(m,k) &=F(m,k)\cdot \frac{k\,\left(m-k-i\right)\,\left(n+k-j-1\right)} {m-k+1} \\\\ &=\frac{(n+k-1)!}{(n-1)!}\binom{j-i}{k}\frac{(n-j+m-1)!}{(n-j+k-1)!}\color{red}{\binom{i+1}{m-k+1}}\frac{k\,\left(m-k-i\right)\,\left(n+k-j-1\right)} {\color{red}{i+1}} \end{align} Note that the first expression for $G(m,k)$ is undefined when $k=m+1$, as it contains $\frac00$. However, it can be rearranged to the second expression, where $G(m,k)$ is unambiguously defined for all $k$. Note that $G(m,k)=0$ for all $k$ outside $[1,m+1]$.

You can verify via tedious algebraic manipulations$^*$ that $$ (m+1)F(m+1,k)-(j-m)(n+m-i)F(m,k)=G(m,k+1)-G(m,k)\label1\tag1 $$ holds for all nonnegative integer inputs.

Now, sum both sides of the above equation from $k=0$ to $m+1$. The right had side is a telescoping sum. We attain $$ (m+1)S_{m+1}-(j-m)(n+m-i)S_m=G(m,m+2)-G(m,0)=0-0, $$
or $$ S_{m+1}=\frac{(j-m)(n+m-i)}{m+1}S_m $$ This easily lets you prove that $S_m=m!\binom{n-i+m-1}{m}\binom{j}m$ by induction.

$^*$ The calculations really are tedious, but certainly feasible for even a high schooler to do. Start by dividing $\eqref1$ though by $F(m,k)$, then replace all of the binomial coefficients with factorials. Every factorial term in the numerator will have a counterpart which cancels nicely with one in the denominator. For example, in $F(m+1,k)/F(m,k)$, there will appear $$\binom{i}{m+1-k}\Big/\binom{i}{m-k}=\frac{i!}{(m+1-k)!(i-m-1+k)!}\Big/\frac{i!}{(m-k)!(i-m+k)!}=\frac{i-m+k}{m+1-k}$$ After making all these cancellations, you will be left with a sum of fractions of polynomials in $i,j,k,m,n$. After clearing denominators, this is a polynomial equation which can be verified by collecting all like coefficients.

But there is not reason not to just have Mathematica verify the equation for you automatically.

F[m_,k_] := k! * (m-k)! * 
            Binomial[n+k-1,k] * Binomial[j-i,k] * 
            Binomial[n-j+m-1,m-k] * Binomial[i,m-k];

G[m_,k_] := F[m,k] * k * (m - k - i) * (n + k - j - 1) / (m - k + 1);

    (m + 1)F[m + 1,k] - (j - m)(n + m - i)F[m,k] == G[m,k + 1] - G[m,k]

Try it online!

$^{**}$ The quotient $ \frac{k\,\left(m-k-i\right)\,\left(n+k-j-1\right)}{m-k+1}$ in the definition of $G$, and the coefficients $m+1$ and $i(j-m)(n+m-i)$ on the left hand side of $\eqref1$, are attained using Zeilberger's algorithm. Specifically, I used the programming language Maxima, this code snippet:

load (zeilberger)$

    k! * (m-k)! * 
    binomial(n+k-1,k) * binomial(j-i,k) * binomial(n-j+m-1,m-k) * binomial(i,m-k)

Try it online! (ignore the small differences in the linked code).

This algorithm, and others is discussed in the book A = B by Marko Petkovsek, Herbert Wilf and Doron Zeilberger, available for free online. Basically, the book shows must summations similar to yours can be solved completely automatically, and computer verifiable proofs of these equation can also be produced automatically.

  • $\begingroup$ This is a very helpful answer. I have a couple of small corrections (although I might be missing something). We need to define $G(m,m+1) = -(m+1) F(m+1,m+1)$, rather than $0$. This means that when we sum (1) for $k$ between $0$ and $m$ (rather than $-1$ and $m$) we obtain $(m+1) \sum_{k=0}^m F(m+1,k) - (j-m)(n+m-i) S_m = - G(m,m+1)$, which then rearranges as claimed. $\endgroup$ – lokodiz Apr 22 '19 at 18:44
  • $\begingroup$ @lokodiz I have (hopefully) fixed the mistake. I did so in a way more in line with the general theory. Note that it is okay to sum both sides from $0$ to $m+1$, because $F(m,m+1)=0$ anyway. $\endgroup$ – Mike Earnest Apr 22 '19 at 20:41

\begin{align*} \sum_{k+\ell=m} k! \ell! \binom{n+k-1}{k} \binom{j-i}{k} \binom{n-j+m-1}{\ell} \binom{i}{\ell} = m! \binom{n-i+m-1}{m}\binom{j}{m}. \end{align*} Okay, first thing I'd do, is expand the sum termwise a bit to cancel things to be: \begin{align*} \sum_{k+\ell=m} \frac{(n+k-1)!i!}{(n-1)!(i-\ell)!} \binom{j-i}{k} \binom{n-j+m-1}{\ell} = m! \binom{n-i+m-1}{m}\binom{j}{m}. \end{align*} Scanning a bit more, we see the possibility to get rid of $m!$ on the right hand side: \begin{align*} \sum_{k+\ell=m} \frac{(n+k-1)!i!}{(n-1)!(i-\ell)!} \binom{j-i}{k} \binom{n-j+m-1}{\ell} = \frac{(n-i+m-1)!}{(n-i-1)!}\binom{j}{m}. \end{align*} Using the fact (finally...) that $k+\ell=m$, noting that means $m!$ has $\ell!$ and $k!$ as factors, remaining factor p,we get: \begin{align*} \sum_{k+\ell=m} \frac{p(n+k-1)!(i)!(j-i)!(n-j+m-1)!}{(n-1)!(i-\ell)!(j-i-k)!(n-j+k-1)!} = \frac{p(n-i+m-1)!(j)!}{(n-i-1)!(j-m)!}. \end{align*}

Looking a bit closer, we have $$\ell\leq i\leq j\leq n, m\leq n,k\leq j, k\leq n$$ As well as simplifying because factorials in denominators have a factor separating them, we can go down to: \begin{align*} \sum_{k+\ell=m} qsrt(n+k-1)!= uvp^2 \end{align*} Where p,q,r,s,t,u, and v are all quotients of factorials. So, you have the statement that, a factorial and a square of a quotient of factorials, can be related by another set of 6 not necessarily distinct quotients of factorials,

  • $\begingroup$ Yes I'll work it again to double check later. $\endgroup$ – user645636 Mar 6 '19 at 0:55
  • $\begingroup$ Unfortunately, this isn't particularly useful as it stands. I'd already been able to make the same "simplifications" you did, but the form of the claimed identity I gave seemed the cleanest. In any case, I don't have a proof that my claimed identity is true, and all of your manipulations hinge on its validity. $\endgroup$ – lokodiz Mar 6 '19 at 13:52
  • $\begingroup$ all my manipulations, hinge on the claimed nonnegative integer values, and factorial properties, actually. in a proof you can assume validity to prove consistency with the axioms used, if not you get a proof by contradiction. $\endgroup$ – user645636 Mar 6 '19 at 14:20

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.