Return to Answer

Let $B(a,b;x):=\int_0^x t^{a-1}(1-t)^{b-1}dt$ denote, as usual, the value of the incomplete Beta function. We have to show that $$ n\binom{n}{k}B(k+1,n-k+1,\tfrac k{n+1}) \le 1/2 \quad\text{for $k=0,\dots,n$}. \tag{1} $$
I thought it would be easy to use asymptotic analysis to check that $(1)$ holds for any real $c>1/2$ (in place of $1/2$) if $n$ is large enough. This turned out to be not quite so easy, as we need uniformity in $k$, and we need to deal with cases when $k$ or $n-k$ is not large, even though $n\to\infty$. This is detailed in the addendum at the end of this answer.

Thus, we can use the reverse induction in $n$. That is, it is enough to show that, if $(1)$ holds for some natural $n+1\ge2$ in place of $n$ and some real $c>0$ in place of $1/2$, then it holds as written, but with the same real $c>0$ in place of $1/2$. The key here is the simple identity \begin{equation} B(a,b;x)=B(a+1,b;x)+B(a,b+1;x), \end{equation} which yields, by the reverse induction, $$ B(k+1,n-k+1,\tfrac k{n+1})=B(k+2,n-k+1,\tfrac k{n+1})+B(k+1,n-k+2,\tfrac k{n+1}) $$ $$ =B(k+2,n-k+1,\tfrac{k+1}{n+2})+B(k+1,n-k+2,\tfrac k{n+2})+I_1-I_2 $$ $$ \le\frac c{n+1}/\binom{n+1}{k+1} +\frac c{n+1}/\binom{n+1}{k}+I_1-I_2 =\frac{c(n+2)n}{(n+1)^2}\frac1{n\binom nk}+I_1-I_2 <\frac c{n\binom nk}+I_1-I_2, $$ where \begin{equation} I_1:=\int_{t_0}^{t_1}f(t)\,\frac{dt}t,\quad I_2:=\int_{t_1}^{t_2}f(t)\,\frac{dt}{1-t}, \end{equation} \begin{equation} f(t):=t^{k+1}(1-t)^{n-k+1},\quad t_0:=\tfrac k{n+2}, \quad t_1:=\tfrac k{n+1}, \quad t_2:=\tfrac{k+1}{n+2}, \end{equation} so that $0\le t_0<t_1<t_2<1$ and the function $f$ is increasing on the interval $(t_0,t_2)$.

It remains to check the inequality $I_1\le I_2$. This is easy: since $f$ is increasing, \begin{equation} I_1-I_2\le \int_{t_0}^{t_1}f(t_1)\,\frac{dt}t-\int_{t_1}^{t_2}f(t_1)\,\frac{dt}{1-t}=0. \end{equation} $\qed$

Addendum: The case $k=0$ is trivial. So, assume $k>0$. The left-hand side of $(1)$ is $\frac n{n+1}L_{n,k}$, where \begin{equation} L_{n,k}=P\Big(\frac{S_{k+1}+k+1}{S_{k+1}+T_{n-k+1}+n+2}\le\frac k{n+1}\Big) =P\Big(\frac{S_{k+1}+1}{\sqrt k}\le\frac{T_{n-k+1}}{\sqrt{n-k+1}}\sqrt{\frac{k}{n-k+1}}\Big), \end{equation} $S_{k+1}$ and $T_{n-k+1}$ are independent random variables (r.v.'s) such that $S_{k+1}+k+1$ and $T_{n-k+1}+n-k+1$ have the Gamma distributions with parameters $k+1,1$ and $n-k+1,1$ (respectively). We need to show that $\limsup_{n\to\infty}\max\{L_{n,k}\colon k=1,\dots,n\}\le1/2$.

Without loss of generality (wlog), it suffices to consider the following cases.

First is the case when $k\to\infty$ and $n-k\to\infty$. Then, by the central limit theorem, $\frac{S_{k+1}+1}{\sqrt k}\to Z_1$ and $\frac{T_{n-k+1}}{\sqrt{n-k+1}}\to Z_2$ in distribution, where $Z_1$ and $Z_2$ are standard normal r.v.'s, which are wlog independent. Wlog, $\sqrt{\frac{k}{n-k+1}}$ converges to a limit $a\in[0,\infty]$. So, by a version of Slutsky's theorem, $L_{n,k}$ converges to $P(Z_1\le aZ_2)=1/2$ or to $P(0\le Z_2)=1/2$ depending on whether $a<\infty$ or not.

The second case is when $k$ is fixed (and hence $n-k\to\infty$). Then $L_{n,k}\to P(S_{k+1}+1\le0)=P(S_{k+1}+k+1\le k)\le1/2$, where the inequality follows from the "Mode, Median, and Mean Inequality" for the Gamma distribution, which says that \begin{equation} M<m<\mu, \tag{2} \end{equation} where $M,m,\mu$ are the mode, median, and mean (respectively); see Richard A. Groeneveld and Glen Meeden, The American Statistician, 1977, Vol. 31, No. 3, pp. 120--121. Note that for the Gamma distribution with parameters $k+1,1$ one has $M=k$ and $\mu=k+1$, so that the median of $S_{k+1}+k+1$ is between $k$ and $k+1$.

Finally, the case when $n-k$ is fixed (and hence $k\to\infty$). Here $L_{n,k}\to P(0\le T_{n-k+1})=P(n-k+1\le T_{n-k+1}+n-k+1)\le1/2$, again by $(2)$, since the median of $T_{n-k+1}+n-k+1$ is less than $n-k+1$. $\qed$

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.

Let $B(a,b;x):=\int_0^x t^{a-1}(1-t)^{b-1}dt$ denote, as usual, the value of the incomplete Beta function. We have to show that $$ n\binom{n}{k}B(k+1,n-k+1,\tfrac k{n+1}) \le 1/2 \quad\text{for $k=0,\dots,n$}. \tag{1} $$
As suggested by Brendan McKay, it should be easy to use asymptotic analysis to check that $(1)$ holds for any real $c>1/2$ if $n$ is large enough. Thus, we can use the reverse induction in $n$. That is, it is enough to show that, if $(1)$ holds for some natural $n+1\ge2$ in place of $n$ and some real $c>0$ in place of $1/2$, then it holds as written, but with the same real $c>0$ in place of $1/2$. The key here is the simple identity \begin{equation} B(a,b;x)=B(a+1,b;x)+B(a,b+1;x), \end{equation} which yields, by the reverse induction, $$ B(k+1,n-k+1,\tfrac k{n+1})=B(k+2,n-k+1,\tfrac k{n+1})+B(k+1,n-k+2,\tfrac k{n+1}) $$ $$ =B(k+2,n-k+1,\tfrac{k+1}{n+2})+B(k+1,n-k+2,\tfrac k{n+2})+I_1-I_2 $$ $$ \le\frac c{n+1}/\binom{n+1}{k+1} +\frac c{n+1}/\binom{n+1}{k}+I_1-I_2 =\frac{c(n+2)n}{(n+1)^2}\frac1{n\binom nk}+I_1-I_2 <\frac c{n\binom nk}+I_1-I_2, $$ where \begin{equation} I_1:=\int_{t_0}^{t_1}f(t)\,\frac{dt}t,\quad I_2:=\int_{t_1}^{t_2}f(t)\,\frac{dt}{1-t}, \end{equation} \begin{equation} f(t):=t^{k+1}(1-t)^{n-k+1},\quad t_0:=\tfrac k{n+2}, \quad t_1:=\tfrac k{n+1}, \quad t_2:=\tfrac{k+1}{n+2}, \end{equation} so that $0\le t_0<t_1<t_2<1$ and the function $f$ is increasing on the interval $(t_0,t_2)$.

It remains to check the inequality $I_1\le I_2$. This is easy: since $f$ is increasing, \begin{equation} I_1-I_2\le \int_{t_0}^{t_1}f(t_1)\,\frac{dt}t-\int_{t_1}^{t_2}f(t_1)\,\frac{dt}{1-t}=0. \end{equation} $\qed$

Let $B(a,b;x):=\int_0^x t^{a-1}(1-t)^{b-1}dt$ denote, as usual, the value of the incomplete Beta function. We have to show that $$ n\binom{n}{k}B(k+1,n-k+1,\tfrac k{n+1}) \le 1/2 \quad\text{for $k=0,\dots,n$}. \tag{1} $$
I thought it would be easy to use asymptotic analysis to check that $(1)$ holds for any real $c>1/2$ (in place of $1/2$) if $n$ is large enough. This turned out to be not quite so easy, as we need uniformity in $k$, and we need to deal with cases when $k$ or $n-k$ is not large, even though $n\to\infty$. This is detailed in the addendum at the end of this answer.

Thus, we can use the reverse induction in $n$. That is, it is enough to show that, if $(1)$ holds for some natural $n+1\ge2$ in place of $n$ and some real $c>0$ in place of $1/2$, then it holds as written, but with the same real $c>0$ in place of $1/2$. The key here is the simple identity \begin{equation} B(a,b;x)=B(a+1,b;x)+B(a,b+1;x), \end{equation} which yields, by the reverse induction, $$ B(k+1,n-k+1,\tfrac k{n+1})=B(k+2,n-k+1,\tfrac k{n+1})+B(k+1,n-k+2,\tfrac k{n+1}) $$ $$ =B(k+2,n-k+1,\tfrac{k+1}{n+2})+B(k+1,n-k+2,\tfrac k{n+2})+I_1-I_2 $$ $$ \le\frac c{n+1}/\binom{n+1}{k+1} +\frac c{n+1}/\binom{n+1}{k}+I_1-I_2 =\frac{c(n+2)n}{(n+1)^2}\frac1{n\binom nk}+I_1-I_2 <\frac c{n\binom nk}+I_1-I_2, $$ where \begin{equation} I_1:=\int_{t_0}^{t_1}f(t)\,\frac{dt}t,\quad I_2:=\int_{t_1}^{t_2}f(t)\,\frac{dt}{1-t}, \end{equation} \begin{equation} f(t):=t^{k+1}(1-t)^{n-k+1},\quad t_0:=\tfrac k{n+2}, \quad t_1:=\tfrac k{n+1}, \quad t_2:=\tfrac{k+1}{n+2}, \end{equation} so that $0\le t_0<t_1<t_2<1$ and the function $f$ is increasing on the interval $(t_0,t_2)$.

It remains to check the inequality $I_1\le I_2$. This is easy: since $f$ is increasing, \begin{equation} I_1-I_2\le \int_{t_0}^{t_1}f(t_1)\,\frac{dt}t-\int_{t_1}^{t_2}f(t_1)\,\frac{dt}{1-t}=0. \end{equation} $\qed$

Addendum: The case $k=0$ is trivial. So, assume $k>0$. The left-hand side of $(1)$ is $\frac n{n+1}L_{n,k}$, where \begin{equation} L_{n,k}=P\Big(\frac{S_{k+1}+k+1}{S_{k+1}+T_{n-k+1}+n+2}\le\frac k{n+1}\Big) =P\Big(\frac{S_{k+1}+1}{\sqrt k}\le\frac{T_{n-k+1}}{\sqrt{n-k+1}}\sqrt{\frac{k}{n-k+1}}\Big), \end{equation} $S_{k+1}$ and $T_{n-k+1}$ are independent random variables (r.v.'s) such that $S_{k+1}+k+1$ and $T_{n-k+1}+n-k+1$ have the Gamma distributions with parameters $k+1,1$ and $n-k+1,1$ (respectively). We need to show that $\limsup_{n\to\infty}\max\{L_{n,k}\colon k=1,\dots,n\}\le1/2$.

Without loss of generality (wlog), it suffices to consider the following cases.

First is the case when $k\to\infty$ and $n-k\to\infty$. Then, by the central limit theorem, $\frac{S_{k+1}+1}{\sqrt k}\to Z_1$ and $\frac{T_{n-k+1}}{\sqrt{n-k+1}}\to Z_2$ in distribution, where $Z_1$ and $Z_2$ are standard normal r.v.'s, which are wlog independent. Wlog, $\sqrt{\frac{k}{n-k+1}}$ converges to a limit $a\in[0,\infty]$. So, by a version of Slutsky's theorem, $L_{n,k}$ converges to $P(Z_1\le aZ_2)=1/2$ or to $P(0\le Z_2)=1/2$ depending on whether $a<\infty$ or not.

The second case is when $k$ is fixed (and hence $n-k\to\infty$). Then $L_{n,k}\to P(S_{k+1}+1\le0)=P(S_{k+1}+k+1\le k)\le1/2$, where the inequality follows from the "Mode, Median, and Mean Inequality" for the Gamma distribution, which says that \begin{equation} M<m<\mu, \tag{2} \end{equation} where $M,m,\mu$ are the mode, median, and mean (respectively); see Richard A. Groeneveld and Glen Meeden, The American Statistician, 1977, Vol. 31, No. 3, pp. 120--121. Note that for the Gamma distribution with parameters $k+1,1$ one has $M=k$ and $\mu=k+1$, so that the median of $S_{k+1}+k+1$ is between $k$ and $k+1$.

Finally, the case when $n-k$ is fixed (and hence $k\to\infty$). Here $L_{n,k}\to P(0\le T_{n-k+1})=P(n-k+1\le T_{n-k+1}+n-k+1)\le1/2$, again by $(2)$, since the median of $T_{n-k+1}+n-k+1$ is less than $n-k+1$. $\qed$

Let $B(a,b;x):=\int_0^x t^{a-1}(1-t)^{b-1}dt$ denote, as usual, the value of the incomplete Beta function. We have to show that $$ n\binom{n}{k}B(k+1,n-k+1,\tfrac k{n+1}) \le 1/2 \quad\text{for $k=0,\dots,n$}. \tag{1} $$
As suggested by Brendan McKay, it should be easy to use asymptotic analysis to check that $(1)$ holds for any real $c>1/2$ if $n$ is large enough. Thus, we can use the reverse induction in $n$. That is, it is enough to show that, if $(1)$ holds for some natural $n+1\ge2$ in place of $n$ and some real $c>0$ in place of $1/2$, then it holds as written, but with the same real $c>0$ in place of $1/2$. The key here is the simple identity \begin{equation} B(a,b;x)=B(a+1,b;x)+B(a,b+1;x), \end{equation} which yields, by the reverse induction, $$ B(k+1,n-k+1,\tfrac k{n+1})=B(k+2,n-k+1,\tfrac k{n+1})+B(k+1,n-k+2,\tfrac k{n+1}) $$ $$ =B(k+2,n-k+1,\tfrac{k+1}{n+2})+B(k+1,n-k+2,\tfrac k{n+2})+I_1-I_2 $$ $$ \le\frac c{n+1}/\binom{n+1}{k+1} +\frac c{n+1}/\binom{n+1}{k}+I_1-I_2 =\frac{c(n+2)n}{(n+1)^2}\frac1{n\binom nk}+I_1-I_2 <\frac c{n\binom nk}+I_1-I_2, $$ where \begin{equation} I_1:=\int_{t_0}^{t_1}f(t)\,\frac{dt}t,\quad I_2:=\int_{t_1}^{t_2}f(t)\,\frac{dt}{1-t}, \end{equation} \begin{equation} f(t):=t^{k+1}(1-t)^{n-k+1},\quad t_0:=\tfrac k{n+2}, \quad t_1:=\tfrac k{n+1}, \quad t_2:=\tfrac{k+1}{n+2}, \end{equation} so that $0\le t_0<t_1<t_2<1$ and the function $f$ is positive and increasing on the interval $(t_0,t_2)$.

It remains to check the inequality $I_1\le I_2$. The case $k=0$ is trivial. So, assume that $k>0$. Since each side of the inequality $I_1\le I_2$ is linear in $f$, it is enough to prove if for functions $f$ of the form $t\mapsto I\{t>w\}$, where $I$ is the indicator function and $w$ is any real number in the interval $[t_0,t_2]$. If $w\ge t_1$, then $I_1-I_2=0-I_2\le0$. If $w\in(t_0,t_1)$, then $I_1$ can be increased by moving $w$ to the left, without affecting $I_2$. So, without loss of generality $w=t_0$ and $f=1$, in which case $I_1-I_2=0$. $\qed$

Let $B(a,b;x):=\int_0^x t^{a-1}(1-t)^{b-1}dt$ denote, as usual, the value of the incomplete Beta function. We have to show that $$ n\binom{n}{k}B(k+1,n-k+1,\tfrac k{n+1}) \le 1/2 \quad\text{for $k=0,\dots,n$}. \tag{1} $$
As suggested by Brendan McKay, it should be easy to use asymptotic analysis to check that $(1)$ holds for any real $c>1/2$ if $n$ is large enough. Thus, we can use the reverse induction in $n$. That is, it is enough to show that, if $(1)$ holds for some natural $n+1\ge2$ in place of $n$ and some real $c>0$ in place of $1/2$, then it holds as written, but with the same real $c>0$ in place of $1/2$. The key here is the simple identity \begin{equation} B(a,b;x)=B(a+1,b;x)+B(a,b+1;x), \end{equation} which yields, by the reverse induction, $$ B(k+1,n-k+1,\tfrac k{n+1})=B(k+2,n-k+1,\tfrac k{n+1})+B(k+1,n-k+2,\tfrac k{n+1}) $$ $$ =B(k+2,n-k+1,\tfrac{k+1}{n+2})+B(k+1,n-k+2,\tfrac k{n+2})+I_1-I_2 $$ $$ \le\frac c{n+1}/\binom{n+1}{k+1} +\frac c{n+1}/\binom{n+1}{k}+I_1-I_2 =\frac{c(n+2)n}{(n+1)^2}\frac1{n\binom nk}+I_1-I_2 <\frac c{n\binom nk}+I_1-I_2, $$ where \begin{equation} I_1:=\int_{t_0}^{t_1}f(t)\,\frac{dt}t,\quad I_2:=\int_{t_1}^{t_2}f(t)\,\frac{dt}{1-t}, \end{equation} \begin{equation} f(t):=t^{k+1}(1-t)^{n-k+1},\quad t_0:=\tfrac k{n+2}, \quad t_1:=\tfrac k{n+1}, \quad t_2:=\tfrac{k+1}{n+2}, \end{equation} so that $0\le t_0<t_1<t_2<1$ and the function $f$ is increasing on the interval $(t_0,t_2)$.

It remains to check the inequality $I_1\le I_2$. This is easy: since $f$ is increasing, \begin{equation} I_1-I_2\le \int_{t_0}^{t_1}f(t_1)\,\frac{dt}t-\int_{t_1}^{t_2}f(t_1)\,\frac{dt}{1-t}=0. \end{equation} $\qed$