Induction proof: $\sqrt{\sum_{i=1}^na_i^2}\leq\sum_{i=1}^n\sqrt{a_i^2}$

Question

I would like to show that $\sqrt{\sum_{i=1}^na_i^2}\leq\sum_{i=1}^n\sqrt{a_i^2}$ $(^*)$ for each $n\in\mathbb N$. It is easy to show that $\sqrt{a^2+b^2}\leq\sqrt{a^2}+\sqrt{b^2}$, so for $n=2$ the statement holds. Let's assume $(^*)$ holds for some $n\in\mathbb N$. I need to show that $$ \sqrt{\sum_{i=1}^{n+1}a_i^2}\leq\sum_{i=1}^n\sqrt{a_i^2}+\sqrt{a_{n+1}^2}. $$ Is there a way for me to say $\sqrt{\sum_{i=1}^{n+1}a_i^2}$ is smaller than or equal to $\sqrt{\sum_{i=1}^na_i^2}$ + something else?

Answer 1

Hint: $$\textstyle \sqrt{\sum_{i=1}^{n+1}a_i^2} = \sqrt{\left(\sum_{i=1}^{n}a_i^2\right) + a_{n+1}^2} = \sqrt{\left({\sqrt{\sum_{i=1}^na_i^2}}\right)^2 + a_{n+1}^2} $$ and your formula $\sqrt{a^2 + b^2} \leq \sqrt{a^2} + \sqrt{b^2}$ should apply here.

Answer 2

Hi cutie note that$\sqrt{\sum_{i=1}^{n}a_{i}^{2}} \leq \sum_{i=1}^{n}|a_{i}|$ iff $\sum_{i=1}^{n}a_{i}^{2} \leq (\sum_{i=1}^{n}|a_{i}|)^{2}$. So if some integer $n \geq 2$ is such that this is true, then $$ \sum_{i=1}^{n+1}a_{i}^{2} \leq (\sum_{i=1}^{n}|a_{i}|)^{2} + a_{n+1}^{2} \leq (\sum_{i=1}^{n+1}|a_{i}|)^{2} $$ by the fact that all terms involved are $\geq 0$.

Answer 3

This comes from triangular inequality like the one verified by norms, no surprise about this because on lhs of your question you get $||\cdot||_2$ while on rhs you get $||\cdot||_1$.

The inequality we'll use is :

$\sqrt{a+b}\le \sqrt {\vphantom{b}a}+\sqrt b\tag{E}$

It can easily be showed from $a,b\ge 0,\quad (\sqrt{\vphantom{b}a}+\sqrt b)^2=a+b+2\sqrt{ab}\ge a+b$ and the result comes from taking the square root of that.

The inequality is passing through sums with more terms than just two by simple induction, for instance for any such $f$ :

$f(x_1+x_2+...+x_{n+1})=f((x_1+x_2+...+x_n)+x_{n+1})\le f(x_1+x_2+...+x_n)+f(x_{n+1})$

Written with sum symbols this means $f(\sum\limits_{i=1}^{n+1}x_i)\le f(\sum\limits_{i=1}^{n}x_i)+f(x_n)\le...\le\sum\limits_{i=1}^{n+1}f(x_i)$.

Here it is just an application with $f=\sqrt{\cdot}$ and $x_i=a_i^2$.

Note: note that we have always $(a_i)^2\ge 0$ or any sum of them, thus we can apply $(E)$.