Let $0\le k \le n$. Prove that $$ n\binom{n}{k}\int_{0}^{\frac{k}{n+1}}t^k(1-t)^{n-k}\,dt \le 1/2. $$ As far as I know 1) it is proved for $\frac{k}{n+1}\le 1/2$ and 2) not proved for $1/2 <\frac{k}{n+1}< 1$. Is it really so?

  • 1
    $\begingroup$ The integral is $B_{k/(n+1)}(k+1,n-k+1)$, in the notation of the Wolfram site. Various transformations and identities (though nothing obviously relevant) are cataloged here: functions.wolfram.com/GammaBetaErf/Beta3 $\endgroup$ Apr 17, 2016 at 14:31
  • $\begingroup$ @KevinO'Bryant - thank you for the reference. But it is not obvious how to use such transformations. $\endgroup$
    – Sergei
    Apr 17, 2016 at 14:42
  • $\begingroup$ No, they don't seem relevant to me, either. But my first step was to track it down and see what was there. I posted the link for the convenience of the next reader. $\endgroup$ Apr 17, 2016 at 14:54
  • 2
    $\begingroup$ Where can one find the proof for $k\le(n+1)/2$? $\endgroup$ Apr 17, 2016 at 17:55
  • $\begingroup$ I knew of this problem from Prof. Igor Novikov, he also said that proved the first part. I do not know his proof. $\endgroup$
    – Sergei
    Apr 17, 2016 at 20:30

1 Answer 1


The following stronger inequality holds for all $k=0,\dots,n$: $$ (n+1)\binom{n}{k}\int_{0}^{\frac{k}{n+1}}t^k(1-t)^{n-k}\,dt \le 1/2. $$ Indeed, the latter inequality means precisely that the median $m$ of the Beta distribution with parameters $a:=k+1\ge1$ and $b:=n-k+1\ge1$ is no less than $\frac{k}{n+1}=\frac{a-1}{a+b-1}$. By the well-known "Mode, Median, and Mean Inequalities" for the Beta distribution (see e.g. page 2 in http://arxiv.org/abs/1111.0433v1), \begin{equation} m\ge\frac{a-1}{a+b-2}\bigwedge\frac{a}{a+b} \ge\frac{a-1}{a+b-1}=\frac{k}{n+1}, \end{equation} as desired.

  • $\begingroup$ Great! We can not take $c=1/2$ from the beginning? $\endgroup$
    – Sergei
    Apr 19, 2016 at 3:48
  • $\begingroup$ what I do not understand properly. For $k=n$ we may take $c=1/e$. If the reverse induction works the inequality must be true with this constant, $c=1/e$. But it is not so. $\endgroup$
    – Sergei
    Apr 19, 2016 at 4:25
  • $\begingroup$ @Sergei : We cannot take $c=1/2$ right away from the beginning, because I can (in the beginning) get $1/2$ only in the limit. But we can take any $c>1/2$ for all large enough $n$, and then by the backward induction get any such $c$ for all $n$. Thus, we get $1/2$ for all $n$. $\endgroup$ Apr 19, 2016 at 5:20
  • $\begingroup$ @Sergei : For the backward induction to work, it is not enough to have a $c$ just for one value of $k$ (say for $k=n$). We need to have a $c$ for all $k=0,\dots,n$. $\endgroup$ Apr 19, 2016 at 5:20
  • $\begingroup$ your solution seems to be clever and good. Unfortunately I am too silly for understanding it, but it is my problem... But - it is just an estimate for an integral, let me believe it has a simple calculus solution. $\endgroup$
    – Sergei
    Apr 19, 2016 at 12:04

Your Answer

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