HOMEWORK 5, PART A

MATH 25

1. Problems graded by Jennifer

1.1. The AM-GM inequality. Let a_{1}, ⋯, a_{n} be positive real numbers. The arithmetic mean of the a_{k}’s is (a_{1} + ⋯ + a_{n})/n and their geometric mean is \sqrt[n]{a_{1} ⋯ a_{n}}. The AM-GM inequality says that

\sqrt[n]{a_{1} ⋯ a_{n}} ≤ \frac{a_{1} + ⋯ + a_{n}}{n} .

The goal of this problem is to prove the above inequality. If a, b ≥ 0, compute (\sqrt{a} + \sqrt{b})^{2} − (\sqrt{a} − \sqrt{b})^{2} and deduce that \sqrt{ab} ≤ (a + b)/2

Proof: We have (\sqrt{a} + \sqrt{b})^{2} − (\sqrt{a} − \sqrt{b})^{2} = 4\sqrt{ab} and since (\sqrt{a} + \sqrt{b})^{2} − (\sqrt{a} − \sqrt{b})^{2} ≤ (\sqrt{a} + \sqrt{b})^{2} = a + b + 2\sqrt{ab}, we have \sqrt{ab} ≤ (a + b)/2.

Use this to prove that if k ≥ 1 and a_{1}, ⋯, a_{2^{k}} are positive real numbers, then

\sqrt[2^{k}]{a_{1} ⋯ a_{2^{k}}} ≤ \frac{a_{1} + ⋯ + a_{2^{k}}}{2^{k}} .

Proof: For k = 1, this is the above result. Now if we set a = \sqrt[2^{k−1}]{a_{1} ⋯ a_{2^{k−1}}} and b = \sqrt[2^{k−1}]{a_{1+2^{k−1}} ⋯ a_{2^{k}}}, then \sqrt{ab} ≤ (a + b)/2 so that

\sqrt[2^{k}]{a_{1} ⋯ a_{2^{k}}} ≤ (a + b)/2 ≤ \frac{\sqrt[2^{k−1}]{a_{1} ⋯ a_{2^{k−1}}} + \sqrt[2^{k−1}]{a_{1+2^{k−1}} ⋯ a_{2^{k}}}}{2} ≤ \frac{a_{1} + ⋯ + a_{2^{k}}}{2^{k}}

prove the AM-GM inequality. Hint: given a_{1}, ⋯, a_{n} choose k such that 2^{k} ≥ n and set a_{n+1}, ⋯, a_{2^{k}} = \sqrt[n]{a_{1} ⋯ a_{n}}

Proof: Set a = a_{n+1}, ⋯, a_{2^{k}} = \sqrt[n]{a_{1} ⋯ a_{n}}. We then have

\sqrt[2^{k}]{a_{1} ⋯ a_{2^{k}}} ≤ \frac{a_{1} + ⋯ + a_{2^{k}}}{2^{k}}

which implies that

\sqrt[2^{k}]{a_{1} ⋯ a_{n}a^{2^{k}−n}} ≤ \frac{a_{1} + ⋯ + a_{n} + (2^{k} − n)a}{2^{k}}

and a_{1} ⋯ a_{n} = a^{n} so that

a ≤ \frac{a_{1} + ⋯ + a_{n} + (2^{k} − n)a}{2^{k}}

2 MATH 25

and this directly implies

\sqrt[n]{a_{1} ⋯ a_{n}} ≤ \frac{a_{1} + ⋯ + a_{n}}{n} .

1.2. Let {f_{n}}_{n≥0} : R_{≥0} → R be the sequence of functions defined by f_{0}(x) = 0 and

f_{n+1}(x) = f_{n}(x) + \frac{1}{2}(x − f_{n}^{2}(x)).

Prove that for every x ∈ [0, 1],

0 ≤ \sqrt{x} − f_{n}(x) ≤ \sqrt{x} (1 − \frac{\sqrt{x}}{2})^{n} .

Proof: for n = 0, the above inequality is just 0 ≤ \sqrt{x} ≤ \sqrt{x} which is certainly true. Now assuming that it is true for n, we will prove it for n+1. Note that \sqrt{x}−f_{n}(x) ≤ \sqrt{x} (1 − \frac{\sqrt{x}}{2})^{n} implies that f_{n}(x) ≥ 0. We have

\sqrt{x} − f_{n+1}(x) = \sqrt{x} − f_{n}(x) − \frac{1}{2}(x − f_{n}^{2}(x))

= (\sqrt{x} − f_{n}(x)) (1 − \frac{1}{2}(\sqrt{x} + f_{n}(x)))

≤ \sqrt{x} (1 − \frac{\sqrt{x}}{2})^{n} (1 − \frac{1}{2}(\sqrt{x} + f_{n}(x)))

≤ \sqrt{x} (1 − \frac{\sqrt{x}}{2})^{n} (1 − \frac{\sqrt{x}}{2})

= \sqrt{x} (1 − \frac{\sqrt{x}}{2})^{n+1}

while

\sqrt{x} − f_{n+1}(x) = (\sqrt{x} − f_{n}(x)) (1 − \frac{1}{2}(\sqrt{x} + f_{n}(x)))

≥ (\sqrt{x} − f_{n}(x)) (1 − \frac{1}{2}(2\sqrt{x}))

≥ 0.

Prove that f_{n} converges uniformly to \sqrt{x} on [0, 1].

Proof: the function y ↦ y(1 − y/2) from [0, 1] to R has its maximum is at y = 1 where it is equal to 1/2. This implies that

0 ≤ \sqrt{x} − f_{n}(x) ≤ (\frac{1}{2})^{n}

and therefore that f_{n} converges uniformly to \sqrt{x} on [0, 1].