MathOverflow is a question and answer site for professional mathematicians. 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 need to bound a sum of a portion of binomial coefficients in terms of "the next one", and understand what is the best which can be said in this sense.

Given a real number $t \geq 2$, call $P(t)$ the following assertion.

"There exists $N \in \mathbb{N}$ such that $\sum_{i=1}^{[n/t]} \binom{n}{i} \leq \binom{n}{[n/t]+1}$ for every $n \geq N$".

Here $[a]$ denotes the floor of $a$ (the largest integer at most $a$). Note that $P(t)$ is clearly false if $t \leq 2$. Using what I found here (answer of Michael Lugo):

Sum of 'the first k' binomial coefficients for fixed n

I was able to show that $P(3)$ is true.

My question is: is it true that $P(t)$ is false for every $2 < t < 3$?

share|cite|improve this question
Yes. For all n, the sum is minorized by a geometric series of length k and ratio close to (n - n/t -k)/(n/t - k). Now pick n very large so that the k's disappear, and so that the geometric series has sum large enough. This can be done for t arbitrarily close to 3. Gerhard "Ask Me About Sum Estimation" Paseman, 2013.05.09 – Gerhard Paseman May 9 '13 at 14:45
My comment above would be improved by saying for large enough n, and using (1 - 1/t)/(1/t) as the target ratio. In any case, for t close to and less than 3, one can find k and then choose n accordingly. Gerhard "Still Answering The Question Affirmatively" Paseman, 2013.05.08 – Gerhard Paseman May 9 '13 at 15:21
Also, for t far from 2, one can find decent approximations to the sum using a combination of geometric series and combining adjacent terms to express the sum as a sum of fewer terms of (n+1) choose stuff. Gerhard "Search MathOverflow For Binomial Approximation" Paseman, 2013.05.09 – Gerhard Paseman May 9 '13 at 15:27
@Gerhard: Agreed, and it shouldn't be too hard to identify the boundary exactly. – Brendan McKay May 10 '13 at 5:30

Your Answer


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

Browse other questions tagged or ask your own question.