Return to [Polya Home Page] [Members] [Problem Center] [Inventory] [Reserve Area]

POLY031  A combinatorial sum (proposed by Luis Lopes, 10/7/02).

Prove that   \sum_{k=0}^n  (3k - 2n) \binom{n}{k}^2 \binom{2k}{k} = 0.

[JPE] (11/22/02):  A classical method using telescopic sums gives the result (surely, there is something better)
u(n,k) = C(2k,k)C(n,k)^2
f(n,k) = (3k-2n)u(n,k).
g(n,k) = k^3/(n+1-k)^2 u(n,k)
s(n) = sum(f(n,k), k = 0..n)
We have f(n+1,k)-f(n,k) = g(n,k)-g(n,k+1) hence
s(n+1) - s(n) = f(n+1,n+1)+f(n+1,n)-f(n,n)-g(n,n) = 0
As s(1) = 0, we get s(n) = 0.

[JPE](11/24/02): I just realize that this identity is given as example and proved page 132 in  the remarkable book A = B by  Marko Petrovsek, Herbert S. Wilf, and  Doron Zeilberger. Many thanks to the authors, this book gives different algorithms of summation and a free PDF version is available at

[LL] (11/25/02): Thank you to JPE for this discussion. I do know the A=B book, a remarkable book indeed. We can say that the algorithms presented in A=B
close the matter regarding these sums as far as one is concerned with a "mechanical" approach. owever, I am looking for a solution more on the spirit of Concrete Maths book or Crux or in that of another remarkable book, Generatingfunctionology, by Wilf. I dare to say that because the algebra involved when one tries to solve "by hand"  these sums is so rich that they will keep interesting people, even when that formidable machine is at our disposal.

Return to [Polya Home Page] [Members] [Problem Center] [Inventory] [Reserve Area]