[Computational Complexity] An Interesting Summation- NOT new but raises some ...
- 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.
- 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.
- 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.
- 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.
- 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.
Posted By GASARCH to Computational Complexity at 7/16/2008 09:21:00 AM