Mathematics 220 Homework 7 Due March 3/4 1. Question 6.2. Prove that any non-empty subset of a well-ordered set of real numbers is well-ordered. 2. Prove that for all n N 1 1 n 1 + ++ = . 12 23 n(n + 1) n+1 3. Let a, b Z and m. Using mathematical induction, prove that if a b mod m then an bn for all n N. 4. Let A be a nite set, and let P(A) be the set of all its subsets. Prove the fact that |P(A)| = 2|A| by mathematical induction. 5. Use induction to prove DeMorgan's law for n sets (n 1): let A1 , . . . , An be sets; prove that A1 An = A1 A2 An . 6. Prove that for all natural numbers n 10, 2n > n3 . 7. Let F1 , F2 , . . . , Fn . . . , be the sequence of Fibonacci numbers: by denition, F1 = F2 = 1, and the sequence is dened recursively by the formula Fn = Fn1 + Fn2 for n 3. (Thus, we get the sequence 1, 1, 2, 3, 5, 8, 13, 21, . . . . ) Prove the formula 1 Fn = 5 1+ 5 2 n 1 5 2 n . Two remarks: (1) Note that it's not even completely obvious why the expression on the right is a rational number! But you will prove that it is, in fact, an integer, namely, the n-th Fibonacci number. (2) The number = 1+2 5 is called the golden ratio. 8. A graph is called complete if any two vertices are connected by an edge. Prove that the complete graph with n vertices contains precisely n(n 1)/2 edges. 9. A graph is called a tree if it is connected and contains no cycles (equivalently, there is precisely one path from any vertex v1 to any other vertex v2 ). Prove that: (a) Any tree must contain at least one vertex of degree 1 (that is, a vertex with only one edge leading to it; sometimes such a vertex in a tree called \"a leaf\"). Hint: consider the longest possible path in this graph, and think about its ends. (b) Prove that any tree with n vertices contains precisely n 1 edges. Page 1 of 1