| | |
Can we argue with induction? ...especially since we must show a claim holds for an infinite collection of integers $n$? 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}$$