18.100A Recitation 1 Notes

Recitation 01 To-do list: 1. Proving the AM-GM inequality and introducing proof by mathematical induction. 2. Exercise 1.2.10: Given that A, B ⊂ R>0 (both bounded and nonempty), consider the set C := {a · b | a ∈ A, b ∈ B} (where := means that we are defining C to be that way). Show that sup C = sup A · sup B. The Arithmetic Mean-Geometric Mean inequality (abbreviated as AM-GM) states that for n nonnegative real numbers x1 , . . . , xn , √ x1 + · · · + xn ≥ n x1 . . . xn . n In the homework, y’all proved the base case of n = 2. Note that this inequality is true for n = 1, but this is a more √ trivial statement ( x11 ≥ 1 x1 ). Normally we could try to use Standard Induction to prove this: 1. First prove the base case (which is already done). 2. Then, assume the statement is true for some k and show that this implies the statement is true for k + 1 (where k is an arbitrary natural number). However, we will instead use a new method that is similar to Standard Induction: 1. Prove that the statement is true for n = 2k using induction. 2. Then, show this implies it is true for all natural numbers. The case where k = 1 was done in the homework. So now, assume that the AM-GM inequality is true for some k. Then, we want to show that the inequality is true for k + 1: x1 + · · · + x2k+1 (x1 + · · · + x2k ) + (x2k +1 + · · · + x2k+1 ) = . 2k+1 2k+1 Notice that we haven’t changed anything here, but we have separated the sum of 2k+1 terms into to sums of 2k terms. This allows us to apply what we have assumed: √ √ 2k · ( 2k x1 . . . x2k + 2k x2k +1 . . . x2k+1 ) ≥ 2k+1 √ √ ( 2k x1 . . . x2k + 2k x2k +1 . . . x2k+1 ) = . 2 Now we can apply the base case with k = 1: √ √ x1 . . . x2k · 2k x2k +1 . . . x2k+1 √ = 2k+1 x1 . . . x2k+1 . ≥ q 2k Thus, we have shown the AM-GM inequality is true for n = 2k for all k ∈ N. To show the AM-GM inequality is true for all n (not just those which are powers of 2) we want to find the nearest m ≥ n such that m = 2k for some 1 nonnegative integer k. Let µ= x1 + · · · + xn , n and let xn+1 = xn2 = · · · = xm = µ. Hence, x1 + · · · + xn n m n (x1 + · · · + xn ) = m x1 + · · · + xn + m−n n (x1 + · · · + xn ) = m x1 + · · · + xn + (xn+1 + · · · + xm ) = . m µ= Applying the AM-GM inequality since m = 2k : √ x1 . . . xm p m x1 . . . xn · µm−n . µ≥ µ≥ m Moving all the µ to the left hand side and dealing with exponents, we get µ≥ √ n x1 . . . xn . Since µ is the arithmetic mean, we are complete with our proof. Now we will work on Exercise 1.2.10. Step 1: We want to show that C is bounded (i.e. that the supremum exists). Given that A is bounded, there exists an α such that a ≤ α for all a ∈ A. Similarly, there exists a β such that b ≤ β for all b ∈ B. Hence, since A and B only contain positive numbers, ab ≤ αβ for all a ∈ A and all b ∈ B. Therefore, C must be bounded as C is the set of all such ab. Proving the existence of a supremum is almost always the first step in proving a statement like this one. Step 2: Now that we know it exists, we want to show that sup C = sup A · sup B. We can do this by showing that sup C ≤ sup A · sup B and sup C ≥ sup A · sup B (a very common technique in analysis). It is clear that ⎧ ⎨0 ≤ a ≤ sup A ⎩0 ≤ b ≤ sup B ∀a ∈ A . ∀b ∈ B Hence, ab ≤ sup A · sup B for all ab ∈ C. Hence, sup A · sup B is an upper bound for C, and thus sup C ≤ sup A · sup B. Now for the other direction. Fix b ∈ B (noting of course that b > 0 for all b ∈ B). Then, a ≤ supb C for all a ∈ A. This implies that supb C is an upper bound for A. Since sup A is the least upper bound for A, this implies that for all b ∈ B, sup C sup C sup A ≤ =⇒ b ≤ ∀b ∈ B. b sup A Note that sup A = 6 0 as A = 6 ∅, and A ⊂ R>0 . Therefore, sup B ≤ sup C sup A is an upper bound for B, and hence sup C =⇒ sup A · sup B ≤ sup C. sup A 2 Therefore, sup C = sup A · sup B. We leave the following exercise to the student: Show that given A, B ⊂ R≥0 (such that A and B are bounded and nonempty), and C defined just as before, then sup C = sup A · sup B. The only di˙erence between this exercise and 1.2.10 is that before we were dealing with sets of only positive numbers, and now we want to include the possibility that A and/or B contain 0. 3