Induction Problem from Putnam and Beyond

Question

I have copied the first step of the solution below in order to save time and space, the problem, with full solution, can be found in the book Putnam and Beyond.

Question: Let $a_1, a_2, \ldots, a_n, \ldots$ be a sequence of distinct positive integers. Prove that for any positive integer $n$,

$$a_1^2 + a_2^2 + \cdots + a_n^2 \ge \tfrac{2n + 1}{3}(a_1 + a_2 + \cdots + a_n).$$

Solution: $$a_{n+1}^2 \ge \tfrac{2n + 3}{3}a_{n+1} + \tfrac{2}{3}(a_1 + a_2 + \cdots + a_n) \ldots$$

Note: I understand how to make the jump from the question to the inductive step, namely replacing $n$ with $n+1$, but I don't see where the term $\tfrac{2}{3}(a_1 + a_2 + \cdots + a_n)$ came from in the solution. Any help would be appreciated.

Answer 1

The $\frac23(a_1 + a_2 + \dots + a_n)$ term appears because the coefficient of those terms increases from $\frac{2n+1}{3}$ to $\frac{2(n+1)+1}{3} = \frac{2n+1}{3} + \frac23$.

For example, to go from $n=2$ to $n=3$ in the inductive step, we assume that the inequality $$a_1^2 + a_2^2 \ge \frac53(a_1 + a_2)$$ holds, and want to prove the inequality $$a_1^2 + a_2^2 + a_3^2 \ge \frac73(a_1 + a_2 + a_3).$$ Take the difference and you see that it's enough to prove that $$a_3^2 \ge \frac23 (a_1 + a_2) + \frac73 a_3.$$

Answer 2

An inductive approach would use $$a_1{}^2 + \dots + a_n{}^2 \ge \frac{2n + 1}3\bigg(a_1 + \dots + a_n\bigg)$$ to establish $$a_1{}^2 + \dots + a_n{}^2 + a_{n+1}{}^2\ge \frac{2(n+1) + 1}3\bigg(a_1 + \dots + a_n + a_{n+1}\bigg)$$

by using transitivity of $x \ge y \text{ and } y \ge z \text{ implies } x \ge z$. So $x,y,z$ must be figured out. We can choose $x$ and $y$ as:

$$x = a_1{}^2 + \dots + a_n{}^2$$ $$y = \frac{2n+1}{3}\bigg(a_1 + \dots a_n\bigg)$$

but then to figure out what $z$ has to be, we have to choose $z$ to make the last equation $x \ge z$ :

$$z = \frac{2(n+1) + 1}3\bigg(a_1 + \dots + a_n + a_{n+1}\bigg) - a_{n+1}{}^2$$

So we are given $x \ge z$ by inductive hypothesis, we know the goal is $x \ge z$, we need to establish now $y \ge z$:

$$\frac{2n+1}{3}\bigg(a_1 + \dots a_n\bigg) \ge \frac{2(n+1) + 1}3\bigg(a_1 + \dots + a_n + a_{n+1}\bigg) - a_{n+1}{}^2$$

which is

$$a_{n+1}{}^2 \ge \bigg(\frac{2n + 1}3 + \frac{2}{3}\bigg)\bigg(a_1 + \dots + a_n + a_{n+1}\bigg) - \frac{2n+1}{3}\bigg(a_1 + \dots a_n\bigg)$$

which is

$$a_{n+1}{}^2 \ge \frac{2n + 1}3 a_{n+1} + \frac{2}{3}\bigg(a_1 + \dots + a_n + a_{n+1}\bigg) $$