Wednesday, July 16, 2008

An Interesting Summation- NOT new but raises some questions

In my last post I asked for information about the summation &sumi (-1)i (k choose i)(a+i)k (Where the sum goes from i=0 to i=k.)

I knew it was (-1)kk! but wondered if this was already known and if there was a combinatorial proof. The comments said YES to both questions. (Side Note: THANK YOU READERS. The comments were INTELLIGENT and HELPFUL!.) This raises some questions.
  1. The book A=B gives a way to determine for a large class of sums if they are expressible in closed form, and if so what that form is. My sum did not fall into there category since mine has that pesky a in it.
  2. Since my summation is solvable with calculus of finite differences is there an algorithm, perhaps an extension of A=B, that will also deal with summations like this. Might be hard to define like this.
  3. One of the commenters gave a combinatorial proof but then said that it was better understood using calculus of differences. Doren Zeilberger might agree. In this interesting essay he seems to be saying that once you have a mechanical proof of something (e.g., like those in A=B) then having combinatorial proofs of them that are over a page then such proofs are not that interesting. The combinatorial proof was under a page, but I think Zeilberger was really referring to how complicated things are rather than actual page length. Might be a close call.
  4. Dear Anonymous 6 on my last post: When I write a paper that uses this sum I will include your combinatorial proof. I will of course credit you. What name should I use? Anonymous 6 (and point to the website) of course.


  1. Are you sure you want to "point to your website" in a mathematical paper? Website addresses are typically not permanent...

  2. Doron Zeilberger10:13 AM, July 17, 2008

    "NOT new" is an understatement.
    You were scooped by Euler. This may be one of the most rediscovered identities ever.

    * Euler's formula nth Differences of PowersEuler's formula nth Differences of Powers
    * H. W. Gould
    * The American Mathematical Monthly, Vol. 85, No. 6 (Jun. - Jul., 1978), pp. 450-467

    The question of A=B-ing it is a good one
    and has been (partly) done see sec. 9.11 of A=B