Homework3.solution

.pdf
MAT157 Homework 3 Solutions S HUYANG S HEN Problem 1. Find a formula for n X r = 1 1 r ( r + 1 ) and prove it by induction. Solution. Notice that 1 r ( r + 1 ) = 1 r − 1 r + 1 , which gives n X r = 1 1 r ( r + 1 ) = n X r = 1 1 r − n X r = 1 1 r + 1 = n X r = 1 1 r − n + 1 X r = 2 1 r = 1 − 1 n + 1 = n n + 1 . So we claim that our formula is n X r = 1 1 r ( r + 1 ) = n n + 1 , and we verify this via induction. When n = 1 , we indeed have 1 X r = 1 1 r ( r + 1 ) = 1 2 = n n + 1 . Now suppose the formula holds for n = k , that is, ∑ k r = 1 1 r ( r + 1 ) = k k + 1 . Then for k + 1 , we get k + 1 X r = 1 1 r ( r + 1 ) = k X r = 1 1 r ( r + 1 ) + 1 ( k + 1 )( k + 2 ) = k k + 1 + 1 ( k + 1 )( k + 2 ) = k ( k + 2 ) + 1 ( k + 1 )( k + 2 ) = k + 1 k + 2 . So the formula is true for k + 1 as well. By induction, this formula is true for all natural numbers n . 1
Problem 2. Suppose that a 1 , . . . , a n ≥ 0 are non-negative real numbers. Their arithmetic mean (average) is defined by A n = A n ( a 1 , . . . , a n ) = 1 n ( a 1 + · · · + a n ) and their geometric mean is defined by G n = G n ( a 1 , . . . , a n ) = ( a 1 . . . a n ) 1 n . (i) Suppose that a 1 < A n , so that there must be another, say a 2 , with a 2 > A n . Let ¯ a 1 = A n and ¯ a 2 = a 1 + a 2 − A n . Show that ¯ a 1 ¯ a 2 ≥ a 1 a 2 . (ii) Apply (i) repeatedly to prove that G n ≤ A n . (iii) Write the proof in (ii) as a proof by induction. Hint: It will not be an induction on n . Solution. (i) Consider the difference ¯ a 1 ¯ a 2 − a 1 a 2 . We have ¯ a 1 ¯ a 2 − a 1 a 2 = A n ( a 1 + a 2 − A n ) − a 1 a 2 = − A 2 n + A n a 1 + A n a 2 − a 1 a 2 = −( A n − a 1 )( A n − a 2 ) . Now since a 1 < A n < a 2 , we have −( A n − a 1 )( A n − a 2 ) > 0 and hence ¯ a 1 ¯ a 2 > a 1 a 2 . Before we proceed with the rest of this problem, we first introduce two lemmas. Lemma 1. For any real numbers a 1 , . . . , a n with arithmetic mean A n , either a i = A n for all i , or there are some i and j such that a i < A n < a j . Additionally, we can reorder the numbers so that a 1 < A n and a 2 > A n without changing the arithmetic and geometric means. Proof. Suppose there is some i such that a i ̸ = A n . Without loss of generality 1 , we assume a i < A n . Now suppose there are no j s where a j > A n . Then a j ≤ A n for all j and we have A n = 1 n ( a 1 + · · · + a n ) ≤ 1 n (( n − 1 ) A n + a i ) < 1 n nA n = A n , This yields a contradiction, so we must have some j such that a j > A n . We can reorder the elements as desired by swapping a 1 with a i and a 2 with a j . The arith- metic and geometric means do not change upon reordering as addition and multiplication are commutative. 1 If a i > A n , we simply flip every inequality in this proof. 2
Lemma 2. With the setup in (i), write G ′ n = G n ( ¯ a 1 , ¯ a 2 , a 3 , . . . , a n ) and A ′ n = A n ( ¯ a 1 , ¯ a 2 , a 3 , . . . , a n ) . Then G ′ n ≥ G n and A ′ n = A n . Proof. We have G ′ n = n √ ¯ a 1 ¯ a 2 a 3 . . . a n ≥ n √ a 1 a 2 a 3 . . . a n = G n , and A ′ n = 1 n ( ¯ a 1 + ¯ a 2 + a 3 + · · · + a n ) = 1 n ( A n + a 1 + a 2 − A n + a 3 + · · · + a n ) = 1 n ( a 1 + a 2 + a 3 + · · · + a n ) = A n . (ii) Let a 1 , . . . , a n be non-negative real numbers. Lemma 1 tells us either they are all equal to A n (in which case we are done), or there are k > 0 elements not equal to A n . In the latter case, we may rearrange the terms so that a 1 < A n and a 2 > A n and apply (i) to get ¯ a 1 = A n and ¯ a 2 = a 1 + a 2 − A n satisfying, per Lemma 2, G ′ n ≥ G n and A ′ n = A n . Note that ¯ a 1 = A n , so this new set of numbers ¯ a 1 , ¯ a 2 , a 3 , . . . , a n has at most k − 1 terms not equal to A n . We may apply Lemma 1 and (i) repeatedly, each application reducing the number of non- A n terms by at least 1 . Then after at most k ≤ n applications, all n numbers in our set will be A n . 2 By Lemma 2, G ′ n does not decrease on each application, so G n ( A n , . . . , A n ) ≥ · · · ≥ G n ( ¯ a 1 , ¯ a 2 , a 3 , . . . , a n ) ≥ G n ( a 1 , . . . , a n ) . Now G n ( A n , . . . , A n ) = n p A n n = A n , so we have G n = G n ( a 1 , . . . , a n ) ≤ G n ( A n , . . . , A n ) = A n . (iii) Let k be the number of a i s that are not equal to A n . We claim that G n ≤ A n for each k = 0, . . . , n . When k = 0 , a i = A n for all i and so G n = n p A n n = A n , and our claim holds. Let k ≤ n − 1 and suppose the claim is true for each 0 ≤ j ≤ k . That is, G n ≤ A n holds if there are at most k a i s that are not equal to A n . 2 This is the step we are formalizing in (iii). 3
Now say we have k + 1 a i s not equal to A n . By Lemma 1 we can relabel them so that a 1 < A n < a 2 . Applying (i) to a 1 and a 2 , we know from Lemma 2 that G ′ n ≥ G n and A ′ n = A n . Consider our new set { ¯ a 1 , ¯ a 2 , a 3 , . . . , a n } . Now ¯ a 1 = A n and a 1 , a 2 ̸ = A n , so this set has at least one more A n than the original set { a 1 , a 2 , a 3 , . . . , a n } does. That is, it has at most k different a i s not equal to A n . By our induction hypothesis, we know G ′ n ≤ A ′ n , and so G n ≤ G ′ n ≤ A ′ n = A n . By mathematical induction, G n ≤ A n for all possible values of k , that is, for any number of a i not equal to A n . So G n ≤ A n for any nonnegative real numbers a 1 , . . . , a n . 4
Problem 3. Consider the following subsets S k ⊂ Z 3 × Z 3 where Z 3 = { 0, 1, 2 } and k = 1, 2, 3, 4, 5 . { ( 0, 1 ) , ( 0, 2 ) , ( 1, 2 ) } ( S 1 ) { ( 0, 1 ) , ( 1, 2 ) , ( 2, 0 ) } ( S 2 ) { ( 0, 0 ) , ( 1, 1 ) , ( 2, 2 ) } ( S 3 ) { ( 0, 1 ) , ( 1, 1 ) , ( 2, 1 ) } ( S 4 ) { ( 1, 0 ) , ( 1, 1 ) , ( 1, 2 ) } . ( S 5 ) (i) Which of the sets S k are functions Z 3 → Z 3 ? Justify your answer. (ii) When S k is a function, denote it by f k : Z 3 → Z 3 . For which of the functions f k is there a function g such that g ◦ f k is the identity map id : Z 3 → Z 3 , id : a 7 → a for all a . Give the subset S defining g . (iii) For which of the functions f = f k is it true that f ( a + b ) = f ( a ) + f ( b ) ? (iv) For which of the functions f = f k is it true that f ( ab ) = f ( a ) f ( b ) ? Solution. (i) S 1 contains two distinct pairs with the same first element ( 0, 1 ) and ( 0, 2 ) , while S 5 contains ( 1, 0 ) and ( 1, 1 ) . So S 1 and S 5 are not functions. On the other hand, S 2 , S 3 , S 4 each contains three pairs of distinct first elements, so they do not have distinct pairs with the same first element. That is, S 2 , S 3 , S 4 are functions on Z 3 while S 1 and S 5 are not. (ii) As per 5(i), such a g exists if and only if f k is injective. Now f 2 and f 3 are injective, so we can find functions g for f 2 and f 3 , defined by the sets S ′ 2 and S ′ 3 respectively: { ( 0, 2 ) , ( 1, 0 ) , ( 2, 1 ) } ( S ′ 2 ) { ( 0, 0 ) , ( 1, 1 ) , ( 2, 2 ) } . ( S ′ 3 ) On the other hand, we cannot find such a g for f 4 . Indeed, for any a ∈ Z 3 , we have ( g ◦ f 4 )( a ) = g ( f 4 ( a )) = g ( 1 ) , which can only take one value. So such a g cannot exist. (iii) We know f 3 is the identity function id, so f 3 ( a ) = a for all a . That is, f 3 ( a ) + f 3 ( b ) = a + b = f 3 ( a + b ) . On the other hand, we have f 2 ( 0 ) + f 2 ( 1 ) = 0 ̸ = f 2 ( 1 ) and f 4 ( 0 ) + f 4 ( 1 ) = 2 ̸ = f 4 ( 1 ) , so the only function satisfying f ( a + b ) = f ( a ) + f ( b ) is f 3 . (iv) As with part (iii), we know f 3 ( a ) f 3 ( b ) = ab = f 3 ( ab ) . As for f 4 , we know f 4 ( a ) = 1 for any a , so f 4 ( a ) f 4 ( b ) = 1 = f 4 ( ab ) . We also have f 2 ( 0 ) f 2 ( 1 ) = 2 ̸ = f 2 ( 0 ) , so the functions satisfying f ( ab ) = f ( a ) f ( b ) are f 3 and f 4 . 5
Problem 4. For x ∈ R , define s ( x ) = 0 if x is irrational 1 if x is rational. Let f ( x ) = 1 1 − x and g ( x ) = p | x | . Compute the functions: f ◦ s, s ◦ f, g ◦ s, s ◦ g. In particular, you need to determine their domains. Solution. We first consider the domains and ranges of s , f , and g . s : R → { 0, 1 } , f : R \{ 1 } → R \{ 0 } , g : R → R ≥ 0 . ( R ≥ 0 = { x ∈ R : x ≥ 0 } is the set of nonnegative real numbers.) In particular, f ( 1 ) is undefined (division by zero) and f ( x ) = y solves to x = 1 − 1 y , which has no solutions when y = 0 . Now ( f ◦ s )( x ) is undefined when s ( x ) = 1 , that is, when x is rational. On the other hand, for any irrational x , we have ( f ◦ s )( x ) = f ( 0 ) = 1 . So the domain of f ◦ s is the set of irrational numbers R \ Q , and ( f ◦ s )( x ) = 1. ( s ◦ f )( x ) is only undefined if f ( x ) is undefined, so the domain of s ◦ f is R \{ 1 } . The value of ( s ◦ f )( x ) depends on the rationality of f ( x ) . Since Q is a field, it is closed under + , · , and inverses. Then for any rational number x ̸ = 1 , ( 1 + (− x )) − 1 ∈ Q . On the other hand, if y = f ( x ) ̸ = 0 is rational, we know −( y − 1 − 1 ) ∈ Q . So within the domain of f , f ( x ) is rational precisely when x is rational. That is, ( s ◦ f )( x ) = 0 if x is irrational 1 if x is rational. g and s are both defined everywhere, so the domains of g ◦ s and s ◦ g are both R . Now s takes only the values 1 and 0 while g ( 1 ) = 1 , g ( 0 ) = 0 , so ( g ◦ s )( x ) = 0 if x is irrational 1 if x is rational. As for s ◦ g , we know s ( g ( x )) = 1 if g ( x ) is rational and 0 if g ( x ) is irrational, so ( s ◦ g )( x ) = 0 if p | x | is irrational 1 if p | x | is rational. Unfortunately there isn't much else we can do to simplify the conditions on this last one. 6
Problem 5. Let A and B be nonempty sets. Suppose that f : A → B is a function. Show that (i) f is injective if and only if there is a function g : B → A such that g ◦ f = id A . (ii) f is surjective if and only if there is a function g : B → A such that f ◦ g = id B . (iii) f is bijective if and only if there is a function g : B → A such that g ◦ f = id A and f ◦ g = id B . Solution. (i) Suppose f is injective. Define a function g : B → A such that g ( y ) = x if f ( x ) = y for some x , and g ( y ) = a for some a ∈ A otherwise. (This requires A to be nonempty, and in turn B must also be nonempty since f : A → B is a function.) Since f ( x ) = f ( y ) only if x = y , we know g is well-defined. Then g ◦ f = id A . Now suppose there is a function g : B → A such that g ◦ f = id A . For any x, y ∈ A , if f ( x ) = f ( y ) , then we have x = ( g ◦ f )( x ) = g ( f ( x )) = g ( f ( y )) = ( g ◦ f )( y ) = y. That is, x = y whenever f ( x ) = f ( y ) . Then f is injective. (ii) Suppose f is surjective. Then for any y ∈ B there is some x ∈ A such that f ( x ) = y . In other words, the set S y = { x : f ( x ) = y } is nonempty for any y . Define a function g : B → A such that g ( y ) = x for some x ∈ S y . 3 This function is well-defined by construction, and f ◦ g = id B . Now suppose there is a function g : B → A such that f ◦ g = id B . For any y ∈ B , take x = g ( y ) . Then f ( x ) = f ( g ( y )) = y . That is, f is surjective. (iii) The backward direction is easy as the existence of such a function g tells us f is injective and surjective per (i) and (ii). If f is bijective, we know there are functions g 1 , g 2 : B → A such that g 1 ◦ f = id A and f ◦ g 2 = id B . Since function composition is associative, we have g 1 = g 1 ◦ id B = g 1 ◦ ( f ◦ g 2 ) = ( g 1 ◦ f ) ◦ g 2 = id A ◦ g 2 = g 2 . Then g 1 is our function g . 3 Note that this isn't quite as intuitive as it may seem-when B is infinite, we need the Axiom of Choice to guarantee we can choose an x for each y , but we assume it in this course. 7
Uploaded by AmbassadorScorpionPerson951 on coursehero.com