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

3 Answers 3

7

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

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
    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
3

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