Proof by induction of a given inequality

Question

I am trying to solve the underneath problem. I managed to get the initial proof but to generalize on $n+1$ I failed.

Show that for any natural $n\geq 2 $ and any real $a_i$ we have : $$(\sum_{i=1}^n a_i)^2 \leq 2^{n-1}\sum_{i=1}^n a_i^2.$$

Thanks

Answer 1

For the inductive step you may apply the $n$-case inequality to $$a_1,a_2,\dots, a_{n-1},(a_n+a_{n+1}).$$ Hence $$(\sum_{i=1}^{n+1} a_i)^2=(\sum_{i=1}^{n-1} a_i+(a_n+a_{n+1}))^2 \leq 2^{n-1}\left(\sum_{i=1}^{n-1} a_i^2+(a_n+a_{n+1})^2\right).$$ So it remains to show that $$2^{n-1}\left(\sum_{i=1}^{n-1} a_i^2+(a_n+a_{n+1})^2\right)\leq 2^{n}\sum_{i=1}^{n+1} a_i^2$$ that is $$\sum_{i=1}^{n-1} a_i^2+(a_n+a_{n+1})^2\leq 2\sum_{i=1}^{n-1} a_i^2+2a_n^2+2a_{n+1}^2.$$ Can you take it from here?

Answer 2

Use the inequality $(a+b)^{2} \leq 2(a^{2}+b^{2})$. If $s_n= \sum\limits_{k=1}^{n} a_i$ then $(s_n+a_{n+1})^{2} \leq 2(s_n^{2}+a_{n+1}^{2}) \leq 2(2^{n}\sum\limits_{k=1}^{n} a_i^{2}+a_{n+1})^{2}$. Can you take over from here?

Answer 3

Without induction we have $$ 2^{n-1}\sum_{i=1}^na_i^2-(\sum_{i=1}^na_i)^2= $$ $$= 2^{n-1}\sum_{i=1}^na_i^2-\sum_{i=1}^na_i^2-\sum_{1\le i<j\le n}2a_ia_j=$$ $$= (2^{n-1}-n)\sum_{i=1}^na_i^2+(n-1)\sum_{i-1}^na_i^2-\sum_{1\le i<j\le n}2a_ia_j=$$ $$=(2^{n-1}-n)\sum_{i=1}^na_i^2\,+\sum_{1\le i<j\le n}(a_i-a_j)^2\ge 0$$ because $2^{n-1}- n\ge 0.$

Answer 4

I see 3 solutions of the above inequality:

$$(\sum_{i=1}^n a_i)^2 \leq 2^{n-1}\sum_{i=1}^n a_i^2.$$ Let me join the fun:

$$(\sum_{i=1}^n a_i)^2\ = \ \sum_{i=1}^n\,(a_i\cdot\sum_{j=1}^n a_j)\ \le \ \frac 12\cdot \sum_{i=1}^n\,(n\!\cdot\! a_i^2+\sum_{j=1}^n a_j^2) \ =\ n\cdot\sum_{k=1}^n a_k^2 $$ i.e. $$(\sum_{i=1}^n a_i)^2\ \le\ n\cdot\sum_{i=1}^n a_i^2 $$

which is clearly much better than our original OP's goal -- indeed, $\ \forall_{n=1}^\infty\, n\le 2^{n-1}.$