The following (folklore) proof is probably the shortest. Consider the quadratic function

in the variable \(x\). We may assume \(a \neq 0\). If \(b = \lambda a\), then clearly

If, on the other hand, \(a\) and \(b\) are linearly independent, then \(|x a + b|^2 {\gt} 0\) for all \(x\), and thus the discriminant \(\langle a, b \rangle ^2 - |a|^2 |b|^2\) is less than 0.

The following beautiful nonstandard induction proof is attributed to Cauchy. Let \(P(n)\) be the statement of the second inequality, written in the form

For \(n=2\), we have \(a_1 a_2 \le \left(\frac{a_1+a_2}{2}\right)^2 \iff (a_1-a_2)^2 \ge 0\), which is true. Now we proceed in the following two steps:

1. \(P(n) \implies P(n-1)\)

2. \(P(n)\) and \(P(2) \implies P(2n)\)

which will clearly imply the full result.

To prove (A), set \(A := \frac{\sum _{k=1}^{n-1} a_k}{n-1}\), then

and hence \(\prod _{k=1}^{n-1} a_k \le A^{n-1}\).

For (B), we see

The condition for equality is derived just as easily.

The left-hand inequality, between the harmonic and the geometric mean, follows now by considering \(\frac{1}{a_1}, \dots , \frac{1}{a_n}\).

Of the many other proofs of the arithmetic-geometric mean inequality, let us single out a particularly striking one by Horst Alzer, with some shortenings due to France Dacar. As a matter of fact, this proof yields the stronger inequality

for any positive numbers \(a_1, \dots , a_n\), \(p_1, \dots , p_n\) with \(\sum _{i=1}^n p_i = 1\). Let us denote the expression on the left side by \(G\), and on the right side by \(A\). Fix \(c {\gt} 0\) and define the function \(f(t) := \frac{1}{c} - \frac{1}{t}\) on \(\mathbb {R}_{{\gt}0}\). Since \(f(t) {\lt} 0\) for \(t {\lt} c\) and \(f(t) {\gt} 0\) for \(t {\gt} c\), we get the inequality

for every \(x {\gt} 0\), with equality if and only if \(x = c\). Now

and setting \(c = G\) and \(x = a_i\) we conclude that

Multiplying this inequality by \(p_i\) and summing over all \(i\) gives

With \(\sum p_i = 1\), the left side equals \(\frac{A}{G} - 1\), while the right side is \(\log \left(\prod a_i^{p_i}\right) - \log G = \log G - \log G = 0\). We conclude \(\frac{A}{G} - 1 \ge 0\), which is \(A \ge G\). In the case of equality, all inequalities must be equalities, which implies \(a_1 = \cdots = a_n = G\).

There is another nice proof, due to Michael D. Hirschhorn. It uses Bernoulli’s inequality, which says

Suppose \(a_1, a_2, \dots , a_{n+1} {\gt} 0\) and set

By Bernoulli,

which translates into

and the arithmetic-geometric mean inequality follows by induction.

Let \(y\) be one of the roots and \(y_1, \dots , y_{n-1}\) the others. Then the polynomial is \((x-y)(x-y_1)\cdots (x-y_{n-1})\). Thus by comparing coefficients

and so \(a_{n-1}^2 - 2a_{n-2} - y^2 = \sum _{i=1}^{n-1} y_i^2\).

By Cauchy’s inequality applied to \((y_1, \dots , y_{n-1})\) and \((1, \dots , 1)\),

or

Thus \(y\) (and hence all \(y_i\)) lie between the two roots of the quadratic function, and these roots are our bounds.

Proof of \(\frac{2}{3}T \le A\). Since \(f(x)\) has only real roots, and none of them in the open interval \((-1,1)\), it can be written (apart from a constant positive factor which cancels out) in the form

with \(\alpha _i \ge 1\), \(\beta _j \ge 1\). Hence \(A = \int _{-1}^{1} f(x)\, dx\).

By making the substitution \(x \to -x\), we find that also \(A = \int _{-1}^{1} (1-x^2)\prod _i(\alpha _i + x)\prod _j(\beta _j - x)\, dx\), and hence by the inequality of the arithmetic and the geometric mean (note that all factors are \(\ge 0\)):

Computing \(f'(1)\) and \(f'(-1)\) from the product form, we find \(f'(1) = -2\prod (\alpha _i - 1)\prod (\beta _j + 1)\) and \(f'(-1) = 2\prod (\alpha _i + 1)\prod (\beta _j - 1)\), hence \(-f'(1)f'(-1) = 4\prod (\alpha _i^2-1)\prod (\beta _j^2-1)\), so

Applying the inequality of the harmonic and geometric mean to \(-f'(1)\) and \(f'(-1)\), we arrive by formula (2) for \(T\) at

The inequality \(A \le \frac{2}{3}R\): The book notes “The reader is invited to search for an equally inspired proof of the second inequality in Theorem 2.” This half is not formalized in Lean.

This proof, using Cauchy’s inequality, is due to Mantel. Let \(V = \{ 1, \dots , n\} \) be the vertex set and \(E\) the edge set of \(G\). By \(d_i\) we denote the degree of \(i\), hence \(\sum _{i \in V} d_i = 2|E|\) (see chapter 28). Suppose \(ij\) is an edge. Since \(G\) has no triangles, we find \(d_i + d_j \leq n\) since no vertex is a neighbor of both \(i\) and \(j\).

It follows that

Note that \(d_i\) appears exactly \(d_i\) times in the sum, so we get

and hence with Cauchy’s inequality applied to the vectors \((d_1, \dots , d_n)\) and \((1, \dots , 1)\),

and the result follows. In the case of equality we find \(d_i = d_j\) for all \(i, j\), and further \(d_i = \frac{n}{2}\) (since \(d_i + d_j = n\)). Since \(G\) is triangle-free, \(G = K_{n/2, n/2}\) is immediately seen from this.

The following proof of Theorem 3, using the inequality of the arithmetic and the geometric mean, is a folklore Book Proof. Let \(\alpha \) be the size of a largest independent set \(A\), and set \(\beta = n - \alpha \). Since \(G\) is triangle-free, the neighbors of a vertex \(i\) form an independent set, and we infer \(d_i \le \alpha \) for all \(i\).

The set \(B = V \setminus A\) of size \(\beta \) meets every edge of \(G\). Counting the edges of \(G\) according to their endvertices in \(B\), we obtain \(|E| \le \sum _{i \in B} d_i\). The inequality of the arithmetic and geometric mean now yields

and again the case of equality is easily dealt with.