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 contributionsto mathematics, but it is ironic that he is often best known today for mentioning a sequence that had been previously introduced byothers and which really plays an extremely minor part in his work as a whole. Further information on these historical issues is givenat the following online site:http://math.ucr.edu/~res/math153/history07.pdf5. 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 amountand 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 paymentfor 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.26Exercises 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.66Exercises to work . 1. Let A be a set of real numbers containing exactly two elements. Explain why A isbounded, 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.17Exercises to work . 1. Suppose that a and b are real numbers such that a < b. Prove that there are infinitely many rational numbers in the open interval (a, b).2. For an arbitrary base N, one has “base N decimal – like” expansions analogous to …
View Full Document