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

Let $j \in N, n\in N, n>1, q\geq 2$. I would like to show that $$ \sum_{j=\frac{n}{\ln n}}^{\sqrt n/2}(2j-n)^q{n \choose j}<\sum_{j=\sqrt n/2}^{{\frac n2}}(2j-n)^q{n \choose j} $$

Any help would be appreciated.

Thank you.

share|cite|improve this question
motivation?${}$ – Grumpy Parsnip Apr 19 '12 at 4:16
I am working under some approximation question. I wanted to 'cut out' part of the sum. It seems that the LHS sum is much more smaller then the RHS sum. – David Apr 19 '12 at 4:20
Are you sure about the limits of the LHS? – Yuval Filmus Apr 19 '12 at 4:28
cross-posted to MO: – user16299 Jun 8 '12 at 21:21
up vote 2 down vote accepted

One approach would be to bound the term $(2j-n)^2$ on both sides, use the upper bound on the LHS, and the upper bound on the RHS. Then estimate the binomial sums using the identities $$ \left( \frac{n}{k} \right)^k \leq \binom{n}{k} \leq n^k, $$ or if you want to be fancier, using Stirling's approximation or even using Berry-Esséen (recall that a binomial distribution is close to a normal distribution).

share|cite|improve this answer
Thank you. Could you please explain how did you get term $(2j-q)^2$? – David Apr 19 '12 at 4:42
That was just a typo, sorry. – Yuval Filmus Apr 19 '12 at 15:07

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.