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

Question

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?

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

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

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

Answer 4

There's a number of asymptotic approximations. One of the simpler (assume wlog $N<\frac{n}{2} \in \mathbb{Z}$) upper bounds is obtained by dividing the partial sum by the largest term, $\binom{n}{N}$: $$ \frac{S_{n,N}}{\binom{n}{N}} = \frac{\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{N}}{\binom{n}{N}} = 1+ \frac{N}{n-N+1} + \ldots \frac{1}{\binom{n}{N}} $$ Each term in this sum, $\frac{\binom{n}{k}}{\binom{n}{N}}$, after cancellations, reduces to $$ a_{k,N,n} = \frac{(n-N)!}{(n-k)!}\cdot\frac{N!}{k!} \leq N^k $$ Since $N\geq k$, the first term is upper-bounded by $1$. As as result, the upper bound is just $$ S_{n,N} \leq \binom{n}{N}\sum_{k=0}^{N+1}N^k $$ the latter being a simple Geometric sum that exists in closed form. If you want to reduce it further, you get something like (Geometric sum approximation + Stirling's formula) $$ S_{n,N} \leq \bigg(n\bigg(1-\frac{1}{N}\bigg)\bigg)^{N+1} $$