8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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}.$$ $\endgroup$ – anon Nov 22 '11 at 22:48
6
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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