3
$\begingroup$

I want to show that $\left(\sqrt{\binom{n}{1}}+\sqrt{\binom{n}{2}}+...+\sqrt{\binom{n}{n}}\right)^2≤n(2^n-1)$.

My attempt: We know that $\sqrt{ab}≤\frac{a+b}{2}$ because $(\sqrt{a}-\sqrt{b})^2≥0$ and that $\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{n}=2^n$ by expanding $(1+x)^n$ and substituting $x=1$.

Next, I re-wrote $\left(\sqrt{\binom{n}{1}}+\sqrt{\binom{n}{2}}+...+\sqrt{\binom{n}{n}}\right)^2$ as $\binom{n}{1}+\binom{n}{2}+...+\binom{n}{1}+\sum_{0<i<j}\sqrt{\binom{n}{i}\binom{n}{j}}$

$≤2^n-1+\sum_{0<i<j}\frac{\binom{n}{i}+\binom{n}{j}}{2}$ using the two term $A_m G_m$ inequality.

$=2^n-1+\frac{1}{2}\left(\binom{n}{1}+\binom{n}{2}+\binom{n}{1}+\binom{n}{3}+...+\binom{n}{1}+\binom{n}{n}+\binom{n}{2}+\binom{n}{3}+\binom{n}{2}+\binom{n}{4}+...+\binom{n}{n-1}+\binom{n}{n}\right)$

$=2^n-1+\frac{n}{2}\left(\binom{n}{1}+\binom{n}{2}+\binom{n}{3}+...+\binom{n}{n}\right)$

$=2^n-1+\frac{n}{2}(2^n-1)$

$=\frac{n+2}{2}(2^n-1)$, which is clearly not the result.

Could someone point out the mistake in my working and help me finish the proof?

$\endgroup$
0

2 Answers 2

7
$\begingroup$

Hint: Use the CS inequality: $(1\cdot x_1+1\cdot x_2+\cdots+1\cdot x_n)^2 \le (1+1+\cdots+1)(x_1^2+x_2^2+\cdots+x_n^2)$, with $x_k = \sqrt{\binom{n}{k}}$

$\endgroup$
1
  • $\begingroup$ Seems more like a solution than a hint to me. If you want to phrase it as a hint (which I'm generally in favor of), maybe hide the inequality? $\endgroup$
    – Calvin Lin
    Feb 22, 2022 at 14:08
4
$\begingroup$

There is an error in your calculation. You should have $$ \left(\sqrt{\binom{n}{1}}+\sqrt{\binom{n}{2}}+...+\sqrt{\binom{n}{n}}\right)^2 = \sum_{i=1}^n \binom ni + 2 \sum_{0<i<j}\sqrt{\binom{n}{i}\binom{n}{j}} \\ \le \sum_{i=1}^n \binom ni + \sum_{0<i<j} \left(\binom{n}{i} + \binom{n}{j}\right)\, , $$ note the factor $2$ which is missing in your equation. The right-hand side is equal to $$ \frac 12 \sum_{i=1}^n\sum_{j=1}^n \left(\binom{n}{i} + \binom{n}{j}\right) = n \sum_{i=1}^n \binom{n}{i} = n (2^n-1) \, . $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .