8
$\begingroup$

Is it true that

$$\frac{\dbinom{3n}{0}+\dbinom{3n}{1}+\cdots+\dbinom{3n}{n-1}}{2^{3n}}<\frac13$$ for all positive integers $n$?

I've plotted the first few values of $n$ and noticed that the left-hand side decreases rapidly, so I'm quite sure that it's true. But how to prove it? Induction doesn't looks like helping much here.

$\endgroup$
12
$\begingroup$

Here's an outline of a proof. We have that $\binom{3n}{0}+\binom{3n}{1}+\cdots+\binom{3n}{3n} = 2^{3n}$. Split the sum into thirds. The middle third is clearly larger than the other two, which, being equal by symmetry, must therefore each account for less than a third of the total.

$\endgroup$
0
7
$\begingroup$

The Binomial Distribution $2^{-3n}\binom{3n}{k}$ has mean $\frac32n$ and variance $\frac34n$. Thus, by Chebyshev's Inequality, we have $$ P\left[|x-\tfrac32n|\ge a\right]\le\frac{\frac34n}{a^2}\tag{1} $$ Letting $a=\frac12n+1$ yields $$ \begin{align} P\left[|x-\tfrac32n|\ge\tfrac12n+1\right] &\le\frac{\frac34n}{(\frac12n+1)^2}\\ &=\frac{3n}{(n+2)^2}\tag{2} \end{align} $$ By the symmetry of the binomial distribution, we get $$ \begin{align} P\left[x\le n-1\right] &=P\left[x-\tfrac32n\le-\tfrac12n-1\right]\\ &\le\bbox[5px,border:2px solid #C0A000]{\frac{3n}{2(n+2)^2}}\tag{3} \end{align} $$ which is less than $\frac13$ for all $n$. In fact, it reaches a maximum of $\frac3{16}$ at $n=2$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.