# How prove this inequality $\sum_{k=1}^{n}\frac{2k-1}{k\binom{n}{k}}\ge \frac{n}{2^{n-1}}$

let $1\le k\le n,k,n\in N^{+}$, show that $$\sum_{k=1}^{n}\dfrac{2k-1}{k\binom{n}{k}}\ge \dfrac{n}{2^{n-1}}$$

I know this $$\sum_{k=1}^{n}(2k-1)=n^2$$ and $$\sum_{k=1}^{n}k\binom{n}{k}=n\cdot 2^{n-1}$$

I want Use Cauchy-Schwarz inequality . $$\left(\sum_{k=1}^{n}\dfrac{2k-1}{k\binom{n}{k}}\right)\left(\sum_{k=1}^{n}k\binom{n}{k}\right)\ge (\sum_{k=1}^{n}\sqrt{2k-1})^2$$ then $$\sum_{k=1}^{n}\dfrac{2k-1}{k\binom{n}{k}}\ge\dfrac{(\sum_{k=1}^{n}\sqrt{2k-1})^2}{n\cdot 2^{n-1}}$$ Now we must prove $$\sum_{k=1}^{n}\sqrt{2k-1}\ge n?$$ maybe can use integral inequality to prove it.

I can't prove this.Thank you

• Induction?${}{}$ – Zircht Apr 29 '14 at 1:53
• maybe can use integral to prove it – china math Apr 29 '14 at 2:08
• $\sqrt{2k-1}\geq 1$ for $k\geq 1$. – WimC Apr 29 '14 at 4:58

Another way would be to use Cauchy-Schwarz Inequality in a slightly different form, which gives:

$$\left(\sum_{k=1}^{n}\dfrac{2k-1}{k\binom{n}{k}}\right)\left(\sum_{k=1}^{n}(2k-1)k\binom{n}{k}\right)\ge \left(\sum_{k=1}^{n}(2k-1) \right)^2 = n^4$$

Also we have $$\sum_{k=1}^{n}(2k-1)k\binom{n}{k} = n^2 \cdot 2^{n-1}$$

which gives us the stronger inequality $$\sum_{k=1}^{n}\dfrac{2k-1}{k\binom{n}{k}}\ge \dfrac{n^2}{2^{n-1}}$$

First prove that: for $x≥0$ and $y≥0$, $(x+y)^{\frac{1}{2}}≤x^{\frac{1}{2}}+y^{\frac{1}{2}}$. Define $f(x)=(x+1)^{\frac{1}{2}}-x^{\frac{1}{2}}-1$. Note that $f'(x)<0$. Then for $x >0$, we have $f(x)<0$. Therefore $(x+1)^{\frac{1}{2}}<x^{\frac{1}{2}}+1$. Replace $x$ by $x/y$ we have, $(x+y)^{\frac{1}{2}}<x^{\frac{1}{2}}+y^{\frac{1}{2}}$. As the result holds for $x=y=0$, we have $(x+y)^{\frac{1}{2}}≤x^{\frac{1}{2}}+y^{\frac{1}{2}}$, for $x≥0$ and $y≥0$. For induction, $$(x_{1}+...+x_{n})^{\frac{1}{2}}≤x^{\frac{1}{2}}_{1}+...+x^{\frac{1}{2}}_{n}.$$ So, for $x_{k}={2k-1}$ we have, $\sum_{k=1}^{n}\sqrt{2k-1}≥\sqrt{\sum_{k=1}^{n}{2k-1}}=\sqrt{n^{2}}=n.$

• Nice! Thank you very much,+1 – china math Apr 29 '14 at 2:13
• You're welcome. – VJunior Apr 29 '14 at 2:14
• Isn't induction a much easier way? Each time you are adding more than 1 to the LHS – Calvin Lin Apr 29 '14 at 2:50
• I believe you want the substitution $x_k=2k-1$, as opposed to the root – Calvin Lin Apr 29 '14 at 2:54
• Yes, thanks! I edited. – VJunior Apr 29 '14 at 2:58

Another starting point is the inequality $\boxed{\binom{n}{k} \leq 2^n}$ This trivial starting point allows us to deduce that

$$\sum_{k=1}^n \binom{n}{k}^{-1} \geq \frac{n}{2^n}$$

If we plugged this into the original inequality we fall short of what we're trying to prove:

$$\sum_{k=1}^n \left( 1 - \frac{1}{2k}\right)\binom{n}{k}^{-1} \geq 2^{-n} \sum_{k=1}^n \left( 1 - \frac{1}{2k}\right) \geq \mathbf{\color{blue}{\frac{n - \tfrac{1}{2}\log n}{2^n}}}$$

Or we can try it the other way, but we still fall a little bit short.

$$\sum_{k=1}^n \left( 1 - \frac{1}{2k}\right)\binom{n}{k}^{-1} = \sum_{k=1}^n \left( k - \frac{1}{2}\right)\frac{1}{n}\binom{n-1}{k-1}^{-1} = \frac{1}{n 2^{n-1}}\sum_{k=1}^n \left( k - \frac{1}{2}\right) = \mathbf{\color{blue}{\frac{n- \frac{1}{n}}{ 2^n} }}$$

I hope improve $\frac{1}{2^n}\binom{n}{k} \leq 1$, perhaps by a constant that depends on $k$.

In fact, we can use the Arithmetic mean - Harmonic mean inequality - or possibly Jensen's inequality - to get:

$$\sum_{k=1}^n \left( 1 - \frac{1}{2k}\right)\binom{n}{k}^{-1} \geq \frac{n^2}{\sum_{k=1}^n \left( 1 - \frac{1}{2k}\right)^{-1}\binom{n}{k}} \geq \frac{n^2}{2 \sum_{k=1}^n \binom{n}{k}} > \mathbf{\frac{n^2}{2^{n+1}} }$$