A (Human!) Proof of A Conjectured Triple Sum Identity Made By Juan Sebastián Pereyra

Doron ZEILBERGER^{1}

In [P] the following conjecture was made

∑_{i=1}^{n} [i^{2} ∑_{k=0}^{m} (\binom{i − 1}{m − k}\binom{n − i}{k})^{2}] +

2 ∑_{j=1}^{m} [∑_{i=1}^{n−j} i(i + j) (∑_{k=j}^{m} \binom{i + j − 1}{k}\binom{n − (i + j)}{m − k}\binom{n − i}{m − k + j}\binom{i − 1}{k − j})]

is equal to

\binom{n + 1}{m}^{2} ( ∑_{i=1}^{n−m} i^{2}) .

Of course the right side is \binom{n+1}{m}^{2}(n−m)(n−m+1)(2n−2m+1)/6 (using ∑_{i=1}^{n} i^{2} = n(n+1)(2n+ 1)/6), and the left side can be written more symmetrically as

∑_{i,j,k} i(i + j)\binom{i + j − 1}{k}\binom{n − (i + j)}{m − k}\binom{n − i}{m − k + j}\binom{i − 1}{k − j} ,

where the summation range is over all triples (i, j, k) for which the binomial coefficients “make sense” i.e. whenever you have \binom{r}{s} we have 0 ≤ s ≤ r).

Writing a = i + j, (and leaving i as a discrete variable, but letting j = a − i), it is more convenient to evaluate

∑_{a,k,i} ia\binom{a − 1}{k}\binom{n − a}{m − k}\binom{n − i}{m − k + a − i}\binom{i − 1}{k − a + i} .

It is easily seen that this equals the iterated summation

∑_{a=1}^{n} ∑_{k=max(0,a−(n−m))}^{min(a−1,m)} ∑_{i=a−k}^{a−k+m} ia\binom{a − 1}{k}\binom{n − a}{m − k}\binom{n − i}{m − k + a − i}\binom{i − 1}{k − a + i}

= ∑_{a=1}^{n} a ∑_{k=max(0,a−(n−m))}^{min(a−1,m)} \binom{a − 1}{k}\binom{n − a}{m − k} ∑_{i=a−k}^{a−k+m} i\binom{n − i}{m − k + a − i}\binom{i − 1}{k − a + i} .

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg/ . March 5, 2013. Exclusively publised in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger.

http://www.math.rutgers.edu/~zeilberg/pj.html . Supported in part by the NSF.

Let’s do the innermost sum first. Since i\binom{i−1}{k−a+i} = (a − k)\binom{i}{a−k} the inner sum is

(a − k) ∑_{i=a−k}^{a−k+m} \binom{n − i}{m − k + a − i}\binom{i}{a − k} = (a − k)\binom{n + 1}{m} ,

by the celebrated Vandermonde-Chu (alias terminating Gauss’s _{2}F_{1}(1) identity).

Now let’s do the middle sum

\binom{n + 1}{m} ∑_{k=max(0,a−(n−m))}^{min(a−1,m)}(a − k)\binom{a − 1}{k}\binom{n − a}{m − k} .

Now

∑_{k=max(0,a−(n−m))}^{min(a−1,m)}(a − k)\binom{a − 1}{k}\binom{n − a}{m − k}

= a ∑_{k=max(0,a−(n−m))}^{min(a−1,m)} \binom{a − 1}{k}\binom{n − a}{m − k} − ∑_{k=max(0,a−(n−m))}^{min(a−1,m)} k\binom{a − 1}{k}\binom{n − a}{m − k} .

The first sum is a\binom{n−1}{m}, again by Vandermonde, while for the second we replace

k\binom{a − 1}{k}

by

(a − 1)\binom{a − 2}{k − 1}

getting that it equals

(a − 1) ∑_{k=max(0,a−(n−m))}^{min(a−1,m)} \binom{a − 2}{k − 1}\binom{n − a}{m − k} ,

that again by Vandermonde, equals (a−1)\binom{n−2}{m−1}. So the inner and the middle ∑’s give the following expression in m, n, a:

\binom{n + 1}{m} (a\binom{n − 1}{m} − (a − 1)\binom{n − 2}{m − 1}) .

Finally to do the outermost sum, w.r.t. to a (don’t forget the a in front that we took out since it didn’t depend on i and k)

\binom{n + 1}{m} (\binom{n − 1}{m} (∑_{a=1}^{n} a^{2}) − \binom{n − 2}{m − 1} (∑_{a=1}^{n} a(a − 1)))

= \binom{n + 1}{m} (\frac{(n − 1)!}{m!(n − m − 1)!} · \frac{n(n + 1)(2n + 1)}{6} − \frac{(n − 2)!}{(m − 1)!(n − m − 1)!} · \frac{(n − 1)n(n + 1)}{3})

= \binom{n + 1}{m} · (\frac{(n + 1)!}{m!(n − m − 1)!} · \frac{(2n + 1)}{6} − \frac{(n + 1)!}{m!(n − m − 1)!} · \frac{m}{3})

= \binom{n + 1}{m}\frac{(n + 1)!}{m!(n − m − 1)!} · (\frac{2n + 1}{6} − \frac{m}{3})

= \binom{n + 1}{m}\frac{(n + 1)!}{m!(n − m − 1)!} · \frac{2n − 2m + 1}{6}

= \binom{n + 1}{m} · \frac{(n + 1)!}{m!(n − m + 1)!} · \frac{(n − m)(n − m + 1)(2n − 2m + 1)}{6}

= \binom{n + 1}{m}^{2} \frac{(n − m)(n − m + 1)(2n − 2m + 1)}{6} .

References

[P] Juan Sebastián Pereyra, private communication,

http://www.math.rutgers.edu/~zeilberg/akherim/pereyraConj.pdf