Consider the sequence $(a_n)_{n \ge1}$ of real nos such that $$a_{m+n}\le a_m+a_n,\ \forall m,n \ge 1$$
Prove that for any $n$, we have $$\sum_{i=1}^n \frac{a_i}i \ge a_n .$$
7
$\begingroup$
$\endgroup$
-
$\begingroup$ Is $a_n$ nonnegative ? $\endgroup$ – HK Lee Oct 6 '14 at 11:02
-
$\begingroup$ not necessarily $\endgroup$ – user152715 Oct 6 '14 at 11:04
2
$\begingroup$
$\endgroup$
This is Problem 2 from the Asian Pacific Mathematical Olympiad (APMO) 1999. I took the following proof essentially from AoPS:
We will prove this by strong induction. Note that the inequality holds for $ n=1$. Assume that the inequality holds for $ n=1,2,\ldots,k$, that is, $$ a_1\ge a_1,\quad a_1+\frac{a_2}{2}\ge a_2,\quad a_1+\frac{a_2}2+\frac{a_3}3\ge a_3,\quad \dotsc,\quad a_1+\frac{a_2}3+\frac{a_3}3+\cdots+\frac{a_k}k\ge a_k. $$ Sum them up: $$ ka_1+(k-1)\frac{a_2}2a_2+\cdots+\frac{a_k}{k}\ge a_1+a_2+\cdots+a_k.$$ Add $ a_1+\ldots+a_k$ to both sides: $$ (k+1)\left(a_1+\frac{a_2}2+\cdots+\frac{a_k}k\right)\ge (a_1+a_k)+(a_2+a_{k-1})+\cdots+(a_k+a_1)\ge ka_{k+1}.$$ Divide both sides by $ k+1$: $$ a_1+\frac{a_2}2+\cdots+\frac{a_k}k\ge\frac{ka_{k+1}}{k+1},$$ i.e. $$a_1 + \frac{a_2}{2} + \frac{a_3}{3} + \cdots + \frac{a_{k+1}}{k+1} \geq a_{k+1}$$ which proves the induction step.
