Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In Concrete Mathematics, the authors state that there is no closed form for $$\sum_{k\le K}{n\choose k}.$$ This is stated shortly after the statement of (5.17) in section 5.1 (2nd edition of the book).

How do they know this is true?

share|improve this question
Actually, there is a "closed form", but it involves the Gaussian hypergeometric function. Thus, it boils down again to whose definition of "closed form" are we using... –  J. M. Aug 8 '12 at 16:26
I'm guessing the Concrete Mathematics authors had some specific result in mind, and my question is hoping to understand how one can show this expression does not have a closed form for whatever definition of "closed form" they were using. –  Tyler Aug 8 '12 at 16:32
Read the middle paragraph on page 228: "If we apply...is not summable in hypergeometric terms." –  Byron Schmuland Aug 8 '12 at 16:35

1 Answer 1

up vote 5 down vote accepted

The very next paragraph of the book says:

"Near the end of this chapter, we'll study a method by which it's possible to determine whether or not there is a closed form for the partial sums of a given series involving binomial coefficients, in a fairly general setting. This method is capable of discovering identities (5.16) and (5.18), and it also will tell us that (5.17) is a dead end."

As Byron pointed out, the specific answer is on P228. The method is called Gosper's algorithm. The next section tells you about Zeilberger's algorithm, which can do more. The book "A = B" is available free online and is all about such mathematics, including more powerful stuff than what is shown in "Concrete Mathematics".

share|improve this answer
Aha, I am a bit embarrassed to have not read further myself. Thanks for the answer and the reference to A=B, which looks very interesting. –  Tyler Aug 8 '12 at 18:44
@tyler Hehe, it happens. You get so excited about your question that you start looking for an answer and miss it. –  Graphth Aug 8 '12 at 18:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.