Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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 not summable in hypergeometric terms." – Byron Schmuland Aug 8 '12 at 16:35
up vote 6 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|cite|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

For every positive integer $n$,

$$\sum_{k\le K}{n\choose k}=\left\lfloor\frac{(4^{K+1}\cdot(1+4^{-n}))^{n}}{4^{n}-1}-4^{n}\cdot\left\lfloor\frac{(4^{K}\cdot(1+4^{-n}))^{n}}{4^{n}-1} \right\rfloor\right\rfloor$$

Note that $$\sum_{k\le K}{n\choose k}=[x^{0}]\left(\frac{(1+x)^n}{x^{K}(1-x)}\right)$$.

Hence $$\sum_{k\le K}{n\choose k}=mod(\left\lfloor\frac{(1+x)^n}{x^{K}(1-x)}\biggr|_{x=4^{-n}}\right\rfloor,4^{n})$$.

share|cite|improve this answer
Interesting formula! Could you provide a reference? – Markus Scheuer May 1 '15 at 13:57
@Markus Scheuer: No reference. I derived this formula by myself. – nczksv May 1 '15 at 23:44
Great! Very nice formula! :-) – Markus Scheuer May 2 '15 at 5:20
This is cool! I find the last formula much easier to grasp than the first. I see that the value 4 here is not critical - it looks like any integer > 2 will work. Thanks for finding and posting this. – Tyler May 13 '15 at 18:20
Could you explain how you derived this? – wchargin May 27 '15 at 22:37

Proof of the answer by nczksv.

$$ \begin{array}{l} f = \dfrac{(1+x)^n}{x^K \cdot (1-x)} = \left(\dfrac{1+x}{x}\right)^n \cdot \dfrac{x^{n-K}}{1-x}\\ = \left(4^n+1\right)^n \cdot 4^n \cdot \dfrac{x^{n-K}}{4^n - 1}\\ = \dfrac{\left(4^n+1\right)^n \cdot 4^n }{(4^n - 1)(4^n)^{(n-K)}} \end{array} $$ Let $A = 4^n - 1$, mod = $A+1$. Consider both flooring function and mod function, Note that

$$\forall r > 1, ~ \left\lfloor \frac{(A+1)^r}{A} \right\rfloor \equiv \left\lfloor (A+1)^{r-1} + \frac{(A+1)^{r-1}}{A} \right\rfloor = \left\lfloor \frac{(A+1)^{r-1}}{A} \right\rfloor = \frac{A+1}{A}$$ we have $$ \begin{array}{l} f = \dfrac{\left(A+2\right)^n }{A \cdot (A+1)^{n-K-1}} \\ = \dfrac{ \sum_{k=0}^{K} {n \choose k} (A+1)^{n-k} + \sum_{k=K+1}^{n} {n \choose k} (A+1)^{n-k} }{A \cdot (A+1)^{n-K-1}}\\ = \dfrac{ \sum_{k=0}^{K} {n \choose k} (A+1)^{K+1-k} }{A} + \dfrac{ \sum_{k=K+1}^{n} {n \choose k} (A+1)^{K+1-k} }{A}\\ = \sum_{k=0}^{K} {n \choose k} + \dfrac{ \sum_{k=0}^{K} {n \choose k} }{A} + \dfrac{ \sum_{k=K+1}^{n} {n \choose k} (A+1)^{K+1-k} }{A} = \sum_{k=0}^{K} {n \choose k} + 0 \end{array} $$

share|cite|improve this answer

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.