Show: $\left(\sum_{k=0}^n a_k\right)^2\leqslant (n+1)\sum_{k=0}^n a_k^2$

Question

Show: $\left(\sum_{k=0}^n a_k\right)^2\leqslant (n+1)\sum_{k=0}^n a_k^2$ for $n\geqslant 0$ and $a_k\in\mathbb{Z}_{\geq 0}$.

Wanted to show this by induction:

1. $n=0: a_0^2\leqslant a_0^2$

2. Assume it is shown for $n$, now show for $n+1$.

$$ \left(\sum_{k=0}^{n+1}a_k\right)^2=\left(\sum_{k=0}^n a_k+a_{n+1}\right)^2=\left(\sum_{k=0}^n a_k\right)^2+2a_{n+1}\sum_{k=0}^n a_k+a_{n+1}^2\\ \leq (n+1)\sum_{k=0}^n a_k^2+2a_{n+1}\sum_{k=0}^n a_k+a_{n+1}^2\\ \leq(n+1)\sum_{k=0}^na_k^2+(n+1)a_{n+1}^2+2a_{n+1}\sum_{k=0}^n a_k\\ =(n+1)\sum_{k=0}^{n+1}a_k^2+2a_{n+1}\sum_{k=0}^n a_k\\ \leq (n+2)\sum_{k=0}^{n+1}a_k^2+2a_{n+1}\sum_{k=0}^n a_k $$

This is by the assumption.

Now how to continue?

Answer 1

Hint:

AM-GM inequallity give us \begin{align*} a_k(a_0+a_1+\ldots+a_k+\ldots+a_n)&=\sum_{j=0}^na_ka_j\\ &\leq \sum_{j=0}^n\frac{1}{2}(a_k^2+a_j^2) \end{align*}

From this inequallity it follows $$a_k(a_0+a_1+\ldots+a_n)\leq\frac{n+1}{2}a_k^2+\frac{1}{2}\sum_{j=0}^na_j^2$$ Since $\displaystyle{\left(\sum_{k=0}^na_k\right)^2=\sum_{k=0}^{n}\left[a_k(a_0+a_1+...+a_n)\right]}$, we have $$\displaystyle{\left(\sum_{k=0}^na_k\right)^2}\leq\frac{n+1}{2}\left(a_0^2+{a_1}^2+\ldots+a_n^2\right)+\frac{n+1}{2}\sum_{j=0}^na_j^2=(n+1)\sum_{j=0}^na_j^2$$

Answer 2

Recall the variance formula from statistics:

$$\sum(x_i-\bar x)^2=\sum x_i^2-2\sum x_i\bar x+\sum \bar x^2=\sum x_i^2-2\bar x\sum x_i+n\bar x^2=\sum x^2-n\bar x^2\ge0,$$

where $$\bar x=\frac1n\sum x_i$$

Answer 3

You was close.

$$ (n+1)\sum_{k=0}^n a_k^2+2a_{n+1}\sum_{k=0}^n a_k+a_{n+1}^2 = \\ = (n+2)\sum_{k=0}^{n+1}a_k^2-\sum_{k=0}^n \left(a_k^2 -2a_ka_{n+1} +a_{n+1}^2\right) - a_{n+1}^2 = \\ = (n+2)\sum_{k=0}^{n+1}a_k^2-\sum_{k=0}^n \left(a_k-a_{n+1}\right)^2 - a_{n+1}^2 \leq\\ \leq (n+2)\sum_{k=0}^{n+1}a_k^2 $$