Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What exactly would you like to know about these numbers ? –  Joel Cohen Oct 3 '11 at 13:13
1  
The idea is to figure out an expression for $$\sum_{k=m+1}^\infty \binom{n}{k};$$ the hypergeometric expression pops out when you start converting the binomial coefficients to Pochhammer symbols. –  J. M. Oct 3 '11 at 13:28
    
@Joel: a closed expression. it's something like $2^n-F$ where $F$ is some hypergeometric expression. –  sigma.z.1980 Oct 3 '11 at 13:31
1  
Also on MathOverflow (with a separate question for lower bounds). –  anon Oct 3 '11 at 13:35
    
So, you're interested in knowing how ${}_2 F_1$ pops up, or do you want something else? –  J. M. Oct 3 '11 at 14:07
show 3 more comments

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
    
yeah, by 'closed' I meant involving hypergeometric term –  sigma.z.1980 Oct 3 '11 at 16:38
    
@sigma.z.1980: I'll edit my answer with an explanation of why the hypergeometric expression is just a rewrite of the original sum. –  Mike Spivey Oct 3 '11 at 16:41
    
Exercise 9.42 is on page 478 in the "first edition" (not so numbered for the same reason WWI was not called WWI until WWII). –  robjohn Oct 3 '11 at 16:56
    
@sigma.z.1980: I just saw your comment that you wanted hints rather than a complete answer, so I'll hold off on posting the full answer. You need to show that the hypergeometric sum is equal to $\sum_{k=m+1}^n \binom{n}{k}$ (as in J.M.'s comment above). Where are you stuck in that process? –  Mike Spivey Oct 3 '11 at 16:57
1  
The asymptotic formula in Concrete Mathematics is only for $\alpha<\frac{1}{2}$ and simply looks at $\sum_{k\leq\alpha n}\binom{n}{k}$ as a geometric series with lead term $\binom{n}{k}$ and ratio $\frac{\alpha}{1-\alpha}$, then uses Stirling's Approximation to get $\binom{n}{k}$. –  robjohn Oct 3 '11 at 17:37
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.