Given $ n \geq 3$, $ n$ is a integer. Prove that: \[ (2^n - 2) \cdot \sqrt{2i-1} \geq \left( \sum_{j=0}^{i-1}C_n^j + C_{n-1}^{i-1} \right) \cdot \sqrt{n}\] where if $ n$ is even, then $ \displaystyle 1 \leq i \leq \frac{n}{2}$; if $ n$ is odd, then $ \displaystyle 1 \leq i \leq \frac{n-1}{2}$.
Problem
Source: China TST 2002 Quiz
Tags: inequalities, inequalities unsolved
10.08.2010 14:18
who can solve it?
04.04.2016 23:10
Sorry, but what does $C_n^j$ and $C_{n-1}^{i-1}$ mean? Is it like $\binom{j}{n}$ or $\binom{n}{j}$?
04.04.2016 23:46
MathPanda1 wrote: Sorry, but what does $C_n^j$ and $C_{n-1}^{i-1}$ mean? Is it like $\binom{j}{n}$ or $\binom{n}{j}$? $C_n^j=\binom{n}{j}$ and $C_{n-1}^{i-1}=\binom{n-1}{n-i}$
19.12.2017 18:05
Note that for each positive integer $i$ that $2\leq i\leq \lfloor \frac{n}{2}\rfloor -1$, the inequality $\frac{\binom{n-1}{i-1} +\sum_{j=0}^{i-1}{\binom{n}{j}}}{\sqrt{2i-1}} \leq \frac{\binom{n-1}{i} +\sum_{j=0}^{i}{\binom{n}{j}}}{\sqrt{2i}}$ is equivalent to $$(\sqrt{2i+1}-\sqrt{2i-1} )\sum_{j=0}^{i-1}{\binom{n}{j}} \leq \sqrt{2i-1}\binom{n-1}{i} +\sqrt{2i-1}\binom{n}{i}-\sqrt{2i+1}\binom{n-1}{i-1}.$$We've $LHS\leq \frac{2}{\sqrt{2i+1}+\sqrt{2i-1}}\sum_{j=0}^{i-1}{\binom{n}{i}} \leq \frac{\sqrt{2i+1}}{2}\binom{n}{i}$. And $\sqrt{2i-1}\binom{n-1}{i} +\sqrt{2i-1}\binom{n}{i}-\sqrt{2i+1}\binom{n-1}{i-1} -\frac{\sqrt{2i+1}}{2}\binom{n}{i} =\frac{(n-1)!}{i!(n-i)!} \times \Big( (n-i)\sqrt{2i-1} +n(\sqrt{2i-1}-\frac{\sqrt{2i+1}}{2}) -i\sqrt{2i+1}\Big)$. The last term is non-negative since $2i(\sqrt{2i-1}+\sqrt{2i+1})\leq n(\sqrt{2i-1}+\sqrt{2i+1})\leq n(4\sqrt{2i-1}-\sqrt{2i+1}).$ (the last bound is equivalent to $3\sqrt{2i-1}\geq 2\sqrt{2i+1}$ which is true for all $i\geq 2$.) Hence the first inequality we stated is true. This reduce the problem to the case when $i\in \{ 1,\lfloor \frac{n}{2}\rfloor \}$, which is easy.