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

  • 1
    $\begingroup$ Induction?${}{}$ $\endgroup$ – Zircht Apr 29 '14 at 1:53
  • $\begingroup$ maybe can use integral to prove it $\endgroup$ – china math Apr 29 '14 at 2:08
  • 1
    $\begingroup$ $\sqrt{2k-1}\geq 1$ for $k\geq 1$. $\endgroup$ – 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.$

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


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.