$ \sum_{1 \le i < j \le n} a_{i} a_{j} \ge n(n-1)/2 $ , prove that $a_{1} + ... + a_{n} \ge n$ for $n \ge 2$ using AM-QM Let $a_{1}, a_{2}, ...$ be a sequence of positive real numbers. Let the following relation holds:
$$ a_{k+1} \ge \frac{k a_{k}}{a_{k}^{2} + (k-1)}, \:\: k \ge 1$$
Prove that $ S_{n} = a_{1} + a_{2} + ... + a_{n} \ge n $, for $n \ge 2$.

Solution:
I have posted this question before and solved it using 2 approaches, (Given $ a_{k+1} \ge \frac{k a_{k}}{(a_{k}^{2} + k-1)}, \:\: k > 0$, prove $ S_{n} = a_{1} + .. + a_{n} \ge n, \:\: n \ge 2 $).
this time I would like to solve it using another approach, the hint is that $ \sum_{1 \le i < j \le n} a_{i} a_{j} \ge n(n-1)/2 $ and then use AM-QM inequality. Here is my attempt:
$$ \sum_{1 \le i < j \le n} a_{i} a_{j} =  \sum_{j=2} S_{j-1} a_{j} $$
by using a result in my previous post that $S_{m} \ge m/a_{m+1}$ we have
$$ \sum_{1 \le i < j \le n} a_{i} a_{j} =  \sum_{j=2}^{n} S_{j-1} a_{j} \ge \sum_{j=2}^{n} (j-1) = n(n-1)/2 $$
the hint is proved, then:
$$ \sum_{j=2}^{n} S_{j-1} a_{j} \le S_{n-1} \sum_{j=2}^{n}  a_{j} $$
then by AM-QM:
$$S_{n-1} \sum_{j=2}^{n}  a_{j} \le S_{n-1} \sqrt{n \sum_{i=2}^{n} a_{i}^{2}} \le S_{n-1} \sqrt{n} \sqrt{(S_{n}^{2})} = \sqrt{n} S_{n-1} S_{n}$$
so $$ \sqrt{n} S_{n-1} S_{n} \ge n(n-1)/2$$
if we use induction, by assuming $S_{n-1} \ge n-1$ then we can have
$$ S_{n} \ge \sqrt{n}/2$$
This is as far as i have gone.
 A: Since
$$(a_1+a_2+\cdots +a_n)^2=(a_1^2+a_2^2+\cdots +a_n^2)+2\sum_{1 \le i < j \le n} a_{i} a_{j}$$
we can write
$$\sum_{1 \le i < j \le n} a_{i} a_{j}=\frac{S_n^2-(a_1^2+a_2^2+\cdots +a_n^2)}{2}$$
So, the hint $$ \sum_{1 \le i < j \le n} a_{i} a_{j} \ge \frac{n(n-1)}{2} $$
is equivalent to
$$\frac{S_n^2-(a_1^2+a_2^2+\cdots +a_n^2)}{2}\ge \frac{n(n-1)}{2},$$
i.e.
$$a_1^2+a_2^2+\cdots +a_n^2\le S_n^2-n(n-1)\tag1$$
By AM-QM inequality, we get
$$\frac{a_1^2+a_2^2+\cdots +a_n^2}{n}\ge \left(\frac{a_1+a_2+\cdots +a_n}{n}\right)^2,$$
i.e.
$$a_1^2+a_2^2+\cdots +a_n^2\ge \frac{S_n^2}{n}\tag2$$
It follows from $(1)(2)$ that
$$\frac{S_n^2}{n}\le S_n^2-n(n-1)$$
from which
$$S_n\ge  n$$
follows for $n\ge 2$.
A: Sum up $a_i^2+a_j^2 \geq 2a_i a_j$ for all pairs ($i,j$). You'll get,
$$(n-1)\sum_ia_i^2 \geq 2\sum_{i<j}a_ia_j$$
Implying that,
$$\left(\sum_i a_i\right)^2 = \sum_i a_i^2 + 2\sum_{i<j}a_ia_j \geq \left(2+\frac{2}{n-1}\right)\sum_{i<j}a_ia_j=\frac{2n}{n-1}\sum_{i<j}a_ia_j\geq n^2$$
$$\implies \sum_ia_i \geq n$$
