Select Page

Try this problem from ISI-MSQMS 2018 which involves the concept of Inequality and Combinatorics.

INEQUALITY | ISI 2018 | MSQMS | PART B | PROBLEM 4

Show that $\sqrt{C_{1}}+\sqrt{C_{2}}+\sqrt{C_{3}}+\ldots+\sqrt{C_{n}} \leq 2^{n-1}+\frac{n-1}{2}$ where
$C_k={n\choose k}$

INEQUALITIES

COMBINATORICS

Try with Hints

First hint

Use Cauchy Schwarz Inequality $\left(\displaystyle\sum_{i} a_{i} b_{i}\right)^{2} \leq\left(\displaystyle\sum_{i} a_{i}^{2}\right)\left(\displaystyle\sum_{i} b_{i}^{2}\right)$

Second hint

Apply Cauchy Schwarz Inquality in two sets of real numbers ($\sqrt C_1$,$\sqrt C_2$,…..,$\sqrt C_n$)and ($1$,$1$,$1$,……$1$)

($C_1+C_2+$……..$+C_n$)($1+1+$……$+1$) $\geq$ ($\sqrt C_1+\sqrt C_2+………+\sqrt C_n$)

($2^n-1$)$n \geq$ ($\sqrt C_1+\sqrt C_2+$……….$+\sqrt C_n$)$^2$

$\sqrt C_1+\sqrt C_2+$……….$+\sqrt C_n \leq \sqrt n\sqrt (2^n-1)$

The proof is still not done,why don’t you try the remaining part yourself?

Third hint

We know AM $\geq$ GM

i.e

For $n$ positive quantities $a_{1}, a_{2}, \dots, a_{n}$
$$\frac{a_{1}+a_{2}+\ldots+a_{n}}{n} \geq \sqrt[n]{a_{1} a_{2} \cdot \cdot a_{n}}$$
with equality if and only if $a_{1}=a_{2}=\ldots=a_{n}$

Now you have all the ingredients,why don’t you cook it yourself? I firmly believe that you can cook a food tastier than mine.

Final Step

$\frac{n+2^n-1}{2} \geq \sqrt n\sqrt {2^n-1}$

Thus,$\sqrt C_1+\sqrt C_2+$……..$+\sqrt C_n \leq \frac {n+2^n-1}{2}$