Summation of combinations up to $r-1$ terms

Question

I am trying to come up with a simplified expression for $$\sum_{k=r}^{n}\binom{n}{k}$$ Choosing $x=y=1$ in Binomial theorem, I have $$2^n = \sum_{k=0}^{n}\binom{n}{k}$$ $$2^n = \sum_{k=0}^{r-1}\binom{n}{k} + \sum_{k=r}^{n}\binom{n}{k}$$ $$\sum_{k=r}^{n}\binom{n}{k} = 2^n - \sum_{k=0}^{r-1}\binom{n}{k}$$ Now, It looks like I need a simplified expression for $$\sum_{k=0}^{r-1}\binom{n}{k}$$ Am I stuck in a loop or I can get away? Any possible answer/tip would help me.

Answer 1

Because the Binomial and Beta distributions are directly related, compute that

$$\begin{aligned} \sum_{k=r}^n \binom{n}{k} &= 2^n \sum_{k=r}^n \binom{n}{k} \left(\frac{1}{2}\right)^k\left(1-\frac{1}{2}\right)^{n-k}\\ &= \frac{2^n}{B(r, n-r+1)}\int_0^{1/2} x^{r-1}(1-x)^{(n-r+1)-1}\,\mathrm{d}x. \end{aligned}$$

The right hand side is $2^n$ times the cumulative distribution function of a Beta$(r, n-1+1)$ variable, evaluated at $p=1/2.$ Apart from the factor of $2^n,$ this is known as the Incomplete Beta function. Because the denominator has a similar formula,

$$B(r, n-r+1) = \int_0^1 x^{r-1}(1-x)^{(n-r+1)-1}\,\mathrm{d}x,$$

the resulting expression is in a closed form (that is, its length--and the time needed for its evaluation--does not vary with $n$ or $r$ in a standard model of computing).