# Prove that for any $n$, we have $\sum_{i=1}^n \frac{a_i}i \ge a_n$.

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

• Is $a_n$ nonnegative ? – HK Lee Oct 6 '14 at 11:02
• not necessarily – user152715 Oct 6 '14 at 11:04

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.