Let $a_1, a_2, \ldots$ be a sequence of real numbers satisfying $a_{i+j} \le a_i + a_j$ for all positive integers $i$ and $j$. Prove:

$$a_n \le a_1 + \frac{a_2}{2} + \frac{a_3}{3} + \cdots + \frac{a_n}{n}$$__Can we argue with induction?__ Note, strong induction allows us to assume more...

Let us argue by strong induction...

Clearly, the inequality holds for $n=1$

We need to show that if it holds for $n = 1, 2, 3, \ldots, k$, then it must also hold for $n=k+1$

__What can we determine immediately?__ In particular, what can we conclude from the given nature of the sequence $\{a_n\}$?

Starting with the given fact that $a_{i+j} \le a_i + a_j$ for all positive integers $i$ and $j$, and the corresponding implications for $a_{k+1}$, we notice

$$\begin{array}{rcl} a_{k+1} &\le& a_1 + a_k\\ a_{k+1} &\le& a_2 + a_{k-1}\\ a_{k+1} &\le& a_3 + a_{k-2}\\ &\vdots&\\ a_{k+1} &\le& a_k + a_1 \end{array}$$Adding these together we find

$$ka_{k+1} \le 2(a_1 + a_2 + a_3 + \cdots + a_k)$$__How can we use the inductive hypothesis?__ Can we relate it to the inequality above, for example...

Now, turning our attention to the inductive hypothesis, we know that:

$$\begin{array}{rcl} a_1 &\le& a_1\\\\ a_2 &\le& a_1 + \frac{a_2}{2}\\\\ a_3 &\le& a_1 + \frac{a_2}{2} + \frac{a_3}{3}\\\\ &\vdots&\\\\ a_k &\le& a_1 + \frac{a_2}{2} + \frac{a_3}{3} + \cdots + \frac{a_k}{k} \end{array}$$Adding these together, we can get an inequality that also involves the expression $a_1 + a_2 + a_3 + \cdots + a_k$.

$$a_1 + a_2 + a_3 + \cdots + a_k \le ka_1 + (k-1) \frac{a_2}{2} + (k-2) \frac{a_3}{3} + \cdots + \frac{a_k}{k} $$__Can we insert what we would like to see, and then compensate for that insertion?__ The other inequality involved twice the sum...

Rather than simply doubling both sides to achieve linkage with the earlier inequality deduced, we instead add $a_1 + a_2 + \cdots + a_k$ to both sides to the same end. This has the advantage that, upon collecting like terms on the right, the right side starts to look more recognizable...

$$ 2(a_1 + a_2 + a_3 + \cdots + a_k) \le (k+1) \left( a_1 + \frac{a_2}{2} + \cdots + \frac{a_k}{k} \right)$$__How might we combine what we know?__ (i.e., the two inequalities)

Combining our two results above, we have

$$ka_{k+1} \le (k+1) \left( a_1 + \frac{a_2}{2} + \cdots + \frac{a_k}{k} \right)$$__Can we insert what we want and compensate for the insertion?__ We seem to be missing the $\frac{a_{k+1}}{k+1}$ term...

Recalling that the inequality we are trying to prove has an additional $\frac{a_{k+1}}{k+1}$ term, we add $a_{k+1}$ to both sides. It follows that

$$ (k+1) a_{k+1} \le (k+1) \left( a_1 + \frac{a_2}{2} + \cdots + \frac{a_k}{k} + \frac{a_{k+1}}{k+1} \right)$$__Can we simplify things?__ We have a common (positive) factor on both sides...

Finally, dividing by $(k+1)$ above yields the desired result

$$a_{k+1} \le a_1 + \frac{a_2}{2} + \cdots + \frac{a_k}{k} + \frac{a_{k+1}}{k+1}$$