**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.**

Discussion:
**[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

http://www.cis.upenn.edu/~wilf/Downld.html

**[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]**