Can't get the hang of an induction proof.

Question

$$\left (\sum_{i=1}^n x_{i}\right )^2 ≤ n\times \sum_{i=1}^n x_{i}^2$$ x(i) R, $i>0$

I've tried to put it like this:

$n+1$:

$$((\sum_{i=1}^n x_{i}) + x_{n+1})^2 ≤ (n+1)\times ((\sum_{i=1}^n x_{i}^2) +x_{n+1}^2)$$

$$(\sum_{i=1}^n x_{i})^2 + 2\times (\sum_{i=1}^n x_{i})\times x_{n+1} + x_{n+1}^2 ≤ n\times (\sum_{i=1}^n x_{i}^2) + 2\times (\sum_{i=1}^n x_{i})\times x_{n+1} + x_{n+1}^2$$

$$n\times (\sum_{i=1}^n x_{i}^2) + 2\times (\sum_{i=1}^n x_{i})\times x_{n+1} + x_{n+1}^2 ≤ (n+1)\times ((\sum_{i=1}^n x_{i}^2) +x_{n+1}^2)$$

And got stuck here: $$2\times (\sum_{i=1}^n x_{i})\times x_{n+1} ≤ (n\times \sum_{i=1}^n x_{i}^2) + n\times x_{n+1}$$

So I've been wondering whether someone here could please help me understand how to handle it.

Answer 1

From your second line we can go on $$ \left(\sum_{i=1}^n x_{i}\right)^2 + 2\times \left(\sum_{i=1}^n x_{i}\right)\times x_{n+1} + x_{n+1}^2 ≤ n\times \left(\sum_{i=1}^n x_{i}^2\right) + 2\times \left(\sum_{i=1}^n x_{i}\right)\times x_{n+1} + x_{n+1}^2$$

We can just subtract equal terms on both sides

$$\left(\sum_{i=1}^n x_{i}\right)^2 ≤ n\times \sum_{i=1}^n x_{i}^2 $$

Dividing the inequality by n

$$\frac1n\cdot \sum_{i=1}^n x_{i} \cdot \sum_{i=1}^n x_{i} ≤ \sum_{i=1}^n x_{i}^2 $$

Dividing the inequality by n again

$$\frac1n\cdot \sum_{i=1}^n x_{i} \cdot \frac1n\cdot \sum_{i=1}^n x_{i} ≤ \frac1n\cdot\sum_{i=1}^n x_{i}^2 $$

$$\left(\frac1n\cdot \sum_{i=1}^n x_{i} \right)^2 ≤ \frac1n\cdot\sum_{i=1}^n x_{i}^2 $$

$$ 0≤ \frac1n\cdot\sum_{i=1}^n x_{i}^2 -\left(\frac1n\cdot \sum_{i=1}^n x_{i} \right)^2$$

At the RHS we have the definition of the variance

$$ 0≤ \frac1n\cdot\sum_{i=1}^n \left(x_{i} -\overline x \right)^2$$

Every summmand at the RHS is greater/equal $0$, the inequality holds and therefore proposition for $n$ is true.

Answer 2

Here's another induction approach where we relate $(\sum_{i=1}^{n+1} x_i)^2$ to the square of the sum of $n$ terms, chosen suitably.

Observe that

1. $(\sum_{i=1}^{n+1} x_i)^2 = (\sum_{i=1}^{n+1} x_i^2) + 2 (\sum_{ 1 \leq i < j \leq n+1} x_i x_j) $ by expanding terms.
2. $ \sum_{i=1}^{n+1} ( \sum_{j\neq i} x_j ) ^2 = n (\sum_{i=1}^{n+1} x_i^2) + 2(n-1) (\sum_{ 1 \leq i < j \leq n+1} x_i x_j)$ by expanding terms
3. $ \sum_{i=1}^{n+1} ( \sum_{j\neq i} x_j ) ^2 \leq n^2 (\sum_{i=1}^{n+1} x_i^2) $ by the induction hypothesis on the $n+1$ expressions that are each the square of the sum of $n$ terms.
4. $(n-1) (\sum_{i=1}^{n+1} x_i)^2 + (\sum_{i=1}^{n+1} x_i^2) = n (\sum_{i=1}^{n+1} x_i^2) + 2(n-1) (\sum_{ 1 \leq i < j \leq n+1} x_i x_j) \leq n^2 (\sum_{i=1}^{n+1} x_i^2)$ by combining the above.
5. Thus $(\sum_{i=1}^{n+1} x_i)^2 \leq (n+1) (\sum_{i=1}^{n+1} x_i^2)$ by shifting terms and dividing by $n-1$.

---

Your induction approach views $(\sum_{i=1}^{n+1} x_i)^2$ as $(x_{n+1} + \sum_{i=1}^{n} x_i)^2$ and expands it. You then have to recognize the sum of squares, but I (personally) might argue that if someone recognizes it, they might as well do it directly (IE $\sum_{i\neq j}(x_i - x_j)^2 \geq 0$) without having to use induction.