7
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.