No closed form for the partial sum of ${n\choose k}$ for $k \le K$?

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?

Solution 1:

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

Solution 2:

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

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