4
$\begingroup$

Good day,

Can someone help me with giving hints for this problem:

Show that for $n \geq 2, n \in \mathbb{Z}$, $$\sum_{r = 1}^{n} r \sqrt{\binom{n}{r}} < \sqrt{2 ^ {n - 1} n ^ 3}$$

I tried $$\sum_{r = 1}^{n} r \sqrt{\binom{n}{r}} = \sum_{r = 1}^{n} \sqrt{r ^ 2\binom{n}{r}}$$

$$= \sqrt{n} \sum_{r = 1}^{n} \sqrt{r\binom{n - 1}{r - 1}}$$

So, we need to prove $$\sum_{r = 1}^{n} \sqrt{r\binom{n - 1}{r - 1}} < n \sqrt{2 ^ {n - 1}}$$

This reminds me of $$\sum_{r = 0}^{n} (r + 1) \binom{n}{r} = n 2 ^ {n - 1} + 2 ^ n = 2 ^ {n - 1}(n + 2)$$

but I can't see how to use it.

Also, the only complex math inequality I know is AM-GM, so it's quite possible that it is my theoretical knowledge that is lacking. So, if a well-known inequality is used, please also mention it.

Thanks

$\endgroup$

1 Answer 1

6
$\begingroup$

By Cauchy-Schwarz, \begin{align*} \sum_{r = 1}^{n} r \sqrt{\binom{n}{r}} &\le \left(\sum_{r = 1}^{n} r^2\right)^{1/2}\left(\sum_{r = 1}^{n} \binom{n}{r}\right)^{1/2} \\ &= \left((2^n-1)\left(\frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}\right)\right)^{1/2} \\ &< \left(2^{n-1}\cdot2\left(\frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}\right)\right)^{1/2} \end{align*} Then, verify $2\left(\frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6}\right) < n^3$ for $n \ge 4$ by induction while manually checking the $n=2, n=3$ cases.

$\endgroup$
3
  • $\begingroup$ Thank you for the answer. It seems that we can avoid proving the last inequality, if we apply Cauchy-Schwarz on $\sum_{r = 1}^{n} \sqrt{r\binom{n - 1}{r - 1}} < n \sqrt{2 ^ {n - 1}}$ $\endgroup$
    – MangoPizza
    Mar 30 at 4:40
  • $\begingroup$ $\sum_{r = 1}^{n} \sqrt{r\binom{n - 1}{r - 1}} \leq \sqrt{\sum_{r = 1}^{n} r} \sqrt{\sum_{r = 1}^{n} \binom{n - 1}{r - 1}} < \sqrt{n ^ 2} \sqrt{2 ^ {n - 1}}$ $\endgroup$
    – MangoPizza
    Mar 30 at 4:42
  • $\begingroup$ $\frac{n(n + 1)}{2} < n^2$ because $n > 1$ $\endgroup$
    – MangoPizza
    Mar 30 at 4:43

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.