Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've read this interesting article by Woersch (1994) dealing with approximation of binomial coefficients (rows of Pascal's triangle). I'm just wondering if similar bounds exist for partial binomial sums such as (for $ m < n $)

$$\sum_{k=0}^{m} \binom{n}{k}x^k$$ and $$\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}.$$

If $0<x<1$ the second case can be approximated with the normal distribution using the central limit theorem. If anyone could suggest some general approach to solving problems like these I'd be very grateful.

share|cite|improve this question
Just as a note, they're kinda the same problem;$$\sum_{k=0}^m{n\choose k}x^k(1-x)^{n-k}=(1-x)^n\sum_{k=0}^n{n\choose k}\left(\frac{x}{1-x}\right)^k;$$ $$y=\frac{x}{1-x}\iff x=\frac{y}{1+y}.$$ – anon Nov 22 '11 at 22:48
up vote 5 down vote accepted

As pointed out in the comments, if you can solve one problem you can solve the other, so I'm just going to give a bound for the first sum. Also, $x > 0$. (It seems like the case $x<0$ might be trickier.) We have

$\begin{align} &\frac{\binom{n}{m}x^m + \binom{n}{m-1}x^{m-1} + \cdots + \binom{n}{0}x^0}{\binom{n}{m}x^m} \\ &= 1 + \frac{m}{(n-m+1)x} + \frac{m(m-1)}{(n-m+1)(n-m+2)x^2} + \cdots + \frac{m!}{n^{\underline{m}}!x^m} \\ &\leq 1 + \frac{m}{(n-m+1)x} + \left(\frac{m}{(n-m+1)x}\right)^2 + \cdots + \left(\frac{m}{(n-m+1)x}\right)^m, \end{align}$

which is the partial sum of a geometric series. Therefore,

$$\sum_{k=0}^m \binom{n}{k} x^k \leq \binom{n}{m} x^m \frac{1 - r^{m+1}}{1-r},$$ where $$r = \frac{m}{(n-m+1)x}.$$

Of course, if $r < 1$, then we obtain the simpler expression $$\sum_{k=0}^m \binom{n}{k} x^k \leq \binom{n}{m} x^{m+1} \frac{n-m+1}{(n-m+1)x-m}.$$

(To give credit where credit is due, this is an adaption of Michael Lugo's answer to a related question on Math Overflow.)

share|cite|improve this answer
I like this answer. – Michael Lugo Dec 2 '11 at 6:05
thanks, Mike. Is there any way to estimate the size of error? $O(\frac{1}{m})$ maybe? – user19821 Dec 7 '11 at 1:11

Your Answer


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.