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'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|improve this question
1  
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
add comment

1 Answer

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|improve this answer
2  
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
add comment

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.