Exercises for Unit V (The basic number systems of mathematics) V.1 : The natural numbers and the integers (Halmos, §§ 11 – 13; Lipschutz, §§ 2.1, 2.7 – 2.9) Problems for study. Lipschutz : 2.88, 2.92(c) Exercises to work. 1. Suppose we are given a quadratic equation x 2 + b x + c = 0 where b and c are integers, and suppose that r is a rational root of this equation. Prove that r is an integer. [ Hint : Write the quadratic polynomial as (x – r)(x – s) and explain why r + s and rs must be integers. Why does this imply that s is also rational? Next, using the quadratic formula show that (r – s)2 = b 2 – 4 c and hence the right hand side is a is a perfect square, say d 2. Next, write r = p / q where p and q are relatively prime, and apply the quadratic formula to show that the absolute value of the denominator |q| is at most 2. Why do this and the integrality of rs imply that b and d must be both even or both odd? Now use the quadratic formula once more to show that the root r must be an integer; i.e., we must have |q| = 1. ] 2. Explain how one can prove irrationality of the square root of 2 from a special case of the preceding result. 3. Let n be a positive integer. Explain why the set A of all integers greater than or equal to – n is well – ordered. [ Hint : If B is a nonempty subset of A, consider the set C of all integers of the form n + b where b ∈∈∈∈ B. ] I V.2 : Finite induction and recursion (Halmos, §§ 11 – 13; Lipschutz, §§ 1.11, 4.6, 11.1 – 11.7) Problems for study. Lipschutz : 1.36, 1.74 – 1.76Exercises to work. 1. Prove by induction that for each nonnegative integer k, the integer k2 + 5k is even. 2. Prove the summation formula 13 + … n 3 = (1 + … + n) 2 = n2 (n + 1) 2 / 4. 3. The number n! (n factorial), which is the number of permutations of the first n positive integers, is defined recursively by 0! = 1 and n! = n ⋅⋅⋅⋅ (n – 1) ! for all n > 0. Prove that n! ≤≤≤≤ n n for all n > 0 and strict inequality holds if n > 1. 4. The so – called sequence of Fibonacci numbers is given recursively by the formulas F0 = F1 = 1 and Fn = F n – 1 + F n – 2 for n > 1. Find a function H as in the recursive definition theorem which can be used to define the sequence of Fibonacci numbers. [ Hint : The cases n = 1 and n > 1 must be handled separately. ] Comment: Fibonacci (c. 1170 – 1250), whose real name was Leonardo of Pisa, made many extremely significant contributions to mathematics, but it is ironic that he is often best known today for mentioning a sequence that had been previously introduced by others and which really plays an extremely minor part in his work as a whole. Further information on these historical issues is given at the following online site: http://math.ucr.edu/~res/math153/history07.pdf 5. An amortized loan is paid off in equal periodic payments of P units. Assume that the periodic interest rate over the time period is (100 ⋅⋅⋅⋅ r) % . If L is the loan amount and xn is the balance remaining after the nth payment, give a recursive formula for xn . Comment: Usually one is given L and r, and the objective is to find a value of P such that the balance is equal to zero after the M th payment for some fixed M (which is normally a multiple of 12). In order to do this, one needs to derive a closed formula for xn and solve for P in terms of L, r and M. 6. Let (N, σσσσ) be a system satisfying the Peano axioms with zero element 0N. Prove that 0N is the only element that is not in the image of σσσσ.... [ Hint : Apply the third Peano axiom fo the set A = { 0N } ∪∪∪∪ σσσσ(N). ]I V.3 : Finite sets (Halmos, §§ 11 – 13; Lipschutz, §§ 1.8, 3.2) Problems for study. Lipschutz : 1.25, 1.26 Exercises to work. 1. Suppose that we are given two finite sets A and B and a subset C of A ×××× B such that the following hold: (1) Each element of A is the first coordinate for some element of C. (2) For each a ∈∈∈∈ A , the number of elements in C ∩∩∩∩ [ { a } ×××× B ] is equal to a fixed constant k. Prove that the number of elements in C is equal to k ⋅⋅⋅⋅ |A| , where |A| denotes the number of elements in A. [ Hint : Use induction on the number of elements in A. ] 2. Use the preceding exercise to compute the number of ordered pairs (x, y) where x and y are integers between 1 and 10 such that one is even and the other is odd. 3. Determine the number of Boolean subalgebras of P(X) if X is the set {1, 2, 3, 4}. How many have exactly two atomic subsets? I V.4 : The real numbers (Lipschutz, §§ 2.2 – 2.6, 7.7) Problems for study. Lipschutz : 2.14 – 2.15, 2.17, 2.25 – 2.28, 2.61 – 2.62, 2.67, 2.71 – 2.72, 2.73(d), 7.22, 7.25 – 7.26, 7.62 – 7.63, 7.66 Exercises to work. 1. Let A be a set of real numbers containing exactly two elements. Explain why A is bounded, find the least upper bound and greatest lower bound, and prove that your answers are correct.2. Let A and B be a subsets of the real numbers with least upper bounds u and v. Prove that their union has a least upper bound, and express it in terms of u and v. 3. Let A be the set of negative real numbers. Prove that 0 is equal to the least upper bound of A. [ Hint : One needs to check that 0 is an upper bound and if x < 0 then 0 is not an upper bound; i.e., there is some y ∈∈∈∈ A such that x < y. ] 4. Let A be a set of real numbers with least upper bound x. Show that there is a sequence of elements xn in A whose limit is equal to x; note that the terms of a sequence need not be distinct. [ Hint : Given a positive integer n, why is there an element y of A such that y > a – (1/n)? ] I V.5 : Familiar properties of the real numbers (Lipschutz, §§ 2.2, 4.5) Problems for study. Lipschutz : 4.55, 6.17 Exercises to work. 1. Suppose that a and b are real numbers such that a …
View Full Document