$ \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

Question

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.

Answer 1

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$.

Answer 2

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$$