TITLE: Partial sum of rows of Pascal's triangle
QUESTION [9 upvotes]: I'm interested in finding 
$$\sum_{k=0}^m \binom{n}{k}, \quad  m<n$$
which form rows of Pascal's triangle. Surely $\sum\limits_{k=0}^n \binom{k}{m}$ using addition formula, but the one above involves hypergeometric functions and I don't know how to approach it.
EDIT: if possible, please don't solve it, just a few hints will do.

REPLY [10 votes]: There really isn't a closed-form expression for the partial row sums of Pascal's triangle.  The expression I imagine you're getting, $$\sum_{k=0}^m \binom{n}{k} = 2^n - \binom{n}{m+1} {}_2F_1(1,m+1-n;m+2;-1),$$
isn't really a closed-form; it's just the original sum expressed differently.  (One of the answers to the MO question mentioned above by anon says this as well.)
So, why is this?  
(In what follows, the original version contained a partial explanation, as the OP merely wanted hints.  Now that the OP has completed the derivation for him/herself, I'm giving the full argument.)
We have 
$$
\binom{n}{m+1} {}_2F_1(1,m+1-n;m+2;-1) = \binom{n}{m+1} \sum_{k=0}^{\infty} \frac{1^{\overline{k}} (m+1-n)^{\overline{k}} (-1)^k}{(m+2)^{\overline{k}} k!}$$
$$= \binom{n}{m+1} \left[ 1 - \frac{1(m+1-n)}{(m+2)1} + \frac{2!(m+1-n)(m+2-n)}{(m+2)(m+3)2!} \mp \cdots \right]$$ 
$$= \frac{n!}{(m+1)!(n-m-1)!} \left[ 1 + \frac{n-m-1}{m+2} + \frac{(n-m-1)(n-m-2)}{(m+2)(m+3)} + \cdots \right]$$
$$= \binom{n}{m+1} + \binom{n}{m+2} + \binom{n}{m+3} + \cdots $$
$$= \sum_{k=m+1}^n \binom{n}{k}.$$
Thus 
$$\sum_{k=0}^m \binom{n}{k} = 2^n - \binom{n}{m+1} {}_2F_1(1,m+1-n;m+2;-1)$$
is just a rewrite of the original sum (together with the fact that $\sum_{k=0}^n\binom{n}{k} = 2^n$).

By the way, Concrete Mathematics spends some time discussing $\sum_{k=0}^m \binom{n}{k}$.  On p. 165 they say 

"Surely if we can evaluate the corresponding sum with alternating signs, we ought to be able to do this one.  But no; there is no closed form for the partial sum of a row of Pascal's triangle."

Then on p. 228 they discuss the sum again, in the context of Gosper's algorithm for finding partial hypergeometric sums.  This gives an explanation for why there is no closed-form, as Gosper's algorithm either finds one or proves that no such one exists.

"If we apply the same method to find the indefinite sum $\sum \binom{n}{k} \delta k,$ without the $(-1)^k$, everything will be almost the same except that $q(k)$ will be $n-k$; hence $Q(k) = n-2k$ will have greater degree than $R(k)=n$, and we will conclude that $d$ has the impossible value $\deg(p) - \deg(Q) = -1$.  (The polynomial $s(k)$ cannot have negative degree, because it cannot be zero.)  Therefore the function $\binom{n}{k}$ is not summable in hypergeometric terms."

However, Exercise 9.42 on p. 492 asks to prove the asymptotic formula $$\sum_{k \leq \alpha n} \binom{n}{k} = 2^{n H(\alpha) - \frac{1}{2} \log_2 n + O(1)},$$
where $H(\alpha) = \alpha \log_2 \frac{1}{\alpha} + (1-\alpha) \log_2 (\frac{1}{1-\alpha})$, for $\alpha \leq \frac{1}{2}$.  
There is an outline of the proof of this result in the answer section, so you can look that up if you want to see how they obtain it.  See also robjohn's comments below.
If $\alpha \geq \frac{1}{2}$, then $$\sum_{k \leq \alpha n} \binom{n}{k} = 2^{n + O(1)},$$ since the sum is bounded above by $2^n$ and below by $2^{n-1}$.
(Page numbers are for the second edition of Concrete Mathematics.)
{"set_name": "stack_exchange", "score": 9, "question_id": 69532}