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 have a sequence

$$a_n = (1-p)^n \sum_{\frac{n}{2}\le k \le n} \binom{n}{k} \left( \frac{p}{1-p} \right)^k.$$

I want to show that $a_n\to 0$ when $n\to\infty$ if $0\le p < \frac{1}{2}$. Here's a plot of the sequence for $p=\frac{1}{3}$:

plot of a_n

Failed attempt:

$$\begin{align} (1-p)^n \sum_{\frac{n}{2}\le k \le n} \binom{n}{k} \left( \frac{p}{1-p} \right)^k <& (1-p)^n \sum_{0 \le k \le n} \binom{n}{k}\left(\frac{p}{1-p}\right)^k \text{ for } n\ge 1\\ =& (1-p)^n \left(1+\frac{p}{1-p}\right)^n = 1. \end{align}$$

My hope here was to end up with something like $0.99^n$ in that last step so I could argue that since $a_n<0.99^n$ and $0.99^n\to 0$ as $n\to\infty$, $a_n\to\infty$. Unfortunately it came out to 1, not $0.99^n$.

share|cite|improve this question
up vote 2 down vote accepted

This is a probability question in disguise. Let $X$ be a binomial$(n,p)$ random variable, so $X$ has mean $\mu=np$ and variance $\sigma^2=np(1-p)$. We can write your sum as $a_n=P(X\geq n/2)$, and by Chebyshev's inequality we get $$a_n\leq P\left(|X-\mu|\geq n(1/2-p)\right)\leq {\sigma^2\over n^2(1/2-p)^2}={p(1-p)\over n(1/2-p)^2}.$$ This clearly goes to zero as $n\to\infty$.

You could reverse engineer this proof to eliminate the probability, if necessary.

share|cite|improve this answer
Thanks! Looking back at my class notes, it seems my professor invoked a form of Chebyshev's inequality a few times without referring to it by name. It's nice to know what it's called. – Snowball Feb 13 '12 at 3:56
@Snowball Glad to be of help. – Byron Schmuland Feb 13 '12 at 4:04

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.