An Extension of the AM-GM Inequality

The Arithmetic Mean - Geometric Mean inequality in its simplest form tells us that

For positive \(x_{1}\) and \(x_{2}\),

\(\frac{x_{1}+x_{2}}{2}\ge \sqrt{x_{1}x_{2}}.\)

This is equivalent to saying that

For positive \(x_{1}\) and \(x_{2}\), such that \(x_{1}+x_{2}=1\),

\(x_{1}x_{2}\le \frac{1}{4}.\)

The problem is to prove that

For positive \(x_{1}, x_{2}, \ldots\ , x_{100}\), such that \(x_{1}+x_{2}+\ldots +x_{100}=1 \),

\(x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{4} + \ldots + x_{99}x_{100} \le \frac{1}{4}.\)

Proof

|Contact| |Front page| |Contents| |Induction| |Inventor's Paradox| |Store|

Copyright © 1996-2017 Alexander Bogomolny

For positive \(x_{1}, x_{2}, \ldots\ , x_{100}\), such that \(x_{1}+x_{2}+\ldots +x_{100}=1 \),

\(x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{4} + \ldots + x_{99}x_{100} \le \frac{1}{4}.\)

Proof

It is rather obvious that number 100 in the problem is likely to be random and the inequality holds for an arbitrary \(n\ge 2\), if at all.

For positive \(x_{1}, x_{2}, \ldots\ , x_{n}\), such that \(x_{1}+x_{2}+\ldots +x_{n}=1 \),

\(x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{4} + \ldots + x_{n-1}x_{n} \le \frac{1}{4}.\)

Since we already know that the inequality holds for \(n=2\), mathematical induction naturally comes to mind. Let's check how the inequality looks like for \(n=3\):

\(x_{1}x_{2} + x_{2}x_{3} \le \frac{1}{4},\)

provided \(x_{1}+x_{2}+x_{3}=1\).

This problem easily reduces to the base case of \(n=2\). Indeed, letting \(x'_{1}=x_{1}+x_{3}\) gives, first of all, \(x'_{1}+x_{2}=1\) and then also

\(\frac{1}{4}\ge x_{1}x_{2} + x_{2}x_{3} = (x_{1} + x_{3})x_{2} = x'_{1}+x_{2}\).

Just what is needed; encouragingly, the inequality holds for \(n=3\).

Trying to employ similar grouping of two terms for \(n=4\) we run into a little trouble:

\(x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{4} = x_{1}x_{2} + (x_{2} + x_{4})x_{3}\).

We do get \(2\) terms as required for \(n=3\) but the factors do not form a three term sequence. What is needed is to have factors \(x_{2}\) in the first term and \((x_{2} + x_{4})\) equal. But surely they are not. What actually works is replacing \(x_{2}\) with \((x_{2} + x_{4})\). True, these will increase the whole sum:

\(x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{4} = x_{1}x_{2} + (x_{2} + x_{4})x_{3} \lt x_{1}(x_{2} + x_{4}) + (x_{2} + x_{4})x_{3}\).

However, on the write we do have the sum corresponding to three terms: \(x_{1} + (x_{2} + x_{4}) + x_{3} = 1\). So that from already tackled case of \(n=3\) we conclude that

\(x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{4} = x_{1}x_{2} + (x_{2} + x_{4})x_{3} \lt x_{1}(x_{2} + x_{4}) + (x_{2} + x_{4})x_{3} \le \frac{1}{4}\).

Which not only proves the case of \(n=4\) but also shows how to handle a general inductive step.

So assume that, provided \(x_{1}+x_{2}+\ldots +x_{k}=1 \),

\(x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{4} + \ldots + x_{k-1}x_{k} \le \frac{1}{4}.\)

Under this assumption we show that, for \(x_{1},x_{2},\ldots, x_{k+1}\), with \(x_{1}+x_{2}+\ldots +x_{k+1}=1 \),

\(x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{4} + \ldots + x_{k-2}x_{k-1} + x_{k-1}x_{k} + x_{k}x_{k+1} \le \frac{1}{4}.\)

Since \(x_{k-1}\lt (x_{k-1}+x_{k+1})\), we see that

\(\begin{align} & x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{4} + \ldots + x_{k-2}x_{k-1} + x_{k-1}x_{k} + x_{k}x_{k+1} \lt \\ & x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{4} + \ldots + x_{k-2}(x_{k-1}+x_{k+1}) + (x_{k-1}+x_{k+1})x_{k}\le \frac{1}{4} \end{align}\)

because the sequence if \(k\) terms satisfies \(x_{1}+x_{2}+\ldots +x_{k-2} + (x_{k-1}+x_{k+1}) + x_{k}=1 \) and the inductive assumption applies.

(Elsewhere there is another proof - much shorter and certainly cleverer.)

|Contact| |Front page| |Contents| |Induction| |Inventor's Paradox| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 62315256

Search by google: