15
$\begingroup$

My friend noticed that for $n>12$, we have the following pattern in the binomial coefficients.

$$\sum_{i=0}^{\lfloor n/3 \rfloor}\binom{n}{i} < \binom{n}{\lfloor n/3 \rfloor + 1}$$ $$\sum_{i=0}^{\lfloor n/3 \rfloor + 1}\binom{n}{i} > \binom{n}{\lfloor n/3 \rfloor + 2}$$

We've checked these inequalities up to $n=200$ with a computer, but have not been able to come up with a proof.

Attempt: We've attempted a asymptotic approach using Stirling approximation $$\binom{n}{k} \approx \sqrt{\frac{n}{2\pi k (n-k)}} \frac{n^n}{k^k (n-k)^{n-k}}$$ but approximating with an integral doesn't seem to help very much, as it seems quite hard to compare $$\int_0^{n} \sqrt{\frac{3n}{2\pi k (3n-k)}} \cdot \frac{(3n)^n}{k^k (3n-k)^{3n-k}} dx \quad \text{and} \quad \sqrt{\frac{3}{4\pi}} \frac{3^{3n}}{2^{2n}}$$

One thing I have realized which seems important is that $$2 \binom{3n}{n} \approx \binom{3n}{n+1} $$ However, I have not been able to work this into a proof. Any ideas?

2nd Attempt: Using B. Mehta's linked post, in particular this inequality, $$\sum_{i=0}^k \binom{n}{i} \leq \binom{n}{k} \frac{n-(k-1)}{n-(2k-1)}$$ subbing in $k=\lfloor\frac{n}{3}\rfloor$, we can almost get the inequality as follows $$\sum_{i=0}^{\lfloor n/3 \rfloor} \binom{N}{i} \leq \binom{n}{\lfloor n/3 \rfloor} \frac{n-\lfloor n/3 \rfloor + 1}{n - 2 \lfloor n/3 \rfloor + 1}$$ Now we can use that $\binom{n}{k+1} = \binom{n}{k} \frac{n-k}{k+1}$ to get $$\sum_{i=0}^{\lfloor n/3 \rfloor} \binom{N}{i} \leq \binom{n}{\lfloor n/3 \rfloor + 1}\frac{\lfloor n/3 \rfloor+1}{n-\lfloor n/3 \rfloor}\frac{n-\lfloor n/3 \rfloor + 1}{n - 2 \lfloor n/3 \rfloor + 1}$$ But unfortunately, the inequality $$\frac{\lfloor n/3 \rfloor+1}{n-\lfloor n/3 \rfloor}\frac{n-\lfloor n/3 \rfloor + 1}{n - 2 \lfloor n/3 \rfloor + 1} \leq 1$$ does not hold for any multiples of $3$. Any other ideas?

$\endgroup$
  • $\begingroup$ Some of these may be of interest mathoverflow.net/q/17202/117945 $\endgroup$ – B. Mehta Apr 15 '18 at 20:44
  • $\begingroup$ Looks like the inequalities are true for $n = 10$. $\sum_{i=0}^{3}\binom{10}{i} = 176 < \binom{10}{4} = 210$ And $176 + 210 > \binom{10}{5} = 252$ $\endgroup$ – sku Apr 17 '18 at 7:13
  • 1
    $\begingroup$ @B. Mehta, Thanks for that, but most of those are upper bounds, and I believe I would need some good lower bounds too for answering this question. $\endgroup$ – Isaac Browne Jul 13 '18 at 15:00
1
$\begingroup$

It looks that the same was proven in the paper E.L.Johnson, D.Newman, K.Winston. An Inequality on Binomial Coefficients. Annals of Discrete Mathematics 2 (1978) 155-159. https://doi.org/10.1016/S0167-5060(08)70330-3 page 1 page 2 page 3 page 4 page 5

$\endgroup$
  • $\begingroup$ Thank you for the reference! However, I should probably say something: many stack exchange users may be unable to find full proof or even the ideas behind one given just this link (without paying money!). This is probably why you are getting downvotes. I suggest that in the spirit of stack exchange, you should edit this to include at least the gist of the argument. If you don't want to, thanks for the reference anyway and I'll try to write up the solution! $\endgroup$ – Isaac Browne Sep 10 at 4:35
2
$\begingroup$

This is partially a comment that is slightly too long. In the Math Overflow article, we want to bound

$$ {{N \choose k} + {N \choose k-1} + {N \choose k-2}+\dots \over {N \choose k}} = {1 + {k \over N-k+1} + {k(k-1) \over (N-k+1)(N-k+2)} + \cdots} $$

The author chooses to use a geometric series as an upper bound starting with the first term. However, we can slightly delay the geometric series to get a smaller upper bound as follows:

$$ 1 + {k \over N-k+1} + {k(k-1) \over (N-k+1)(N-k+2)} + \cdots = \\1 + \frac{k}{N-k+1} \left(1 + \frac{k-1}{N-k+2} + \frac{(k-1)(k-2)}{N-k+2(N-k+3)} \right) + \cdots$$ Using a geometric series for an upper bound in the inner parenthesis gives us an upper bound of $$ \dbinom{N}{k} \left(1 + \frac{k}{N-k+1} \cdot \frac{N-k+2}{N-2k+3} \right). $$ We can easily check that for large enough $N$, $$1 + \frac{k}{N-k+1} \cdot \frac{N-k+2}{N-2k+3} < \frac{N-(k-1)}{N-(2k-1)}. $$ Finally we can check that the steps used by the OP in the 2nd attempt portion of the question does go through if $N = 3k$ (which was an issue last time) for large enough $N$. This is just some algebraic manipulations so I won't post it here. Hopefully I haven't made an error.

$\endgroup$
  • $\begingroup$ Awesome, I didn't realize changing the bound so slightly would work! Now we just have to work on that lower bound... $\endgroup$ – Isaac Browne Sep 27 '18 at 14:19

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.