Assignment 1 MA 375 Homework 1 Solutions Section 5.1: 54: The claim is true if n=1 because if you pick 2 numbers from the set {1,2} then it is easy to see that there are 2 chosen numbers that divide each other. (Generally, if 2 equal numbers are chosen this is true trivially, and if you choose 2 distinct ones an easy check shows that the claim is ok.) Now assume the claim is true for n+1 numbers chosen from {1,2,...,2n} and let's try to show it stays true if we pick n+2 numbers from {1,...,2n+2}. Again, if there are 2 equal numbers there is nothing to prove really, so let's suppose all the chosen numbers are distinct. If all, or just n+1 of the n+2 chosen numbers are in the smaller set {1,2,...,2n} then the inductive hypothesis helps us out to conclude that there are 2 chosen ones that divide each other. So let's consider the case where 2n+1, 2n+2 and n of the numbers {1,2,...,2n} are chosen. Clearly, if in this situation n+1 is also a chosen number we are done because n+1 divides 2n+2. So assume that n+1 is not chosen. Let C be the chosen numbers that are less than 2n+1; there are n of these. Consider the set D which is C together with the number n+1. D contains n+1 distinct numbers, and they are all in {1,2,...,2n}. By the inductive hypothesis, D contains 2 numbers A and B which divide each other. If neither A nor B are equal to n+1, then C contains both A and B and so A and B are both chosen numbers and we are done. Finally, we inspect the case where either A or B is n+1. The other number is then either a divisor or a multiple of n+1. It can't be a multiple because the smallest multiple would be 2(n+1) which is bigger than 2n+1 and hence not in C. It follows that C contains a divisor of n+1. Of course, n+1 is not a chosen number, so that this divisor does not seem to be helpful. However, 2*(n+1)=2n+2 IS a chosen number, and a divisor of n+1 is also a divisor of 2n+2. So even in this worst of all cases there are 2 chosen numbers that divide each other. This completes the inductive step and the proof. 51: The problem is that even though x and y are positive integers, the numbers x-1 and y-1 may not be. That means, that we cannot use the inductive hypothesis on x-1 and y-1. To see an explicit example how the proof fails, note first that the base case is ok: if you have 2 positive numbers x, y and their maximum is equal to 1, then they are both equal, x=y=1. If now we look at the next case, k=2, we could have x=1 and y=2. Their max is 2, and yet they are not equal. So with this choice of x and y the proof must fail. It does the moment that you try to use the "fact" that since x-1 and y-1 have max equal to 1 then they must be equal. This is an attempt of using the inductive hypothesis in the wrong way: since x=1, x-1 is NOT positive. So the base case (which only considers positive numbers) does not apply. And indeed, x-1=0 and y-1=1 are not equal. 8: Note that 2-2*7+2*7^2-...+2*(-7)^n = sum 2*(-7)^i i=0 Let P(n) be the statement " 2-2*7+2*7^2-...+2*(-7)^n = (1-(-7)^(n+1))/4 ". Armed with this we see that the base case n=0 is true: (1-(-7)^1)/4 = (1+7)/4 =2. Now assume that P(n) is true. Then 2-2*7+2*7^2-...+2*(-7)^n = (1-(-7)^(n+1))/4 and hence 2-2*7+2*7^2-...+2*(-7)^n +2*(-7)^(n+1)=(1-(-7)^(n+1))/4+2*(-7)^(n+1). =[(1-(-7)^(n+1))+8*(-7)^(n+1)]/4 =[1+(-7)^(n+1)*(-1+8)]/4 =[1+(-7)^(n+1)*(7)]/4 =[1-(-7)^(n+1)*(-7)]/4 =[1-(-7)^(n+2)]/4 which is exactly what we had to show: P(n+1) is true. 6 : Let P(n) be "1*1! + 2*2! + ...+ n*n! = (n+1)! -1". The base case is easy. Assume P(n). Then 1*1! + 2*2! + ...+ n*n! + (n+1)*(n+1)! = (n+1)! -1 +(n+1)*(n+1)! by the inductive hypothesis = (n+1)! *[1+n+1] -1 = (n+2)! -1. This is precisely what P(n+1) says. 20: Let P(n)= " 3^n < n! for all n>6. The base case is n=7, the first number bigger than 6. There we have 3^7= 2187 and 7!=5040. So, ok. No assume P(n). Then 3^(n+1) = 3^n * 3 < n! * 3 (by inductive hypothesis) < n! * 4 < n! * 5 ... < n! *(n+1) = (n+1)!. That is what P(n+1) says. 32: Base case n=0 is true. 3 divides 0. (n+1)^3 +2*(n+1) = n^3 + 3*n^2 + 3*n + 1 + 2*n + 2 = n^3 + 2*n + 3*(n^2+n+1) By inductive hypothesis, n^3+2*n is a multiple of 3. Obviously, 3*(n^2+n+1) is also a multiple of 3. Hence their sum is a multiple of 3. TRhis sum equals (n+1)^3 +2*(n+1), hence P(n+1) holds. Section 8.5: 6: a) 10000 since adding A1 and A2 to A3 does not give anything that was not already in A3. b) 11100 since there is no overlap of the sets. c) If we just add them altogether, we get 11100. However, there are two elements in A1 intersection A2 that we counted twice, once for A1 and once for A2. So we should subtract them from 11100. Similarly we double counted the 2 elements common to A1 and A3, and the two elements common to A2 and A3. So the corrected count is 11100 - 6. Now however we made another mistake: there is one element that was in A1 and A2 and A3. This was counted 3 times in the sum 11100, and then taken out 3 times as one of the two elements in the corrected sum. So in the number 11100-6 it is not counted at all! Let's put it back in, then we get 11095. The general formula is written down on top of page 454. It comes from the double counting considerations we just went through. 12: There are 1000 integers not exceeding 1000. Of these, the squares of 1,2,...,31 are squares. Also, there are the 10 cubes 1,2^3,...,10^3. There are 3 numbers that are simultaneously squares and cubes: 1, 64 and 729. 1=1^2=1^3, 64=4^3=8^2, 729=27^2=9^3. Let A2 be the set of all squares, it has 31 elements. Let A3 be the set of all cubes, it has 10 elements. There are 3 in both, so the union of A2 and A3 has 31+10-3 = 38 elements. 20: 10000+10000+10000+10000+10000 -1000-1000-1000-1000-1000-1000-1000-1000-1000-1000 +100+100+100+100+100+100+100+100+100+100 -10-10-10-10-10 +1 (there are 5 sets, 10 2-fold intersections, 10 3-fold intersections, 5 4-fold intersections and 1 5-fold interesection) 28: This is similar to counting the elements in the union of 4 sets, except that we picture each number of elements being divided by the total number of elements. Let me write "U" for "union" and "^" for intersection. The number of elements in a union of 4 sets A,B,C,D is |A U B U C U D| = |A| + |B| + |C| + |D| - |A ^ B| -|A ^ C| - |A ^ D| - |B ^ C| - |B ^ D|-|C ^ D| + |A ^ B ^ C| + |A ^ B ^ D| + |A ^ C ^ D| + |B ^ C ^ D| - |A ^ B ^ C ^ D|. In our problem, no three events occur at the same time. So triple and 4-fold intersections are empty, their cardinality is zero. This erases all entries in the 3rd and 4th line. Now divide by |S|, the number of elements in the sample space. This gives p(AUBUCUD)=p(A)+p(B)+p(C)+p(D) -p(A^B)-p(A^C)-p(A^D)-p(B^C)-p(B^D)-p(C^D).