5
$\begingroup$

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?

  • 0
    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...2012-08-08
  • 0
    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.2012-08-08
  • 0
    Read the middle paragraph on page 228: "If we apply...is not summable in hypergeometric terms."2012-08-08

3 Answers 3

6

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

  • 0
    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.2012-08-08
  • 0
    @tyler Hehe, it happens. You get so excited about your question that you start looking for an answer and miss it.2012-08-08
4

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})$$.

  • 0
    Interesting formula! Could you provide a reference?2015-05-01
  • 1
    @Markus Scheuer: No reference. I derived this formula by myself.2015-05-01
  • 0
    Great! Very nice formula! :-)2015-05-02
  • 0
    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.2015-05-13
  • 0
    Could you explain *how* you derived this?2015-05-27
  • 0
    Plugging in $4^{-n}$ to the generating function gives an expression for the quantity (for all values of $K$) in base $4^n$, where the the $K$th "digit" in base $4^n$ is $K$th partial sum. The mod and floor get rid of every digit except for the zeros place digit, which has the answer. While it's neat, I would not consider this a closed form, because the method works on basically anything with a generating function. Thus, it would make the concept of a closed form mostly useless. One could rule this out by requiring closed form expressions to only use operators on the set of $O(n)$-bit numbers.2017-08-02
2

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} $$