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?

  • $\begingroup$ 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... $\endgroup$ – J. M. isn't a mathematician Aug 8 '12 at 16:26
  • $\begingroup$ 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. $\endgroup$ – Tyler Aug 8 '12 at 16:32
  • $\begingroup$ Read the middle paragraph on page 228: "If we apply...is not summable in hypergeometric terms." $\endgroup$ – user940 Aug 8 '12 at 16:35

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

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Tyler Aug 8 '12 at 18:44
  • $\begingroup$ @tyler Hehe, it happens. You get so excited about your question that you start looking for an answer and miss it. $\endgroup$ – GeoffDS 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})$$.

| cite | improve this answer | |
  • $\begingroup$ Interesting formula! Could you provide a reference? $\endgroup$ – Markus Scheuer May 1 '15 at 13:57
  • 1
    $\begingroup$ @Markus Scheuer: No reference. I derived this formula by myself. $\endgroup$ – nczksv May 1 '15 at 23:44
  • $\begingroup$ Great! Very nice formula! :-) $\endgroup$ – Markus Scheuer May 2 '15 at 5:20
  • $\begingroup$ 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. $\endgroup$ – Tyler May 13 '15 at 18:20
  • $\begingroup$ Could you explain how you derived this? $\endgroup$ – 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} $$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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