Is there a general formula for the sum of combinations

Question

I am learning statistics, and I'm doing some stuff with combinations. Some of the questions I have seen have answers which are equal to a sum of combinations. It made me wonder, is there a formula for the sum of combinations, i.e. $$\sum_{k=i}^{j}{n \choose k}$$ for $0\le i \le j \le n$?

I have looked at this question which calculates the results:
$$\sum_{k=(n+1)/2}^n \dbinom{n}k = 2^{n-1}, \ \text{for odd} \ n$$ and $$\sum_{k=n/2+1}^n \dbinom{n}k = 2^{n-1} – \dfrac12 \dbinom{n}{n/2}, \ \text{for even} \ n $$

Although, using Pascal's triangle, one could see that the result for odd n would just be the sum of the row / 2 = $2^n – 1$. Can't see an intuitive way to figure it out for even $n$ though.

I also know that ${n \choose 0} = {n \choose n} = 1 $

Answer 1

There is no such closed formula.

A corresponding statement can be found for instance in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik. See formula (5.17) where we can read

• How about the simpler partial sum, \begin{align*} \sum_{k\leq m}\binom{n}{k}=\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{m}\tag{5.17} \end{align*} ... But no; there is no closed form for the partial sum of a row of Pascal's triangle.