L I B RAR.Y
OF THE
U N I VERS ITY
or 1LL1 NOIS
<V 510.7 \S59
Digitized by the Internet Archive
in 2012 with funding from
University of Illinois Urbana-Champaign
http://www.archive.org/details/highschoolmathem07auniv
HIGH SCHOOL MATHEMATICS
Unit 7.
MATHEMATICAL INDUCTION
UNIVERSITY OF ILLINOIS COMMITTEE ON SCHOOL MATHEMATICS
MAX BEBERMAN, Director HERBERT E. VAUGHAN, Editor
UNIVERSITY OF ILLINOIS PRESS ■ URBANA, 1961
HIGH SCHOOL MATHEMATICS
Unit 7.
MATHEMATICAL INDUCTION
UNIVERSITY OF ILLINOIS COMMITTEE ON SCHOOL MATHEMATICS
MAX BEBERMAN, Director HERBERT E. VAUGHAN, Ed/for
UNIVERSITY OF ILLINOIS PRESS • URBANA, 1961
© 1961 by the Board of Trustees of the University of Illinois. Manufactured in the United States of America.
[7-iii]
PREFACE
In Unit 2 you formulated some of your knowledge about the real numbers in ten basic principles. [These principles are repeated on page 7-17 of the present unit.] You found, as you derived theorems from these basic principles, that the latter contained, at least implicitly, most of what you knew about the real numbers and, perhaps, some things you hadn't known. In this unit you will, for one thing, discover a few additional basic principles which you can use, as in Unit 2, to organize more of your knowledge about real numbers and to learn more about them. For example, you will discover simple basic principles which you can use to derive the transformation principles for inequations [see page 7-36] that you learned to use in Unit 3. Knowledge of these new basic principles will also help you to discover new things about inequations, and, in par- ticular, about the positive numbers.
The fact just mentioned- -that some of the new basic principles will imply new theorems about positive real numbers- -should remind you that the basic principles and theorems of Unit 2 formulate only properties which hold of all real numbers [or, in the case of division, of all nonzero real numbers]. Special kinds of real numbers --for two examples, the positive numbers and the positive integers - -have special properties which do not hold of all real numbers. For instance, although it is the case that between any two real numbers there is a third real number, there is no positive integer between, say, the positive integers 5 and 6. Among the new basic principles which you will discover in this unit there are some which will take account of the basic differences between the set of all real numbers and the set, I+, of positive integers. Using these you will be able to discover interesting properties peculiar to the positive integers. In particular, you will learn a special method--proof by mathe- matical induction- -for proving generalizations about positive integers. You will find this method of proof very useful, not only here, but in all your later work in mathematics. [Incidentally, you will find many opportunities in this, as well as in later units, to practice the techniques you learned in Unit 6 for writing column proofs and paragraph proofs.]
Just as the theorems you proved in Units 2 and 6 justified techniques which were helpful in applying your knowledge of real numbers and geometric figures to the solutions of various sorts of problems, so the theorems you learn in this unit will help in solving other kinds of prob- lems. However, as you should have learned by now, mere knowledge of the theorem which justifies a technique does not guarantee that one is adept at using the technique. Such techniques --simplification of algebraic expressions is an example- -must be practiced, both by themselves and as steps in the solutions of problems, if one is to learn to make good use of them. The Miscellaneous Exercises throughout this unit and the Review Exercises at the end furnish opportunity for the practice of both old and new techniques.
[7-v]
TABLE OF CONTENTS
Preface
[7-iii]
Introduction
Some problems
[7-1] [7-1]
7.01 The real numbers [7-3]
Addition [7-3]
The addition table [7-4]
Algorithm [7-4]
A proof of the theorem '2+2=4* [7-6]
Multiplication [7-7]
The multiplication table [7-7]
A proof of the theorem 42» 4 = 8' [7-9]
Miscellaneous Exercises [7-10]
Division-with-remainder algorithm [7-12] Using the division-with-remainder algorithm to find
the value of a function for a given argument [7-14]
Other computing facts [7-16] The 10 basic principles for real numbers used
in Unit 2 [7-17]
The eleventh basic principle: 1^0 [7-18] The notations '=^>* for conditionals and '<==>, for
biconditionais [7-19]
Miscellaneous Exercises [7-20]
7.02 The positive numbers
Basic principles (Px) and (P2) for the set of positive
numbers Closure principle, (P3)> for addition of positive
numbers Closure principle, (P4), for multiplication of
positive numbers
[7-22] [7-22] [7-23] [7-24]
[7-vi] [CONTENTS]
A principle, (N), which defines the negative numbers
Miscellaneous Exercises
Exploration Exercises --
Investigating the relation {(x, y) : y - x € P}
7. 03 Inequations
Basic principle (G) for the relation >
Inequality theorems
Two proofs of the theorem:
VVV [x + z > y + z => x > y] x y z l 3 7J
The inference scheme: — —M- +*
q=5> not p
The transformation principles for inequations
Addition; multiplication; factoring
Proving part of the factoring transformation principle
Inequality theorems on the squaring function
A geometric application of 'VXVV x2 + y2 > 2xy*
The reciprocating function
Inequality theorems on the reciprocating function
Monotonicity of functions
Graphing inequations on a number line picture
Systems of linear equations in two variables
Miscellaneous Exercises
Exploration Exercises --
Discovering whether a given set is an inductive set Proofs that 2, 3, and 4 belong to I*
7.04 The positive integers
Assumptions, used in Unit 4, about positive integers Defining the set of all positive integers Basic principles, I-+, l*t I* tor the positive integer Exercises on inductive sets Proofs by mathematical induction
7-25] 7-27]
7-29] 7-29]
7-30] 7-30] 7-32]
7-34]
7-35]
7-36] 7-36] 7-37] 7-38] 7-39] 7-39] 7-40] 7-41] 7-41] 7-42]
7-43]
7-45] 7-45] 7-46]
7-47] 7-47] 7-48] 7-49] 7-50] 7-51]
[CONTENTS] [7-vii]
A proof of 'V 3 + n € I+' by mathematical induction [7-51] r n
The principle of mathematical induction [PMI] [7-53] Inductive proof: initial step, inductive step
(using the inductive hypothesis), final step [7-53]
A short cut in writing inductive proofs [7-54]
Closure of I+ with respect to + and X [7-56]
Two methods for proving generalizations [7-56]
Combining both methods to prove * Vm Vn m + n e I+* [7-57]
Miscellaneous Exercises [7-59]
Reflection of a point with respect to a point [7-60]
Recursive definitions [7-61]
Computing triangular numbers [7-61]
Recursion--recursive definition [7-62]
The function T [7-62]
Explicit definition [7-62]
Square numbers --S [7-62]
Finding an explicit definition for T [7-63]
Proofs of 'Vn Tn = SjE + iT
Column [7-64]
Paragraph [7-65]
Tree-diagram [7-65]
Even and odd positive integers [7-66]
Finding that S is a function of T [7-66]
Practice with recursive definitions [7-68]
Compound interest formulas [7-68]
Graphing recursively defined functions [7-69]
Oblong numbers [7-69]
Pentagonal numbers --polygonal numbers [7-70]
A pattern for recursive definitions of polygonal
number functions --the notation: P [7-70]
n *• J
The number of p-membered subsets of an n-membered
set--the notations: C(n, p) and : C [7-71]
x tr' n p l J
Finding a recursive procedure for computing values
of lC(n, p)' [7-72]
Applications [7-74]
[7-viii]
[CONTENTS]
"The arithmetic of the positive integers [7-76] Recursive definitions, I4+, and I5+, for addition and
multiplication, respectively, of positive integers [7-76]
Derivation of the apa for positive integers from I4* [7-78]
Derivation of the cpa for positive integers from I4 [7-79]
Miscellaneous Exercises [7-80]
7.05 The relation greater than for the positive integers [7-84]
For each positive integer there is a next one:
V V [n>m=>n>m+l] [7-84]
m n L ~ J L J
Lower bounds and least members [7-87]
Definitions of 4a lower bound' and of *a least member' [7-87]
The least number theorem [for I+] [7-88]
The cofinality principle [7-89]
Exercises on bounds [7-90]
Misuses of induction [7-90]
Miscellaneous Exercises [7-91]
7.06 The integers [7-94]
A definition (I) for the set of integers [7-94] Closure theorems for integers : opposition, addition,
subtraction, and multiplication [7-95]
Exploration Exercises-- [7-96] Investigating the translating function, ti, which maps
each integer k onto k - j [7-96] Investigating the reflecting function, r:, which maps
each integer onto its opposite [7-97]
The least number theorem for integers [7-98]
Induction over {k: k>j} [7-100]
Induction over the set of all integers [7-100]
Miscellaneous Exercises [7-101]
The greatest integer function [7-102]
The notation '[ . . . ] * for 'the integral part of . . . * [7-102]
[CONTENTS) [7-ix]
{(x, y) : y = [xj} is called 4the greatest integer
function' [7-104]
A proof of ,VxVk [k = [x] <=> k < x < k + 1]' [7-104]
Division -with- remainder [7-106]
The least integer function [7-106] The notation '{{... J' for 'the fractional part of . . .' [7-107] {(x, y) : y = {[ x }} is called 'the fractional part
function' [7-107] ^Discovering a technique for "splitting'* each positive integer into multiples of powers of a given
integer > 1 [7-107]
Partial quotient and remainder [7-111]
Miscellaneous Exercises [7-112]
Divisibility [7-115] A theorem stating that j is transitive, and one stating
that | is antisymmetric [7-115]
The divisibility relation [7-116]
Similarities and differences between J and < [7-116] Examining the way in which | orders the positive
integers [7-117]
Prime numbers [7-118]
"^Highest common factor [7-119]
The symbols 'HCF' and 'GCD' [7-120]
Integral linear combinations [7-121] Euclid's algorithm for finding greatest common
divisors [7-123]
Exploration Exercises-- [7-125] Discovering whether a graph of a linear equation
contains a point with integral coordinates [7-125] Finding pairs of integers which satisfy a linear
equation [7-125]
Finding all integral solutions of '6x + lOy = 0' [7-125]
Diophantine problems [7-127] Finding all the integral solutions of a linear
equation in two variables [7-128]
[7-x] [CONTENTS]
Relatively prime integers [7-129]
Solving linear Diophantine equations [7-130]
Review Exercises [7-133]
Basic Principles and Theorems [7-145]
Basic principles for the real numbers [7-145]
Theorems from Unit 2 [7-145]
Basic principles for P--basic principle for > [7-149]
Theorems about > [7-149]
Basic principles for I+ [7-151]
Theorems about positive integers [7-151]
Cofinality principle and basic principle for I [7-152]
Theorems about integers [7-152] Definitions of the greatest integer function and the
fractional part function [7-153]
Theorems involving *|[ . . . J' and '| . . . }' [7-153]
Definition of the divisibility relation [7-153]
Theorems about | [7-153]
Table of Trigonometric Ratios [7-155]
Table of Squares and Square Roots [7-156]
[Introduction] [7-1]
Some problems. --Try to solve these problems:
I. Al Moore is trying to decide between two job offers. Each position starts at the rate of $4000 per year. The first offer promises a salary increase of $100 each six months. The second assures him of an annual increase of $400. If he plans on staying with one position for five years, which one will pay him more money?
II. Stan Brown also has a choice between two jobs. Each job is to last for 30 days. The first job pays $100 per day. The second job starts with 1 cent the first day, 2 cents the second day, 4 cents the third day, etc. doubling each day. Which job pays more? By how much?
III. Study the following sentences and complete the last two.
Vl + 3 = 2
Vl + 3 + 5 = 3
Vl + 3 + 5 + 7 = 4
Vl + 3 + 5 + 7 + 9 = 5
• • •
V1 + 3 + 5 + ... +87 = V1 + 3 + 5 + ... +999 =
IV. Study these sentences and complete the last one.
2<-L+J-+JL+_L<3 4<JL+JL + ..# + -L«
< 7 8 <
18 < — + — + ... + —i— < 19
|
VT |
Vz |
V3 |
VT |
|
JL + VT |
vr |
• • * |
+ -2_ VTe |
|
-L + VT |
-L + vr |
• • • |
+ » Vioo |
|
VT |
VI |
V? |
||
|
-L + VT |
-L + ... V2 |
V25 |
< |
9 |
|
-L + VT |
•n |
+ i ■fioi |
< |
Use the facts that VI = 1.414, V3 = 1.7 32, and VT = 2.236 to check that
2/5 -2< -i.+ J__+J_+JL+J-.< zJl . 1
VT VI V3 V4 VT
[7-2]
[Introduction]
V. You can easily check by computing that (1.0 1)2 > 1.02, ( 1. 0 I)3 > 1 . 03, and that (1.0 l)4 > 1.04. Do so. Do you think that ( 1. 0 l)100 > 2? That (1.05)100 > 6?
VI. You can probably expand '(x + y)2' without much thinking:
(x + y)2 = x2 + 2xy + y2 Other equations like this are below. Complete the last two.
(x + y)3 = x3 + 3x2y + 3xy2 + y3
(x + y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4
(x + y)5 =
(x + y)6 =
VII. Whatever route Milton takes in going from his home to Zabranch- burg High School he has to walk at least nine blocks. How many routes are there which are just nine blocks long?
|
r |
— — |
|||||||
|
i 1 |
L |
|||||||
|
r |
__ _ |
i .j |
||||||
|
i 1 |
||||||||
|
r |
_ — |
j |
||||||
|
1 |
| |
|||||||
|
l |
||||||||
|
-\ |
i i |
! |
||||||
|
J |
l/
HOME
Z.H.S.
You could certainly solve each of the foregoing problems by doing enough computation. But, as you will learn in this unit and the next one, there are easier ways.
Also, each problem suggests a generalization which you couldn't prove by any amount of computation. In fact, the proofs depend upon ad- ditional basic principles for real numbers which you will study in this unit.
[7.01] [7-3]
7.01 The real numbers. --If you were to write a proof of a theorem that tells you that the expanded form of 4(x + 2)2' is *x2 + 4x + 4', you would find yourself making use of basic principles, previously proved theorems, and computing facts such as that 2 + 2 = 4 and that 2*2 = 4. The theorems, of course, are consequences of the basic principles, but where do the computing facts come from? [There is a list of theorems on real num- bers starting on page 7- 145. The first 78 were proved in Unit 2.]
ADDITION
Statements of computing facts of the kind just referred to are conse- quences of the basic principles together with some obvious definitions. What you need to know is that the numeral '2* is merely an abbreviation for *1 + T, 43* is an abbreviation for '2 + 1', '4' for 43 + l\ . . . , and 4 10' is an abbreviation for '9 + 1*. And, as you have known since you first studied place value, '347', for example, is an abbreviation for *3« 102 + 4« 10 + 7\
Now, let's prove the theorem '2 + 2 = 4'.
2 + 2 = 2 + (l+l) [definition]
= (2 + 1) + 1 [apa]
= 3+1 [definition]
= 4 [definition]
In the same way, you can prove, in succession, *2 + 3 = 5*, 42 + 4 = 6', . . . , and 42 + 8 = 10'. Do so. If you try, in this way, to prove '2 + 9 = 11', you need an extra step, and a definition relating to place value:
2 + 9 = 2 + (8+1) = (2 + 8) + 1 = 10+1 = 1-10+1 = 11 A A A A A
definition apa theorem theorem definition
Which step is justified by a place value definition?
[7-4] [7.01]
In this same step-by-step manner you could establish any computing fact concerning sums of positive integers. For example, to prove *54 + 368 = 422' you would prove a sequence of theorems. First, you would prove '54 + 1 = 55'. Once you had proved this theorem, you would use it in proving 454 + 2 = 56'. Continuing in this way, you would eventually have proved *54 + 367 = 421', and would use this theorem in proving 454 + 368 = 422'. Each of your proofs would make use only of definitions [including place value], of the apa, and [except for the first proof] of the preceding theorem in the sequence, [instead of proving 368 theorems, you could get by with proving 54 theorems if you used an additional one of our basic principles for real numbers. Which one?]
Back in grade school you learned an easier way to establish this kind
of fact of arithmetic --that is, to add positive integers. You first learned
the sums of all pairs of the numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9~~
that is, you learned the addition table. Then, you learned how to use
this in adding larger numbers. For example, to add 675 and 237, you
placed the second numeral under the first and, after adding corresponding
digit numbers and "carrying'', you ended up with something like:
/ i
675 237
912
This procedure for finding the sum is an example of an algorithm. Al- though we shall not do so here, the steps you take in using this algorithm can be justified on the basis of place value definitions, the addition table, the cpa, the apa, and the dpma.
There is a similar algorithm for simplifying certain types of alge- braic expressions. Study the following examples of its use.
Example 1. Simplify: (3x3 + 2x - 7) + (2x3 + x + 5x2 - 9)
Solution. 3x + 2x - 7
2x3 + 5x2 + x - 9
5x3 + 5x2 + 3x - 16 [Explain how the principle for subtraction is used here.]
[7.01]
[7-5]
Example 2. Simplify: (a + 3b - c) + (a -
Solution.
5a + 2b
2c) - (b - 3a - 3c)
v ^ ;
Explain.
EXERCISES
A. Simplify.
1.
3.
5.
6.
7.
8.
9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
3a + 4b) + (7a + 9b) 2. (5x - 6y) + (7x + 3y)
-6t + s) + (-4t - 5s) 4. (-9c + 7d) + (3c - 7d)
8x - 3y) + (-2x + 3y) + (-6x + 5y)
y + 7z) + (5y - z) + (-9y - 3z)
5a - 6b + 8c) + (3a - 4b - 3c)
8x2 - 3x + 7) + (5x2 + 9x - 12)
7y2 - 3 + 6y) + (2 - 5y2 + 8y)
Ilk + 7m - 3n) + (8m - 2k + 4n)
5t2 - 3t + 7) - (2t2 + 8t - 5)
3x - 5) + (-2x + 3) + (2 - x)
3a - 7b) + (-2a + 5b) + (-a + 8b) + (4a - 6b)
3x2 + 7 - 5x) - (9 + 4x - 5x2)
8t3 - 3t + 7) + (9t2 - 5t3 + t) + (3t - 5t2 + 9)
lis4 - 3s2 + 9) + (5s2 - 4s4 + 11) - (3s4 - 7 - 2s2)
3a2 - 2ab + 3b2) - (-a2 - 5ab + 3b2)
y2 + 2y - 7) + (2y2 - 4y + 3) - (-8y - 10 + 3y2)
3x3 - 2x + 1) + (5x2 - 3x3 - 3) - (6x3 - 2) - (7x2 + 1 - 2x)
8a3 - 3a2b + 7ab2 - b3) + (9b3 - 3a2b + 7ab2 - 3a3) - (a3 - b3)
[7-6]
[7.01]
B.
Sample. If f(x) = 3x2 - 5x + 7, f(a) + f(3a) =
Solution. f(a) = 3a* - 5a + 7
f(3a) = 3(3a)2 - 5(3a) + 7 = 27a2 - 15a + 7 f(a) + f(3a) = 30a2 - 20a + 14
1. If f(x) = 4x2 - 8x - 3, f(2a) + f(a) =
2. If g(x) = 2x3 - x2 + 7, g(3x) - g(-x) =
3. If g(x) = x3 - x2 + 7, g(3x) = , 3g(x) =
[3g](x) = , [3o g](x) =
4. If f(x) = 7x2 + 2x + 9, f(3) = and f(10) =
5. If f(x) = 8x3 + 7x2 + 5x + 6 and g(x) = 4x2 + 3x + 9, f(10) + g(10) =
6. Suppose that, for each x, f(x) = x - 2x - 3. What is the slope of the line containing the points (2, f(2)) and (2 + h, f(2+h)), where
h ^ 0?
C_. Here is a column proof of the theorem '2 + 2 = 4'. Fill in the mar- ginal comments.
(1) V x = x x ' x
(2) 2+2=2+2
(3) 2 = 1 + 1
(4) 2 + 2 = 2 + (1 + 1)
(5) VxVyX + (y + 1) = (x + y) + 1
(6) 2 + (1 + 1) = (2 + 1) + 1
(7) 2 + 2 = (2 + 1) + 1
(8) 3=2+1
(9) 2+2=3+1
(10) 4 = 3+1
(11) 2 + 2=4
[7.01] [7-7]
MULTIPLICATION
Just as statements of the computing facts of addition are really theorems derivable from the basic principles and definitions of certain numerals and of place value, so are statements of the computing facts of multiplication. As an example, here is a proof of the theorem •2«3 = 6\
2*3 = 2(1 + 1 + 1) [definition]
= 2 • 1 + 2 • 1 + 2 • 1 [idpma]
= 2 + 2 + 2 [pml]
= 4 + 2 [addition table]
= 6 [addition table]
If we had previously proved that 2*2 = 4, we could have given a shorter proof. [Explain. ]
In filling out the rows of the addition table you could use the theorem:
V V x + (y + 1) = (x + y) + 1,
■*■ y
which is a consequence of the apa. In filling out a row in the multipli- cation table, the first entry is given by the pml and, to find the others it is convenient to use a theorem:
V V x(y +1) = xy + x x y w 7
[What basic principles do you need to refer to in order to prove this theorem?] For example,
2-4 = 2(3 + 1) [definition]
= 2*3 + 2 [theorem]
= 6 + 2 [theorem]
= 8 [addition table]
Now, prove 42- 5 = 10', '2-6 = 12', ..., andl2-9 = 18\
As in the case of addition, the multiplication table gives us theorems which are used in carrying out the steps in the multiplication algorithm which you learned in grade school.
[7-8]
[7.01]
Again, there is a similar algorithm for simplifying certain types of algebraic expressions. Study the following examples of its use.
Example 1. Simplify: (3x2 + 2x + l)(7x + 3)
Solution.
3x' + 2x + 1
7x + 3
9x2 + 6x + 3 Zlx3 + 14x2 + 7x
21x3 + 23x2 + 13x + 3
Example 2. Simplify: (5y - 3y + 2)(2y - 7)
Solution.
5yJ - 3y + 2
2
2/
- 7
- 35y* 10y5 - 6y3 + 4y2
+ 21y - 14
lOy5 - 41y3 + 4y2 + 21y - 14
EXERCISES
A. The procedure used in Example 1 above is like that used in multi- plying a 3 -digit number by a 2 -digit number. The procedure used in Example 2 is like multiplying a ( ? ) -digit number by a ( ? ) -digit number.
B^. Simplify.
1. (2t2 - 3t + 5)(5t + 3) 3. (8y2 - 3)(5y2 + y - 1) 5. (6b3 - 3b + 7)(4b + 5) 7. (8k + 2k3 - 3)(5 - 7k2) 9. (5 - 2x2 + 3x4)(7 + 5x)
2. (7x2 + 3x - 5)(-x + 7)
4. (2a2 - 3a + 7)(5a + 4a2 - 1)
6. (7r3 + 2r2 + r)(3r2 - 2)
8. (lis2 - s - 3)(2s2 + 3)
10. (8y3 - 2y + 7y2)(4y2 - y + 3)
[7.01]
[7-9]
11. (2x4 - 3x2 + l)(x - 4) 12. (3y2 - y - l)(2y2 - 2y - 1)
13. (-a3 - a2 + 2a)(a2 - a) 14. (~a4 - |a3 + a2
l)(fa3 - -U2 + 1)
15. [5(q - l)3 - 2(q - l)2 + 7(q - 1) - 8] [2<q - l)2 - 3(q - 1) + 7]
16. [3x(2x2 - x + 1) - 5x2(3x-2)][4x(x- 1) - 3x(2 -x)]
<3. Complete each of the following. 1. V ( )(2x) = 6x2 + lOx
2. V ( x x
3. V ( x
)(x + 2) = x3 + 2x2 + 3x + 6
)(4x + 1) = 20x3 + 17x2 + 19x + 4
D. Here is a column proof of the theorem '2 • 4 = 8'. Fill in the marginal comments.
(1)
(2)
(3) (4) (5) (6) (7) (8) (9) (10)
(11)
V x = x
X
2*4 = 2-4
3 + 1
2-4 = 2(3 + 1)
V V x(y +1) = xy + x x y 7 }
2(3+1) = 2-3 + 2
2-4 = 2 • 3 + 2 2-3=6 2-4 = 6+2 6 + 2 = 8 2-4 = 8
[7-10]
[7.01]
MISCELLANEOUS EXERCISES A. 1. If f(x) = 3x2 - 5x + 7 and g(x) = 2x2 + 3x - 5 then [fg](x)
2. If f(x) = 5x2 - 1 and g(x) = 3x - 7 then [fg](x) = and [gf](x) =
3. If f(x) = 4x2 + 2x - 3 and g(x) = 2x + 1 then [f° g](x) = and [g° f](x) =
B_. Simplify.
1. (x + 2)(x - 3) + (x + 7)(x - 5)
2. (y - 5)(y - 7) + (y - 3)(y + 5)
3. (2y - 4)(y + 8) + (3y - 7)(2y + 5)
4. (a - 2b)(3a + b) + (7a - b)(5a + 3b)
5. (3x - y)(2x + 5y) - (6x + y)(3x + y)
6. (7x - 4)(15x - 9) - (8x + 5)(13x - 7)
7. (5y - 7)(y+ 3) + (5y - 7)(y - 3)
8. (2x + 3y)(2x + 7y) - (2x + 3y)(x - 4y)
9. (3x - 4y)(x - 2y) - (4y - 3x)(3x + 5y) 10. (5a - 2b)(7a - 3b) + (3b - 7a)(5a - 2b)
C. 1
If the perimeter of this rectangle is 34, what is the area-measure?
5x + 2
i
If the area-measure of this rectangle is 33, what is the perimeter?
3x + 5
3. Find the measures of the diagonals of the rectangles in Exer- cises 1 and 2.
[7.01]
[7-11]
D. Simplify.
1. (x - 4)(x - 7)(x + 2)(x - 3)
3. (a + l)(a + 2)(a + 3)(a + 4)
5. (a - 6)(a + 7)(a - 8)(a + 9)
2. (y - 3)(y + 8)(y - 2)(y + 6) 4. (b + 2)(b - 2)(b + 3)(b - 3) 6. (2x - l)(3x - 7)(5x - 3)(4x + 7)
E. 1. Suppose that f(x) = 3x3 - 5x2 - 2x + 8. Compute f(2), f(-2), £(j), f(l), f(0), f(-|), and £(0.05).
2. Suppose that g(x) = 5x4 - 3x + x - x + 1. Compute g(6), g(~5), and g(9).
F_. Replace the letters by digits.
1. 1ABCDE * 3
ABCDE1
2. SEND
+ MORE
MONEY
G. Solve these problems.
1. The weight of a circular disc varies jointly as the square of the radius and the thickness. If the ratio of the thicknesses of two discs is 9 to 8 and if the weight of the first disc is twice that of the second, what is the ratio of their radii?
2. Two numbers are in the ratio 5 to 37. What number should be added to each so that the sums are in the ratio 1 to 3 ?
3. Find three consecutive even numbers whose sum is 204.
4. How many pounds of a 12% salt solution are required to yield 84 pounds of salt ?
5. A printer used 1890 digits in numbering the pages of a certain book. How many pages are in the book?
6. Prove that none of the numbers 11, 111, 1111, 11111, ... is the square of an integer.
[7-12]
[7.01]
DIVISION-WITH-REMAINDER ALGORITHM
The addition, subtraction, and multiplication algorithms are pro- cedures for simplifying indicated sums, differences, and products of positive integers named by decimal numerals. We can extend these algorithms to apply to all integers by taking account of various theorems about opposites.
The situation with division is not so simple. Subtraction, which in some ways is analogous to division, always "comes out even". But, as you know, division doesn't. In earlier grades you learned an algorithm for finding the quotient of a first number by a second when the second is a factor of the first. Take the example of simplifying '867 t 17'.
|
51 |
|||
|
17/867 |
|||
|
1 |
50-17 = |
I 850 17 |
|
|
1 • 17 = |
I 17 |
||
|
867 |
= 51-17 |
1 0 |
The content of the dashed box suggests what is behind the algorithm. The algorithm shows that 867 - 50 • 17 - 1 • 17 = 0. So, 867 = 50 • 17 + 1 • 17 = 51 • 17.
As you know, this algorithm can still be used to yield important information in cases in which the quotient is not an integer. Look at this example :
51
r
|
17/868 |
|
|
50-17 = |
850 |
|
18 |
|
|
1 • 17 = |
17 |
868 = 51 • 17 +
L--n
868
The result of applying the algorithm in this example shows us that — r=
868
is not an integer. More specifically, it tells us that . _ is between the
86 8 1
integers 51 and 52, Further, it tells us that . ^ differs from 51 by y=-
All this information is conveyed by the equation 4868 = 51-17 + 1*.
[7.01]
[7-13]
In fact, the purpose of the algorithm is to arrive at just such an equation So, the algorithm is called the division-with-remainder algorithm.
This algorithm has an analogue used for transforming certain alge- braic expressions. For example, consider the expression:
20x3 + 17x2 + 19x + 6
and the problem of transforming it to an expression of the form:
( )(4x+ 1) +(__.)
Here is a way of finding expressions to fill the blanks:
5x2 + 3x + 4
4x + 1 /20x3 + 17x2 + 19x + 6
5x2(4x + 1) =! 20x3 + 5x2
3x(4x + 1) =
4(4x + 1) =
1 2x2 + 1 9x 12x2 + 3x
I6x + 6 I6x + 4
20x3 + 17x2 + 19x + 6 = (5x2 + 3x+4)(4x + 1) +
"2_n
Let's do another problem:
V 5x4+ 2x2 + 3x + 5 = (_?_)(x - 3) + (_?_)
5x3 + 15x2 + 47x + 144
- 3/5x'
+ 2x2 +
3x +
5x4 - 15x:
15xJ + 2x^ 15x3 - 45x2
47 x2 +
3x
47x,: - 141x
144x + 5 144x - 432
437
So, V 5x4 + 2x2 + 3x + 5 = (5x3 + 1 5x2 + 47 x + 144)(x - 3) + 437.
[7-14] [7.01]
EXERCISES
A. Use the division-with-remainder algorithm to complete the following sentences.
1. 379 = -15+ 2. 5032 = • 28 +
3. V 2x3 + x2 + x + 16 = ( )(x + 2) + (_ _)
4. V 15x4 + 5x3 - 3x2 + llx + 4 = ( )(3x+l) + (_ _)
5. V 6x4 + 17x2 + 7x + 25 = ( )( 2x2 - 2x + 5) + ( _ _)
6. V 3x4 - 8x3 - 7x + 2 = ( )(x2 + 2x - 5) + ( )
7. V x4 - 2x2 - 35 = ( )(x2 - 7) + ( )
8. V 27x3 + 64 = ( )(3x+4) + ( )
9. V x3 - 8 - 6x2 + 12x = ( )(x - 2) + ( )
J^ ■ ' ' ' "" ™ ™ ™"
10. V 2x4 - 3x + 7 = ( )(x - 5) + ( )
J^ ' ' "■ ™ " ~
11. V 2x4 - 3x + 7 = ( )(x + 4) + ( )
vU vO *«,
•"l" *"l% *v
The second example on page 7-13 told us that, for each x,
(*) 5x4 + 2x2 + 3x + 5 = (5x3 + 15x2 + 47x + 144)(x - 3) + 437.
Suppose that f is a function such that f(x) = 5x4 + 2x2 + 3x + 5, and sup- pose that we wish to find f(3). One way to do this is to substitute *3* for 4x' in the expression '5x4 + 2x2 + 3x + 5' and then simplify. Another way is to use (*). Do you see how?
Now, suppose that we wish to find f(-7). We can use the division- with-remainder algorithm to show that, for each x,
5x4 + 2x2 + 3x + 5 = (5x3 - 35x2 + 247x - 1726)(x + 7) + 12087
From this it is easy to see that f(-7) = 12087.
o^ O, vi. ,,x ^x ,t>
[7.01]
[7-15]
B. 1. Suppose that f(x) = 6x4 + 2x3 - I6x2 - lOx + 1. Use the division- with-remainder algorithm to compute f(2), f(6), f(-7), and f(2/3)
2.
(a) Suppose that g(x) = x4 - 14x3 + 71x2 - 154x + 120. Use the division-with-remainder algorithm to compute g(2), g(3), g(4), and g(5).
(b) Solve the equation 4x4 - 14x3 + 71x2 - 154x + 120 = 0'.
3. Show that 4x - 5' is a factor of 4x3 - 9x2 + 23x - 15'. You could
use the division-with-remainder algorithm. [If 4x - 5* is a factor, what would the remainder be?] Do the problem a different way.
4. Show that 4x2 + x - 2' is a factor of 4x5 - x4 + 9x2 - 7x - 2'.
5.
Which of the following fractions can be reduced to lower terms?
(a) (c) (e)
|
(x |
+ 5)(x |
- 2) |
|
|
x - 2 |
|||
|
x2 |
+ 4x - |
21 |
|
|
X2 |
+ x - |
12 |
|
|
X3 |
- 6x2 - |
• 7x + |
60 |
x* - 3x - 18
(b) (d) (f)
x2 + 7x - 18 x - 2
x2 + lOx - 21 x2 - 7x + 12
x2 - 2x - 3 x3 + 3x2 - 25x + 21
C. 1. If an edge of cube is 3x - 2 inches long, then the surface area is square inches and the volume is cubic inches.
2. If the surface area of a cube is ( 3x + 12)(2x + 8) square inches, what is its volume?
3.
If the volume of the pictured rectangular solid is 2x3 + x2 - 8x + 21 cubic feet, what is the area of the shaded face?
4. If the volume of a cube is x3 - 1 5x2 + 75x - 125 cubic inches, how long is a diagonal of a face? How long is a diagonal of the cube?
[7-16] [7.01]
OTHER COMPUTING FACTS
In order to establish a computing fact such as, for example, that
5 5
j- • 2 = -_-, we use the principle of quotients and the division theorem.
Here is a column proof:
(1) V V V xyz = x(yz) [apml
Xyz Lr-j
(2) |*2"3 = |(2'3) [(!)]
(3) 2*3 = 6 [theorem]
(4) VxVy^0 7^ = X fp^
(5) 6/0 [ ? ]
(6) | -6 = 5 [(4) and (5)]
(7) |-2"3 = 5 I<2>' <3>' a^d(6)]
(8) VV / rt V if zv = x then z = — [theoreml
xy/Oz y
(9) 3/0 [ ? ]
(10) if |- • 2 • 3 = 5 then | • 2 = |- [(8) and (9)]
(11) |-2 = | [(7) and (10)]
In the foregoing proof, in addition to basic principles [apm and pq] and theorems derived from them ['2 • 3 = 6' and the division theorem], we used some inequations ['6 / 0' and '3 / 0']. Similarly, in Unit 2, in proving the important theorems:
V -r- = x and: V — r = -x, x 1 x - 1
we used 41 /. 0' and ' — 1 / 0'. Now, it is easy to see that none of these
inequations can be derived from our ten basic principles. All you need
do is to imagine there are no real numbers except 0, and that '1' is just
another name for 0. Nov/, look at each of the ten basic principles:
[7.01]
[7-17]
Commutative principles
VV x + y = y + x x y '
V V xy = yx x y 7 7
Associative principles
V V V x + y+z = x + (y+z) x y z ' 7
V V V xyz = x(yz) xyz7 7
Distributive principle
V V V (x + y)z = xz + yz xyz 7 7
Principles for 0 and 1
V x + 0 = x x
V x • 1 = x
X
Principle of opposites
V x + -x = 0 x
Principle for subtraction
VV x-y = x+ — y x y 7 '
Principle of quotients : y^O
VV / „ (x t y) • y = x
Since 0 + 0 = 0 + 0 and 0*0 = 0 '0, the commutative principles are certainly true for the number system you are imagining.
If you also imagine, as definitions of addition and multiplication, that 0 + 0 = 0 and 0*0 = 0 then you can check at once that the associative principles and the distributive principle also hold.
Remembering that *1' is, for the moment, just another name for 0, you see that the principles for 0 and 1 also hold.
Defining oppositing and subtracting by: -0 = 0, and: 0-0 = 0/ you see that the principle of opposites and the principle for subtraction hold.
Finally, since there aren't any numbers except 0, the principle of quotients is true, too. [If you don't believe this, try to find a counter- example! ]
Now, if we could prove from the ten basic principles that, for example, 1^0 then, since the basic principles are true for your imagined number system, 41 / 0' would also have to be true of this system. But, it isn't.
[7-18]
[7.01]
So, if we want to have enough basic principles to reaLly prove all the theorems of Unit 2, we should add, at least, 41 / 0' to our list of basic principles. [We have left space below the pml on page 7-17 so you can do this. Do it now.]
How about the other inequations? For example, do we need to take 4-l / 0' as a basic principle? The answer to this question is 'no'; we can prove :
|
Theorem 79. |
|
|
V if x i 0 then X |
-x ^ 0 |
[From this and the basic principle '1 fi 0' it follows that -1^0. Why?]
(1) (2) (3) (4) (5) (6)
(7)
(8)
(9)
(10)
(11)
(12)
-a = 0
V x = x
X
*
a + -a = a + -a a + 0 = a + -a
V x + 0 = x x
a + 0 = a
V x + -x = 0 x
a + -a = 0 a = 0 if -a = 0 then a = 0 if a fi 0 then -a £ 0 V if x £ 0 then -x / 0
[assumption]: [Identity]
[(2)1
[(1) and (3)]
[paO]
[(5)]
[po]
r'.7)]
[(4), (6), and (8)]
[(9); *(D]
[(10)]
[(H)]
You can also derive Theorem 80 ['-0 = 01] from our eleven basic principles. Do this now.
Notice that Theorem 79 is equivalent to:
V if -x = 0 then x = 0, x
and that Theorem 80 is equivalent to:
V if x = 0 then -x = 0 x
[7.01] [7-19]
[To see this last equivalence, note that '-0=0' can be deduced from
'V if x = 0 then -x = 0' and the principle of identity. And, on the other x
hand, notice that from the assumption 'a = 0' and the theorem 4-0 = 0' one can infer '-a = 0'. Complete the derivation of 4V if x = 0 then -x = 0' from 4-0=0'.] So, Theorem 79 and Theorem 80 can be combined into a single statement:
(*) • V [x = 0 if and only if -x = 0]
Ox Ox Ox
'i^ T *V
In writing conditional and biconditional sentences we shall find it
convenient to abbreviate the connectives 'if ... then ' and 4. . . if and
only if ' by 4. . . '==> ' and 4. . . <^^> ', respectively. Thus,
Theorem 79 can be written:
V [x / 0 ^ -x / 0]
x L /J
and (*) can be written:
V [x = 0 <=> -x = 0] x L J
The brackets indicate the scope of the quantifier. Why aren't brackets
necessary when we use the 4if ... then ' notation?
Of course, whichever way you write Theorem 79, you still read it
as 'for each x, if x is not 0 then the opposite of x is not 0'. If it is
written with the i^=^>\ it is sometimes convenient to read it as 4for each
x, x is not 0 only if the opposite of x is not 0'.
Ox O, Ox "C "Is "JN
Our eleven basic principles are enough to justify the first 80 theo- rems on pages 7-145 through 7- 149. However, it is not possible to prove, from these alone, that 2^0, [You can show this impossibility by the same kind of argument we used to show that 41 p 0' cannot be derived from the ten basic principles of Unit 2. Imagine that there are no real numbers other than 0 and 1 and that 0 -f 1 . Then, define addition, multiplication, opposition, subtraction, and division in a "natural" way. (Hint : Let 1 + 1=0.) Now, show that all eleven basic principles are true statements.]
Since, for the real numbers, Z f- 0 , it follows that we need more basic principles. In the next section we shall introduce additional basic principles which will enable us to prove not only '2 £ 0', '3 fi 0', etc., but will also give us a basis for proving theorems about the relation >.
[7-20] [7.01]
MISCELLANEOUS EXERCISES
A. Expand and simplify.
1. (5a + b)(5a-b) 2. (x + 7)(x + 8) 3. (y + 9)(y + 9)
4. (y + 9)(y - 9) 5. (3x - 4)2 6. (3z - 4)(3z + 4)
7. (3z + 4)2 8. (7a+2)(5a-6) 9. (ax + b)(ax - c)
10. [(a - b) + c][(a - b) - c] 1 1 . [x - y + z][x - y - z]
12. 5pq(p2 - pq - q2) 13. 7x2y3(x4 - x2y + y4)
14. (2a - 3b)(5a2 - 2ab + 7b2) 15. (3x2 - 2x + l)(5x2 - 7x - 2)
B. Simplify.
1. 81-53+81-47 2. 93-67 + 67-7 3. 8-19*12i
4. (7-33-j) -(9-3) 5. 12 • 87 i + 12j • 12 6. ( 1 1 • 16 |) • (5 • 6)
C. Simplify.
x - 3 2_ x + 4 5_ 8 y - 1
x+8x x - 3 x 'yy+2
4. ^ 7 x + 1 x - 3 , x - 4 x - 5
*x-4 x+5 'x+4 x - 5 *x+4 x+5
7 x + Z + x - 8 8 2x~ 3 + 3x~ 7 q 7y + 3 + 3y - 2
*x-5 x+5 *5x+l 5x-l y-2 3y - 6
5x2y3 7a3b „ 3m3n3 8pg4 8(a - b)3 v 3(a + b)4
1U* 3ab2 8xy4 L1" 2p2q3 * 12mn4 **' 9(a + b)* 2(a - bp
(x- 3)(x +5) y(x.- 7)(x - 5) x2 + 2x- 15 x2 - 12x + 35
(x + 4)(x- 5) (x- 5)(x + 5) x* - x - 20 x2 + 2x - 15
IS x2 - x - 12 x2 + 2x - 15 ., 6x2 + 7x - 5 32x2 - 12x+ 1
x2 + 3x- 10 x^ + 7x + 12 b* 16x2 - 26x + 3 12x2+ 17x-5
17 x2 - 5 x + 1 x - 4 R x2 - 5 2x+ 1 5x - 3
* (x- 3)(x- 2) x - 3 x- 2 x2 - 5x + 6 " x - 3 x - 2
[7.01] [7-21]
ia 3x2 + x - 1 4x + 1 2x-7 . 5x+7 2 x2 - 3x - 7
19' x2 + 5x - 24 " ~x~^8~ + ~ZTT CK)- 3x - 3 x - 9 " x* - 10x + 9
xz + 1 8x + 3 4x+8 ?? x2 + 4x- 21 x2 4 3x - 10
Z1" 2x2 + 7x- 15 " x + 5 8x- 12 "" x* + llx +28 x2 + 9x+20
23. (x. *+*)-<*£!. y) 24. (5-^l + (7-^)
|
£. X |
a |
- 1 |
|
2a- |
-i |
- 1 |
|
a • |
.1 |
8 x + y a - 1 x + 2 x + 3
D. Solve each system of equations.
1. x - y = 2 ^ 2. 4x + 3y = 10 ^ 3. x + 3y = 5 ^ 2x + y = 5 J 2x - 2y = 5 J 2x + 4y = 7
4. 2x - y = 5 ^ 5. 3x - 2y = 5 ^ 6. 2x - y = -2
2x - 3y = 5 J 6x-4y = 9 J 5x + 1 = -2y
E. 1. Find two consecutive integers the difference between whose squares
is 23.
2. If A can do a certain job in 6 days, and if B can do it in 8 days, how long will it take them working together?
3. Mr. Allen drives to Zabranchburg--a 100-mile trip- -at 45 miles per hour. In order to average 55 miles per hour for the entire trip, how fast should he drive during the return trip?
4. Bill has an average grade of 74 after the first two tests. To bring his average up to 80, what must he get on the third test?
5. A car travels north at 45 miles per hour, and 2 hours later another car leaves the same place and travels north at 55 miles per hour. How long will it take the second car to pass the first?
6. Rectangle A is 14 feet longer than it is wide. Rectangle B is 4 feet smaller in width but 16 feet longer in length. If the rec- tangles have the same area, what is it?
7. Given a circle of radius 10. Is the measure, i, of a chord of this circle a function of its distance, d, from the center- -that is, is there a function f such that i = f «d? If so, give such an f.
[7-22] [7.02]
7.0 2 The positive numbers. --We concluded the last section by pointing out that our eleven basic principles for real numbers are not sufficient to prove, among other things, that 2/^0. Evidently, we need more basic principles. Let's find some by trying to prove that 2^0.
Now, by definition, this amounts to proving that 1 + 1^0. Since, by the principle of opposites and the 0-sum theorem, 1 + 1 = 0 if and only if -1 = 1, what we need to prove is that -1^1. [Explain.]
One way to see that -1 and 1 are different is to recall that -1 = "1 and, of course, that 1 = *1. So, -1 is a negative number, and 1 is a positive number. Hence, since the same number cannot be both positive and negative, 1 and -1 are not the same number --that is, -1^1.
Now, several of the things we said in the last paragraph suggest that in proving that -1/^1 [and, so, that 2^0] it will be useful to have some basic principles which deal with positive and negative numbers. Actually, we may as well concentrate on the set P of positive numbers since we can, if we need to, define the set N of negative numbers to consist of the opposites of the members of P. What we need to express in the new basic principles is how the operation oppositing and the property of being positive are related. The following two basic principles do this.
(Px ) V [x ^ 0 => either x € P or -x € P]
(P0 ) V not both x e P and -x e P
Basic principle (Px) says that, no matter what nonzero real number you pick, either it or its opposite is positive. What does basic principle (P2) say?
Using (Px) and (P2), and the basic principle '1 j£ 0', it is easy to prove that -1^1. For, since 1^0, it follows from (Px ) that either 1 € P or -1 e P. But, this being so, if - 1 = 1 then both 1 e P and -1 € P. By (P2), this is not the case. Hence, -1^1.
Since -1 ■£■ 1, it follows from the 0-sum theorem that 1 + 1/^0. That is, 2^0.
However, even with (Pjl) and (P2), we cannot prove that 3^0. But, it seems likely that we are on the right track, and that what we need are more basic principles about the set P. For example, we could prove that 3 ^ 0 if we could show that 3 e P and 0 ^ P. Now, we can prove that
[7.02]
[7-23]
0 i P. This follows from (P2) and the theorem [Theorem 80] that -0=0. So, we have:
Theorem 81.
0 4 P
Let's see how we might show that 3 e P.
By definition, 3 = 2+1. Also, as you probably recall, the sum of two positive numbers is a positive number. If we adopt this as another basic principle then we can show that 2 + 1 e P by showing that 2 e P and 1 6 P. So, as a third basic principle for P we shall take:
(P3) V V [(x € P and y e P) ==> x + y e P]
Now, let's tackle the job of showing that 2 e P and that 1 6 P.
Evidently, using (P3) you can prove that 2 e P once you have proved that 1 e P. [Explain.] So, our only problem is that of proving:
Theorem 82. 1 6 P
Do we know enough basic principles to prove this? We can see that we don't by noticing that if, in each of the principles (P^, (P2)» and (P3)» we replace 4P' by *N\ we get true statements, (Nx), (N2), and (N3), about the set of negative numbers. Now, if we could derive '1 e P' from (P^, (P2)» and (P3), and our eleven other basic principles, then we could, in just the same way, derive 41 e N' from (N1), (N2), and (N3), and our eleven other basic principles. Since 1 is not a negative number, we can't do this .
Our trouble is that none of the basic principles which we have accepted really distinguishes between positive numbers and negative numbers. We need a basic principle which states some property of P which is not also a property of N. What haven't we considered? The most obvious omission, so far, is any consideration of multiplication- - and, with respect to multiplication there is a difference between P and N. The set P is closed with respect to multiplication, but the set N is not. So, let's take the following as a fourth basic principle for P:
[7-24] [7.02]
(P4) VxVy [(xe P andyeP) => xyeP]
Now we can prove Theorem 82. Here is a proof:
Since 1/^0, it follows from (P1) that either 1 e P or -1 e P. Sup- pose that -1 e P. Then, by (P4), -1 • -1 e P. But, by Theorem 23 and the pml, -1 • -1 = 1*1 = 1. So, if -1 € P then 1 e P. Since either 1 6 P or - 1 eP and since, as we have just shown, if - 1 e P then 1 6 P, it follows that, in any case, 1 e P.
So, we have proved that 1 e P. Now [using definitions and (P3)] it is easy to prove that 2 e P, 3 e P, 4 € P, etc. [Incidentally, we can use (P2) to show that -1 f( P.] In addition, using Theorem 81, we have a new proof that 2^0, and can prove '3 ^ 0', '4 fi 0', etc.
We can also prove theorems like '5 £ 2'. For, if 5 = 2 then 5-2 = 0. But, 5 - 2 = (3 + 2) - 2 and, by Theorem 30, (3 + 2) - 2 = 3. So, if 5 = 2 then 3 = 0. Since 3 / 0, it follows that 5/^2.
'2 *
We can also prove theorems like -=- ^ 0 . The key theorem here is
Theorem 54:
VV ,[^ = 0=>x = 0]
x y t o y
? 2
Since 3^0, it follows that if j = 0 then 2 = 0. But, 2^0. So, j ^ 0.
EXERCISES
A. 1. In proving the theorem 45 fi 2' we used the theorem:
*** VxVy tx = y=^ ^ - y = 0]
Prove (*) by first proving 'V x - x = 0*.
2. Prove the converse of (*).
B. Prove each of the following.
1. 4 e P 2. If 3 3. -j £ 1
4. No positive number is its own opposite.
5. P is not closed with respect to subtraction.
[7.02] [7-25]
C. Prove the following theorems.
Sample 1. V V [(x e P and y e P) => x2 + 2xy + y2 e P] x y
Solution. Suppose that a € P and b e P. By (P3), a + b € P.
So, by (P4), (a + b)2 e P. But, (a + b)2 = a2 + 2ab + b2. Hence, a2 + 2ab + b2 € P. So, if a e P and b e P then a2 + 2ab + b2 e P. Consequently,
V V [(x e P and y e P) => x2 + 2xy + y2 e P]. x y
1. V V [(x-yeP and y e P) => x e P] [Hint. Look at Theorem 32. ]
2. V V [(x - y e P and y e P) => x2 - y2 e P]
Sample 2. V V [x ^ y ==> either x-yeP or y-xeP] x y
Solution. Suppose that a fi b. Then a - b fi 0 [Why?] and, by (Px), either a - b e P or -{a - b) e P. But, by Theorem 33, -(a - b) = b - a. Hence, if a ^ b then either a - b 6 P or b • a £ P, Consequently,
V V [x ^ y => either x-yePory -xeP]. x y
3. V V not both x - y e P and y - x e P
x y J J
4. V V V [(x - y e P and y-zeP)=>x-zeP]
5. V V V [x - y e P => (x + z) - (y + z) € P] x y z ' w J
6. V V V [(z € P and x - y e P) =£> xz - yz e Pi x y z L 7 7 J
«.•- vl- k",
*.,% '»^ -V
We have defined the negative numbers to be the opposites of the pos- itive numbers. If we are to prove theorems about the set N of negative numbers it is convenient to incorporate this definition in a basic principle
[7-26] [7.02]
(N) V [-xeN <=> x € P]
We shall not include (N) in our "official" set of basic principles. How- ever, you will be asked to prove some theorems about the set N in the next set of exercises, and for these proofs you will need to use (N) as a basic principle.
vl- o^ o^
^,x ^,<s ,,v
D. Prove each of the following.
1. V [xe N <=> -xe P] x L J
Sample. V [x £ 0 => either x e P or x e N]
Solution.
(1) V [x £ 0 => either x € P or -xe P] [basic principle]
(2) a / 0 => either a e P or -a € P [(1)]
(3) V xeN <=> -x e P [theorem--Ex. 1]
(4) ae N <=> -aeP [(3)]
(5) a £ 0 ^=> either a e P or a e N [(2) and (4)]
(6) V [x/0=> eitherxePorxeN] [(1) - (5)]
x
[Note that step (5) follows from step (4) and step (2) by virtue of the substitution rule for biconditional sentences. This principle of logic tells us that, given a biconditional sentence [(4)] and a second sentence [(2)], if either component of the biconditional sentence [in this case, the component 4-a e P'] is replaced by its other compon- ent ['a e N'] in the second sentence, the new sentence so obtained [(5)] is a consequence of the given sentences [(4) and (2)].]
Here is a paragraph proof for the same theorem:
Since, by (PL), if a -f 0 then either a e P or -a e P, and, since -a e P if and only if a e N, it follows that if a fi 0 then either a e P or a e N. Consequently, V [x £ 0 => either x e P or x e N].
[7.02]
[7-27]
2. V not both x e P and x € N x
3. V [x £ 0 => either x e N or -x € N]
4. V not both x e N and -x e N x
5. V V [(x e N and y e N) => x + yeN]
6. V V [(x € N and y£N)=> xy 6 P]
7. V [x f 0 => x2 e P]
MISCELLANEOUS EXERCISES
A. 1.
2.
3.
4.
5.
6.
7.
8.
9. 10. 11. 12. 13.
f g(x) = x2 - 3x - 28 then g(17) = , g(27) = , and g(6) = .
f f(x) = (x - 7)(x + 4) then f( 17) = , f(27) = , and f(6) =
f h(x) = x2 + x - 30 then h(15) = , h(-6) = , and h(35) =
f f((x, y)) = 6x2 - y2 then f(3, 2) = and f(2, 3) =
i g(x, y) = {-^ - ^- then g(3, 2) = and g(2, 3) = .
f h(x, y) = (5x2) - (5 + x)2 + xy2 then h(3, 2) = and h(2, 3) =
f f(a, b, c) = -3ab + 5a2c then f(-4, -12, 3) =
f g(a, b, c) = 18 - a - 6c + 2ab then g(-4, -12, 3) =
f h(m, n) = mn2 + m2n then h(3, -6) =
£ f(x) = 3(x - 2)(x + 2) - 4(x2 - 5) + (x - 8)(x + 1) then f(-5) =
f f(x) = 8X then f(l) = , f(2) = , and f(3) =
13 1
£ g^X* = x~^2 + x~^T then Si1) = » g(3) » and g( j) =
f f(x) = x2 + 1 and g(x) = 9 - x2 then for what argument do f and g have the same value?
[7-28] [7.02]
B. Tell which expressions are equivalent to the given one.
1. mx + my + nx + ny
(A) (m + n)(x + y) (B) m(x + y) + (x + y)n ( C) m(y + n) + x(m + y)
2. xy + 3x
(A) y(x + 3) (B) x(y + 3) (C) x(y + 2) + x
3. xy + xz + yz
(A) x(y + z) + yz (B) y(x + z) + xz (C) x(y + z + x)
4. T + Ts
(A) T(l + s) (B) s(l + T) (C) (T + 1)(1 + s)
5. y(l + x)2 + y(l + x)2x
(A) y(l + x)3 (B) y(l + x)( 1 + x2) (C) yx + y( 1 + x)3
6. Kk - K
(A) k(K - 1) (B) K(k - 1) (C) k(K - 1) + k - K
7. tx - ty + sx - sy
(A) (t - s)(x + y) (B) (t + s)(x - y) ( C) (t + x)(s - y)
8. xy - xz + yz
(A) x(y - z) + yz (B) z(x - y) + xy (C) -y( -x - z) - xz
C. Compute.
1. 23 -32 2. 89 -f 87 3. (-3)2- (-2);
4. (23)4-r 2U 5. 2-32 6. 5 + 2- 3Z
_D. True-or -false ?
1. 32 + 33 = 35 2. 32 + 33 = 65 3. 32 • 33 = 36
4. 32-33 = 95 5. 38 ~ 32 = 34 6. (34)2=36
[7.01]
[7-29]
E. Solve these equations. 1 . 5x - 2 + 7( 3 - x) = 1 2
3. x + 2(5x - 1) = -x - 3
2. 2 - (1 - x) + 7x = 5 - 3(x - 6)
4. 6 + (x - 3)2 = (x + l)2 - 2
F. 1. Draw a square and mark a point in its plane. Draw a line
through this point such that the line cuts the square region into regions of equal area-measure.
2. Repeat Exercise 1 for a regular hexagon.
3. Given an equilateral triangle AABC. Find the radius of the cir- cular arc with center at A which bisects the triangular region.
4. Draw a square ABCD and draw perpendicular lines Jt and m such that & intersects each of a pair of opposite sides and m intersects each of the other pair of opposite sides. Show that the segment of i determined by the intersection points is congruent to the segment of m determined by m's intersection points.
5. Two players at a circular table take turns in putting pennies on the table. The pennies may touch but not overlap. The loser is the player who can't find a place to put down a penny. The first player can always win. How?
6. Remove two opposite corner squares from a chessboard. Can the remainder of the board be covered without overlapping by
• rectangular cards, each card covering exactly two squares?
EXPLORATION EXERCISES 1. Graph the sentence ly - x e P' on a picture of the number plane
2. What name is customarily given to the relation {(x, y) : y - x e P} which you pictured in Exercise 1?
[7-30]
[7.03]
7.0 3 Inequations. --The principles (P1), (P2), (p3)> a^d (P4) for the set P of positive numbers are also basic for establishing theorems about the relation >. In fact, you may recall from your work in Unit 2 that we defined 4>' by:
(G) V V [y> x <=> y - xeP] x y
We shall now accept (G) as a new basic principle.
(G) tells us what is meant by statements of inequality such as '7 > 2* and '5 > 9'. The statement 47 > 2' is just another way of saying that 7 - 2 is a positive number. Similarly, '5 > 9' is another way of saying that 5 - 9 is a positive number. [Since 7 - 2 is a positive number, we know that 47 > 2' is true. How about '5 > 9'?]
Of course, since the relation < is merely the converse of >, we could get along without the symbol '<'. However, we shall use it occa- sionally. When we do, you should think of a sentence of the form '. . . < 'as merely another way of writing one of the form ' > . . . *
[Similarly, a sentence of the form '. . . > ' is just an abbreviation for
one of the form ' . . . > or . . . = ' . ]
Another thing that (G) tells us is that the real numbers which are greater than 0 are precisely the positive numbers. We state this as:
|
Theorem 83. |
x e P] |
|
|
V x > 0 <^ x u |
— > |
Do you see how to derive Theorem 83 from our basic principles? Try to do so before reading the column-proof which follows.
=> y - x € P] [basic principle]
(1) (2) (3) (4) (5) (6)
V V [y > x x y
a > 0 <^=> a - 0 e P
V x x
0 = x
a - 0
> o <^=> a e P
V [x > 0 x L
xe P]
[ID] [theorem]
[(3)]
[(2), (4)] [(1) -(5)]
[7.03]
[7-31]
In paragraph form we could write:
By (G), a > 0 if and only if a - 0 € P. But, by Theo- rem 43, a - 0 = a. So, a > 0 if and only if a e P. Hence, V [x > 0 <=> x € Pi.
Theorem 83 is useful in that it enables us to replace any sentence of the form *. . . £ P' by one of the form *. . . > 0'. So, for example, we can restate the theorem 41 € P* as 41 > 0'. Theorem 81--'0 i P'--can be restated as '0 / 0'. Also, since Theorem 81 is equivalent to the statement:
Vx [x = 0 => x 4 P]
and, so, to the statement
V [xe P x l
/o],
Theorem 83 can be used to translate Theorem 81 to:
V [x > 0 => x £ 0]
Other convenient ways of saying the very same thing are:
and:
x c P r
\>o^°
EXERCISES
A. 1. Use Theorem 83 to translate our basic principles (P.^, (P2), (P3), (P4), and (G), into statements which do not contain *P*. The last of these five statements we shall call 'Theorem 84'.
2-. Can you use Theorem 83 to translate the five statements you obtained in Exercise 1 back into the basic principles (Pj^),
(P2), (P3), (P4), and (G)?
O, s.K *U
Theorem 84.
V V [y > x <=> y-x > 0]
J^ m.h O,
[7-32]
[7.03]
B. One useful corollary of Theorem 84 is:
|
Theorem 85. |
-x > 0] |
|
V [x < 0 <r-^> x l |
Prove this theorem. [Compare this theorem with Exercise 1 of Part D on page 7-26.]
C. 1. Now look at the theorems in Sample 2 and Exercises 3, 4, 5,
and 6 of Part C on page 7-25. With the help of (G) and Theorem 83 we can translate these five theorems into useful theorems about >. Do so, [These five new theorems are parts a, b^, c, d, and e respectively, of Theorem 86. These five theorems could be taken as a set of basic principles for >. See Part ^D on page 7-35. ]
2. Give a column-proof to show that Theorem 86b is a consequence of (G) and the theorem of Exercise 3 on page 7-25. [See the solution of the Sample on page 7-26.]
INEQUALITY THEOREMS
In Part C of the preceding exercises you discovered Theorem 86. This theorem is an immediate consequence of earlier theorems on positive numbers, and basic principle (G).
|
Theorem 86. |
|
|
a. |
V V [x /£ y => either x > y or y > x] x y |
|
b. |
V V not both x > y and y > x x y ' 7 |
|
c. |
V V V [(x > y and y > z) =^ x > z] x y z L 7 7 J |
|
d. |
V V V fx > y => x + z > v + zl x y z ' J |
|
e. |
V V V [(z > 0 and x > y) => xz > yz] x y z |
[7.03]
[7-33]
Other theorems on inequations can be proved in a simiiar manner, but it is often easier to deduce such theorems from Theorem 86 and our first eleven basic principles. For example, consider:
Theorem 87.
V x f x x
As it happens, there is a previously proved theorem about P which can be used in proving Theorem 87. [Before reading further, try to guess which theorem this is, and use it in proving Theorem 87.] However, it is much simpler to derive Theorem 87 from one of the parts of Theorem 86. Do so now. [Hint. Recall that *x f x' is short for 'not x > x'.]
Theorem 87 is equivalent to:
V V [x = y => x f y] x y L J ii*
[Explain why.] This, and another consequence of Theorem 86b:
(*) V V [y > x=> x^ y]
x y
are very useful. We can combine them into a single theorem:
Theorem 88a.
V V [y > x => x f y]
x y L/ — i i i
[Explain. ]
To see how Theorem 88a is used, consider the following theorem which you probably recognize as the addition transformation principle for inequations :
|
Theorem 89. w W W I i \ i ^- |
^ i |
|
V V V x+z>y+z<= x y z L ' |
=> x > y] |
The if -part of this theorem is Theorem 86d. So, to prove Theorem 89, all we need do is prove its only-if-part :
[7-34] [7.03]
(**) VVV [x+z>y+z=>x>y]
x y z
This can be proved in a considerable number of ways. Probably the simplest of these ways is the following:
Suppose that a + c > b + c. Then, by (G), (a + c) - (b + c) € P and, since (a + c) - (b + c) = a - b, a - b € P. So, by (G) again, a > b.
However, for purposes of illustration, consider the following proof of (**):
Suppose that a + c > b + c. Since a = b or a / b, it follows from Theorem 86a that either a = bora> b or b > a- -that is, that either a > b or b > a. Suppose that b > a. If b = a then b + c = a + c, and if b > a then, by Theorem 86d, b + c > a + c. So, if b >_ a then b + c > a + c. But, by Theorem 88a, ifb + c>a + c then a + c f b + c. Hence, if b ^ a then a + c p b + c. Since, by hypothesis, a + c > b + c, it follows that b ^ a. But, as shown above, either a > b or b •; a. So, a > b. Therefore, if a + c > b + c then a > b. Consequently,
VVV [x + z > y + z => x > y] .
x y z L ' 7J
One advantage of this method of proof is that it can be used to derive: (***) VVV [(z > 0 and xz > yz) => x > y]
Jt y Z
from Theorem 86e. Do this now.
EXERCISES A. On page 7-33 we mentioned that the theorem:
(*) VV[y>x=>x/y]
x y
is an immediate consequence of Theorem 86b:
V V not both x > y and y > x
x y 7 7
By common sense, it sounds as though anyone who accepted Theo rem 86b would agree to (*). That is, it looks as though each inference of the form:
[7.03] [7-35]
not [p and q] q => not p
is a valid inference. Let's use the rules of reasoning we studied in Unit 6 to show that this is the case:
* t
e a
pands *
p => [p and q] not [p and q]
not p q =^ not p
1. You can use this kind of argument to show that: b > a => a ^ b is a consequence of the single premiss: not both a > b and b > a What assumptions would you use and discharge during the proof?
2. As shown in the tree -diagram, the proof would contain four infer- ences. Give the rules of reasoning which justify the inferences.
B. 1. Prove the converse of Theorem 88a from Theorem 86a. [See
second sentence of the second proof of (**) on page 7-34.]
2. Find a third proof for (**).
C. Prove each of the following.
1. V x + 1 > x [Theorem 90]
2. V V V V [(x > y and u>v)=>x + u>y + v] [Theorem 91]
3. V V V [(x > y and y > z) => x > z] [Theorem 92]
x y z
4. VxV [(x>yandy>x) r=> x = y] [Theorem 93] [Hint. Use Theorem 86a on page 7-29.]
5. VxV [-x > -y <=> y > x] [Theorem 94]
^"JD. Show that the five parts of Theorem 86 constitute an adequate set of basic principles for > by deriving from them the five statements you obtained in solving Exercise 1 of Part A on page 7-31.
[7-36] [7.03]
THE TRANSFORMATION PRINCIPLES FOR INEQUATIONS
In Unit 3 you studied theorems which justified the various steps taken in solving equations and inequations. As you learned there, the trans- formation principles for equations are derivable from the first ten of our basic principles. [See Theorems 6 and 7, Theorems 11 and 48, and Theorems 56 and 15.] You are now ready to consider the proofs of the transformation principles for inequations:
The addition transformation principle for inequations
VVV [x+z>y+z <==> x > y] x y z J J
The multiplication transformation principle for inequations
a. V V V . _ [xz > yz <=> x > y]
— xyz>0L 7 7J
b. VVV.,, [xz < yz <=> x > y]
— x y z < 0 L J ' J
The factoring transformation principle for inequations
a. V V [xy > 0 <=> ([x > 0 and y > 0] or [x < 0 and y < 0])]
b. V V [xy < 0 <=> ([x > 0 and y < 0] or [x < 0 and y > 0]) ]
x y
[These principles are Theorems 89, 95, and 96.]
The addition transformation principle is an immediate consequence of Theorem 86d and (**) on page 7-34.
Part a_ of the multiplication transformation principle is a conse- quence of Theorem 86e and (***) on page 7-34. [Recall now how Theorems 86a and 88a are used in deriving (***) from Theorem 86e.]
It is easy to derive part b_ of the multiplication transformation principle from part a_ by using Theorem 85, Theorem 20, and Theorem 94. Here is a proof:
By Theorem 85, for c < 0, -c > 0. So, by part a of the multiplication transformation principle,
a • -c > b • -c <=> a > b.
Hence, by Theorem 20,
-(ac) > -(be) <=> a > b.
[7.03] [7-37]
So, by Theorem 94 [Exercise 5 of Part C on page 7-35],
ac < be <=> a > b. Consequently, V V V < _ [xz < yz <==> x > y].
Parts a and b of the factoring transformation principle for inequations will be proved in Part A of the following exercises.
EXERCISES
A. 1. Prove the if -part of part a of the factoring transformation prin- ciple. Do this by first proving:
if (a > 0 and b > 0) then ab > 0 and then proving:
if (a < 0 and b < 0) then ab > 0
2. Now, let's prove the only-if-part of part a of the factoring trans- formation principle.
Suppose that ab > 0. By Theorem 81, ab £ 0. So, by the principle for multiplying by 0, b ^ 0. Hence, by Theorem 86a, either b > 0 or b < 0.
Suppose that b > 0. By part a of the multiplication transfor- mation principle, it follows that
ab > 0b only if a > 0. Since 0b = 0, it follows that, for b > 0,
ab > 0 only if a > 0. Since ab > 0, it follows that a > 0. So, for b > 0, we have
both a > 0 and b > 0.
Next, suppose that b < 0. [Show that in this case it follows that both a < 0 and b < 0.]
Since either b > 0 or b < 0, it follows that either
(a > 0 and b > 0) or (a < 0 and b < 0).
Hence, if ab > 0 then [(a > 0 and b > 0) or (a < 0 and b < 0)]. Consequently, we have proved the only-if-part of part a of the
[7-38]
[7.03]
B.
factoring transformation principle. This together with Exercise 1 gives us part a_.
3. Prove part b of the factoring transformation principle. [Hint. As in proving part t> of the multiplication transformation principle on page 7-36, you may find it helpful to use Theorem 85; then use part a of the factoring transformation principle.]
1. Prove that the squaring function maps each nonzero real number on a positive number. Interpret this graphically. [Theorem 97a]
2. Suppose that a and b are arguments of the squaring function for which the corres- ponding values are the same. What do you know about a and b? Prove it.
3. Suppose that a and b are nonnegative argu- ments of the squaring function for which the corresponding values are the same. What do you know about a and b? Prove it. [Theorem 98a]
4. Suppose that a and b are arguments of the squaring function such that the corresponding values are different. In particular, sup- pose that b2 > a2. Can you conclude that b > a? If you suppose that b2 > a2 and b > 0, can you conclude that b > a? Can a be -b? Can a be less than -b?
5. Suppose that a and b are arguments of the squaring function such that b > a. Does it follow that b2 > a2? Would additional knowl- edge about b allow you to conclude that b2 > a2? How about more knowledge about a?
6. (a) State the theorems you discovered in Exercises 4 and 5. (b) Prove them. [Theorems 98b and c]
[7.03]
[7-39]
C.
Suppose that quadrilateral ABCD is a square and that quadrilateral CDEF is a rhombus whose diagonals are 2a units and 2b units long.
1. Compute the area-measure of the square and the rhombus.
2. Is the area-measure of the square ever less than the area-meas- use of the rhombus? Are they ever equal?
3. State and prove a theorem about real numbers which tells you that if the rhombus is not a square then the area-measure of the square is greater than that of the rhombus. [Theorem 97b] [Hint. You may find it helpful to use the theorem *V / n x2 > 0'.]
x^ 0
Q(T' 2)
D. 't The figure at the left shows the
graph of the function
«x, y), x > 0: y = i}.
1. What are the side -measures of the rectangle with vertex Q? What is the area-measure of this rectangle?
2. What is the area-measure of the rectangle with vertex P?
3. What is the perimeter of the rectangle with vertex Q?
4. Must the two rectangles shown have the same perimeter?
5. Could you choose a point on the curve such that perimeter of the corresponding rectangle is greater than 100? If there are such points, give the coordinates of one of them.
6. Among the rectangles we have been considering, which has a minimum perimeter? Which a maximum?
[7-40] [7.03]
E. 1. Graph the reciprocating function r defined by:
r(x) = — , for x ^ 0 [Use cross -section paper and a unit length of about 1 inch.]
2. (a) On the figure you drew for Exercise 1, graph the equation
'y = x\
(b) Use these two graphs to draw the graph of the function p where p(x) = x + — , for x > 0. ["addition of ordinates"]
3. Does p have a minimum value?
4. State a theorem which tells what you have guessed in doing Exer- cise 3. [V . _ x + — >
L x > 0 x — J
5. Compare the theorem in Exercise 4 with Theorem 97b. Use the latter in proving the former. [Theorem 97c]
o, *■, v^
T T» T
As you have seen in Exercise 1 of Part E, the reciprocating function has positive values just for positive arguments. That is,
V / n [- > 0 <=> x > 0]. x f- 0 L x J
Let's prove this .
By Theorem 97a, for a f 0, a2 > 0. So, by the multiplication transformation principle for inequations, for a f 0,
I > 0 <=> - «a2 > 0 -a2, a a
So, since 0 • a2 = 0 and since, for a ^ 0, — • a2 = a,
I > 0 <=> a > 0. a
Consequently, V / _ f— > 0 <=> x > 01.
^ ' x f- 0 L x J
*!, «JU O^
•v t -v
[7.03] [7-41]
F. Prove each of the following.
1. VVV , n[2L > i <=> xz > yz] [Theorem 99a]
xyz/=0Lzz
2« VxVy^0 [~>0 <=> xy>0]
3' <*> Vy ^ Q Vz ^ Q [yz > 0 -> (y > z <^> I > I)]
(b) V . . V / . V / n [yz > 0 => (y > z <=> - > -)] ' x>0y^0z^0L7 7 z y J
(c) V.nV/nV._[y>z->~>-] [Theorem 100]
x>0y/=0z>0L7 z y
G. The theorem lV / _ [— > 0 if and only if x > Ol' tells you that the — x f- 0 L x ' J 7
reciprocating function has positive values just for positive argu- ments. What does the theorem in Exercise 3(a) of Part F tell you about the values of the reciprocating function?
H. Suppose that f is a real-valued function whose domain is the set of real numbers and is such that
(*) VxVy [x> y => f(x) > f(y)].
Prove each of the following.
1. V V [£(x) > f(y) => x> y]
x y
2. V V [f(x) = f(y) => x= y]
x. y
I_. Graph each of the following sentences on a picture of the number line 1. 5x - 3 > 7 - 5x 2. 2(x + 3) > 4 + 6x
~ x- 5 . x + 4 5x - 2 - ,
3. -r- > -T- 4. 1 < —3—I6
5. x(x - 3) > 0 6. (2x - l)(x + 3) > 0
[7-42]
[7.03]
7. x(x - 2) > x(x - 3)
8. x2 - x - 6 < 0
9. - > 10 x
11. x+ i > % x 2
13. (x2 + 5x)2 < 36
15. <* - »><V 4> > 0
x + 5
10. 12.
x - 1
6x - 5
< 1
> 7
14. (x + 5)(x - l)(x - 4) > 0
*16. JLLL > 2
Vx* + 1
J. Graph each of the following sentences.
1. y > 3x - 5 2. 2x + y - 3 > 0
3. x - 2y + 1 < 0 4. y - 3 < 0
K, Find all ordered pairs of integers which satisfy the given sentence
1 . 2x + y - 4 > 0 and x - 2y + 3 < 0 and y - 4 < 0
2. 4 - y < 4x < 3y < 9
3. 4x + y > 4 and 2x - y < 0 and x + 2y < 6
4. There is a triangle whose sides are x inches, y inches, and 5 inches long and y = 2x.
JL. 1. If three cans of peaches and four cans of pears cost less than
$1.60, and four cans of peaches and four cans of pears cost more than $1.80, can you buy a dozen cans of peaches for $2.40?
2. In a certain candy store, a lollipop costs less than a piece of
bubblegum. If you have just enough money to buy a piece of bub- blegum and someone gives you 2 cents more, you still won't have enough to buy three lollipops. But, if you have 8 cents, you have more than you need to buy a piece of bubblegum and two lollipops. What is the cost of a lollipop and the cost of a piece of bubblegum?
[7.03] [7-43]
MISCELLANEOUS EXERCISES
|
A. Simplify. |
|||||
|
1. |
7 2 11 " 3 |
2. |
11 12 |
3. |
5a + b a - b a + b a + b |
|
4. |
7x + y x - y x + y 2(x+y) |
5. |
I i 1 a b c |
6. |
4 5 a - b b - a |
|
7. |
k k |
8. |
k k |
9. |
x2 - 4y2 m 5x |
|
x - 2y 2x - y |
x - 2y 2x - y |
x - 2y (x + 2y)2 |
|||
|
10. |
9mb 9m b+1 b+ 1 |
11. |
x2-16 3x+15 x + 5 x - 4 |
12. |
9mb . 9m |
|
b+1 b+1 |
|||||
|
13. |
x2 - 16 3x+15 x + 5 x - 4 |
14. |
1 2 a- b + V |
15. |
k2 1 |
|
k - 1 k2 - k |
|||||
|
16. |
x2 - 4x + 3 xy 9 - x2 x - 3 |
17. |
....*?.„ + ! 9 - 12 t - 3 |
18. |
t* . t 9 - 12 * t - 3 |
B^. Graph each of the following sentences.
1. y = |3x - 4 | 2.y = x+|x| 3. y = 4x - x2
4. y = 4 - |x| 5. y = |4 - x| 6. y = |4x - x
7- y = x~hr 8- y = r^w 9- y = x2 + xTtt
C. Which of the following equations have no roots? 1. x + x = x 2. x+i=i 3.
xx x + 2 x + 3
4x - 8 _ 3x - 12 3 5
x + 4 x + 4 * x x(x - 1) x(x - 1)
ID. Solve.
1. (x + 5)(x - 4) = (x + 5)(2x - 9) 2. y(y - 3) = y(2y + 5)
3. a2 - 5a + 6 = 2a2 - 6a 4. a2 - 5a + 6 = a2 - 3a
5. k(k- l)(k-3) = k(2k + l)(k- 1) 6. (y + 2)(y-4)(y + 5) = 40(y - 4)
7. x(x + 7) = (x + 7)(x + 3) 8. ^-i = 3a + 7
3 3a
[7-44] [7.03]
E. 1. Find a point on the y-axis which is twice as far from (4, 0) as from (-1, 0).
2. What point on the graph of 'y = x' is equidistant from (6, 0) and (6, 8)?
3. A point moves so that it is equidistant from (4, 0) and (0, 4). Find an equation of its path. [Hint. Suppose that the point has coordinates (x, y). Then, . . . ]
4. A point moves so that its distance from (0, 0) is twice its distance from (3, 0). Find an equation of the path. "What is the path?
5. Suppose that P is a moving point whose path is the circle with center (0, 0) and radius 2. Find an equation of the path of M, the midpoint of PA, where A is the point (8, 0). Sketch the path of M.
6. By how much does 0. 3333 differ from -^ ? By how much does 0. 142857 differ from j ?
7. Mr. Johnson travels by car between Zilchville and Zabranchburg. One tenth of the trip is through towns and the rest is on the open highway. If the speed limit in towns is 15 miles per hour and on the open highway 50 miles per hour, can he average 40 miles per hour for the entire trip without exceeding the speed limits?
8. Which is the larger, -rj- or ■£-=-, or are they equal?
9. Mr. Jones starts from Zabranchburg to drive to Frampton, 24 miles away. Fifteen minutes after starting he meets with an accident. After wasting 5 minutes trying to fix the car, he proceeds at half speed to a service station 2 miles farther along the road. Three quarters of an hour later he starts out again, and by driving 12 miles an hour faster than at first, he manages to get to Frampton 50 minutes later than he had planned. What is his usual driving speed?
[7.03]
[7-45]
EXPLORATION EXERCISES A. Consider the eleven sets listed below.
(a) the set of all real numbers
(b) the set of all rational numbers
(c) the set of all irrational numbers
(d) the set of all negative numbers
(e) the set of all nonnegative numbers
(f) the set of all integers
(g) the set of all integers greater than 5 (h) the set I+ of all positive integers
(i) {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
(J) {-y> 0, y, 1, l~, 2, . . . } [What does 4. . . ' mean?]
2 2 2 2
(k) {5, 5-j, 6, 6-j, 7, 7-j, 8, 8y, ...}
|
(1) |
(2) |
|
y |
|
1. For each of the eleven sets, put a check mark in column (1) if the number 1 belongs to the set.
2. For each of the sets, put a check mark in column (2) if, for each x,
if x belongs to the set then x + 1 belongs to this set.
3. For which sets do you have check marks in both columns?
4. Name five other sets S such that
1 e S and V [x e S => x + 1 e Si. x L J
B_. Eet?7\= {S, S a set: 1 c S and V [x € S => x + 1 e S]}.
1. Name some members of77"\.
2. How many sets belong to/71?
3. Do you think that there is a member of 777 which is a subset of each member of 777?
[7-46] [7.03]
C. In Part A you noticed that I+ e#(--that is, that (i) 1 € I+
and that
(ii) V [x e I+ =^ x + 1 e I*].
Here is a proof, using (i) and (ii), that 2 e I+:
(1) 2=1+1 [definition]
(2) V [xel+=»x+le I+] [(ii)]
(3) 1 e I+ => 1 + 1 € I+ [(2)]
(4) 1 e I+ [(i)]
(5) 1 + 1 €l+ [(3), (4)]
(6) 2el+ [(1), (5)]
1. In Part A you also noticed that the set R of all rational numbers belongs toTTT. How could you easily obtain a column proof, in which you used no other fact about R, for the theorem '2eR'?
2. Suppose that all you are told about some set S of real numbers is that S eTf\. Does it follow from this that 2 e S? [Why?]
3. Prove that 3 € I+. [Hint. You may use the previously proved theorem '2 e I+ '. ]
4. Repeat Exercise 2 with 43 e S' in place of 42 e S'.
5. Repeat Exercises 3 and 4 with '4' in place of '3'.
6. Do you think that there is a positive integer which you could not prove belongs to I+ by using (i) and (ii)? [Given lots of time!]
7. In view of your answer for Exercise 6 [and your answers for the preceding exercises], what are some of the numbers which you believe belong to each set S which belongs toT^T?
8. Consider the following statement:
(iii) Vg [( 1 € S and Vx [x e S => x + 1 e S]) ==> I+ C S] Do you believe what this says?
[7.04] [7-47]
7.04 The positive integers. --In an earlier section you proved that 1 € P» that 2 € P, that 3 € P, and that 4 € P. Clearly, we could have continued and shown that 5 e P, that 6 € P, . • • until we got tired. As you know, the real numbers 1, 2, 3, ... are called the positive integers. Could we have proved that each of them really is positive? The answer is 'no*. One reason for this is that a generalization with an infinite number of instances cannot be proved just by proving instances of it. Another reason why it is impossible at this stage to prove that each of the so- called * 'positive'* integers belongs to P is that our basic principles say nothing about the positive integers. In order to prove theorems about I+ --the set of positive integers --we need additional basic principles.
Back in Unit 4 you did prove some theorems about I*, and in order to do so you made certain assumptions. They were the following:
(1) The positive integers belong to P, that is, I* C, P.
(2) I+ is closed with respect to addition and multiplication.
(3) For all positive integers m and n, if n > m then n - m is a positive integer.
(4) 1 is the only positive integer between 0 and 2
(5) Each nonempty set of positive integers has a least member.
(6) For each real number x, there is an integer k such that k < x < k + 1.
(7) Each positive integer other than 1 has just one prime factori- zation.
So, in effect, in Unit 4 you adopted (l)-(7) as additional basic principles. Now, certainly, this is a heterogeneous lot and there is not even any reason to believe that they are adequate for proving all the theorems we may want to prove about I*. Let's try to find some simpler basic prin- ciples which [together with the sixteen we already have] will do the job.
We said that the positive integers are the real numbers 1, 2, 3, . . . . Our problem is that of making this statement more precise- -actually, of explaining the * ... * .
Let's suppose that someone who doesn't know asks you what the positive integers are. You might begin by saying that the positive
[7-48] [7.04]
integers are 1, 2, 3, and so on. To test his understanding of your answer, he might then ask, "Is 4 a positive integer?' You would probably tell him that, yes, 4 is a positive integer and so is 5, and so on. And you might add that, for each positive integer x, x + 1 is a posi- tive integer. So, so far, you have told him two important things about I+:
(a) 1 e T
(b) V ,+ x + 1 € I+
x e I
Knowing these, he has a method for picking out an unlimited number of positive integers. But, he still has one more important question: "Are there any positive integers which can't be gotten this way?" To this you would say, "No, those are all the positive integers there are. " This last bit of information is a third basic principle about I+. Let's try to restate it in a more usable form. Let K be the set of all those real numbers which can be proved to be in I+ by using (a) and (b). Then,
1 e K and V v x + 1 e K
x € K
Your answer, above- -that K contains all the positive integers - -amounts to saying that I+C_K. To see what this entails, suppose that S is a set of real numbers such that
(1) 1 e S and V c x + 1 e S
x e s
If a real number c e K then, by the definition of K, there is a proof using (a) and (b) that c e I+. Consider such a proof. If you replace all the *I+ 's in it by 4S's, you then have a derivation of 'c e S' from (1). So, if S satisfies (1) then each member of K is a member of S, that is, K C^ S. In other words,
VQ [(1 e S and V c x + 1 e S) => K C Si.
So, if you say that I+ C K then you are implying that
(*) VQ[(leSandV c x + 1 e S) => I+ C S].
o x £ o —
On the other hand, suppose that you assert (*). Since 1 e K and V..X+ leK, you are implying that I+CK.
[7.04]
[7-49]
So, (*) says precisely that I+ C K. In other words, (*) tells us that each positive integer can be gotten from (a) and (b). Let's use (*) to prove (1) on page 7-47:
Since P is a set of real numbers, it follows from (*) that if ( 1 € P and V x + 1 e P) then I+ C P.
Now, by Theorem 82, 1 e P. By Theorem 82 and the basic closure principle (P3), V p x + 1 e P. So [by modus ponens], I+C_P.
Although, as you have just seen, (*) is convenient for proving certain theorems, it will be more useful to take as our third basic principle for I+ the following:
(c) Vs [(l e S and Vx e I+ [x e S => x + l e S]) ^Vx£l+xeS]
Using (a) and (b) it is possible to show that (*) and (c) are equivalent.
In order to state our three basic principles for I+ in a simpler form, and to simplify the statements and proofs of later theorems, we shall (as above] use lS' as a variable whose values are sets of real numbers, and use lm', 'n', 'p', and lq' as variables whose domain is I+. So, for example, in place of the sentences 'V T+ x e S', we shall write 'Vm m e S' or 4V q e S'. In particular, lVm m e I+ ' is an abbreviation
m
for the trivial theorem 'V t+ x e I+'
Using these conventions about variables we can restate our three basic principles for I+ as follows:
|
(I\) |
1 el+ |
|
(I *2) |
V n + 1 e I+ n |
|
»*3 ) |
Vs [( 1 e S and Vn [n e S =» n 1 1 € S]) => Vn n e S] |
Note that when (I+2 ) is written out fully, we have *VX [x e I+ ==> x + 1 e I*]1
Also, one can rewrite Theorem 101 as 'V ne P'.
n
[7-50] [7.04]
EXERCISES
A. In each of the following exercises you are given a set S. Your job is to prove or disprove:
V [n € S => n + 1 e S] n
Sample. S = {m: 3 + m e I + }
Solution. What we want to prove [or disprove] is the following:
V [n € {m: 3 + m e T} => n + 1 e {m : 3 + m e I+}] We can simplify this immediately to:
V [3 + n € T => 3 + (n + 1) € T]
n L J
In order to prove this generalization, we proceed in the familiar way by supposing 43 + p e I+' and then deriving 43 + (p + 1) eT\
Proof. Suppose that 3 + p e T. Then, by (I+2), (3 + p) + 1 e I+.
But, by the associative principle for addition, (3 + p) + i = 3 + (p + 1). So, 3 + (p + 1) e T. Therefore, if 3 + p e I+ then 3 + (p + 1) e I+. That is, if p e S then p + 1 e S. Consequently,
V [neS=>n+leS]. n L J
1. S = {m: m > 1}
2. S = {m: m - 5 e I*}
3. S = {m: m2 > m}
4. S = {m: m < 4} *5. S = {m: m < 0}
B. Prove that 3 e I+.
[7.04] [7-51]
PROOFS BY MATHEMATICAL INDUCTION
On page 7-47 we stated certain assumptions you made about the positive integers in an earlier unit. The first of these is Theorem 101 which we have already proved. The other six assumptions can also be proved by using (l*^, (I+2), and (I+3). [To prove (6) we shall need one more basic principle.] These theorems will be proved in this and later units .
As an instructive example of how such theorems are proved, let's prove:
(*) V 3 + n e I +
n
[Notice that since 3 e I+, this is an instance of a theorem, 4V V m + n€ I+',
- m n
which says that I+ is closed with respect to addition.]
To prove (*) is to prove that each positive integer has the property that when it is added to 3, the sum is a positive integer. This amounts to saying that {x: 3 + x e I+} contains all the positive integers. In other words, (*) is equivalent to:
V n € {x: 3 + x € I+}
n l J
Looking at (I+3), we see that we can prove this if we can prove:
1 6 {x: 3 + x € I+} and V [n e {x: 3 + x e T} => n + 1 e {x: 3 + x e T}]
And, we can prove this if we can prove:
(i) 3 + 1 e I*
and:
(ii) Vn [3 + n € I+ => 3 + (n + 1) e I+] [Explain. ]
Now, let's start proving.
[7-52]
[7.04]
Part (i) :
|
(1) |
V n |
n + 1 e T |
|
(2) |
3e r |
|
|
(3) |
3 + 1 € r |
|
|
Part (ii) : |
(4) (5) (6)
3 + q € I+
V n + 1 6 I* n
(3 + q) + 1 £ I+
(7) VxVy x+ (y + 1) = (x+y) + 1
(8) 3 + (q + 1) = (3 + q) + 1
(9) 3 + (q + 1) € I*
(10) 3 + q £ I+ => 3 + (q + 1) e I+
(11) V [3 + n £ I+=> 3 + (n + 1) £ I+]
Part (iii) :
(12) 1 £ {x: 3 + x£ I+}
(13) Vn[n€ {x: 3 + x € I+} => n + 1 € {x: 3 + x£ I+}]
(14) VJdeSandV [n £ S => n + 1 £ S]) => V n £ S]
n
n
r
(15)
(1 € {x: 3 + x £ I+} and V [n £ {x: 3 + x £ I+}=> n + 1 £ {x: 3 + x € I+}])
n
(16) (17)
V n £ {x: 3 + x£ T}
V n £ {x: 3 + x £ I+}
V 3 + n £ I+ n
J
(i*2 )]
theorem] (1), (2)]
assumption]*
u +2)]
(4), (5)] theorem] (7)]
(6), (8)] (9); *(4)] (4) -(10)]
(3)] (11)]
(14)]
(12), (13), (15)] (16)]
[7.04]
[7-53]
This proof is a typical proof by mathematical, induction [or : indue - tive proof]. The basic principle (I+3 ) [or some equivalent statement] is called the principle of mathematical induction. As illustrated above, an inductive proof of a generalization about positive integers--that is, of a sentence of the form:
V F(n) n
[V 3 + n c T] 1 n J
consists of three parts.
Part (i) [steps (1) -(3)] is a proof of the generalization's "first instance" :
F(l) [3 + 1 el+]
[The whole of part (i) is sometimes called the initial step of the proof.] Part (ii) [steps (4) - (11)] is a proof of a sentence of the form:
V^ [F(n) => F(n +1)] [V [3 + n e I+ => 3 + (n + 1) € I+]]
n
n
[The whole of part (ii) is sometimes called the inductive step; and the assumption [step (4)] is called the inductive hypothesis.]
Part (iii) [steps (12) -(17)], which is sometimes called the final step, brings in (I+3). This part is much the same in all inductive proofs. It consists of six steps of the form:
( )
1 € {x: F(x)}
[
]
( ) Vn [n € {x: F(x)}=> n + 1 e {x: F(x)}]
( ) Vg [(1 € S and VR [n 6 S=> n + 1 € S]) => Vn n 6 S] [(I+3)]
C (1 € (x: F(x)} and
( ) I Vn [n € {x: F(x)}=> n + 1 e {x: F(x)}])
">
V.
V n e {x: F(x) } n J
J
( )
V n e {x: F(x)} n ^ J
[ ,
( )
V F(n) n
[7-54] [7.04]
The marginal comments for the first two steps refer, in each such proof, to the conclusions of parts (i) and (ii), respectively. The mar- ginal comment for the fourth step refers to the third step. That for the fifth step refers to the first, second, and fourth steps. Finally, the marginal comment for the last step refers to the preceding step.
Obviously, once you have completed parts (i) and (ii) of an inductive proof, writing part (iii) is just hack work. You could even have a rubber stamp made which would print a form like the one above, but leave blanks in place of 'F(x)' and 'F(n)'. Then you could finish any inductive proof by printing this form after part (ii), writing the appropriate sentences in the nine blanks, and filling in the numerals at the left and the marginal comments on the right. Instead of doing even this, let's agree that once we have completed parts (i) and (ii) we can skip the first five steps given in part (iii), and finish the proof by writing a single step of the form:
( ) Vn F(n) [ , , PMI]
The marginal comment will refer to the conclusions of parts (i) and (ii) and indicate that the justification of this step makes use of (I+3), that is, of the principle of mathematical induction.
With this agreement for shortening part (iii), the proof of theorem (*) consists of twelve steps --the eleven steps which make up parts (i) and (ii), and a final step:
(12) Vn 3 + n el+ [(3), (11), PMI]
[We could also shorten the proof by leaving out step (5), since this is the same as step (1). Doing so, the succeeding steps would be renumbered and the comment for the conclusion of part (ii) would be 4(1), (4) -(9)'.]
As usual, paragraph proofs are shorter. Here is a paragraph proof for (*) :
(i) Since 3 e I+, it follows by (I+2 ) that 3 + 1 e I+ .
(ii) Suppose that 3 + q e I\ It follows by (I+2) that (3 + q) + 1 6 I+ . But, (3 + q) + 1 = 3 + (q + 1). So, 3 + (q + 1) € I+. Hence, Vn [3 + n eI+=> 3 + (n + 1) € I4].
(iii) From (i) and (ii) it follows, by the PMI, that V 3 + n e I+.
n
[7.04] [7-55]
Before writing an inductive proof, you will find it helpful to restate the theorem you wish to prove in the form:
V n e {x: F(x) } n *• J
and to write the sentences of the forms:
F(l) and: V [F(n) => F(n + 1)]
which are to be the conclusions of parts (i) and (ii) . If you have trouble in seeing what these last two sentences are, you may find it helpful to write a sentence -form with a blank in place of the variable. Thus, if you were to prove (*):
V 3 + n € T n
you would, before beginning the proof, write:
V ne {x: 3 + xc T}
n v J
3 + . . . e I+
(i) 3 + 1 e I+ (ii) V [if 3 + n e I* then 3 + (n + 1) € I+]
EXERCISES
A_. 1. Give a column proof of Theorem 101 [*V n e P'] by mathematical induction. [Before stating the proof, carry out the suggestion made in the preceding paragraph.]
2. Write all six steps of part (iii) of the inductive proof of Theorem 101.
B. 1. Give a column proof of 'V 3n e I+*.
— r n
2. Give a paragraph proof of the same theorem
[7-56]
[7.04]
CLOSURE OF T WITH RESPECT TO + AND X
Two of the assumptions about positive integers which you made in an earlier unit amount to the following theorems:
and:
Theorem 102.
V V m + n € I+
m n
Theorem 103.
V V m • n e I+ m n
Theorem (*) on page 7-51 is the "third instance" of Theorem 102, and its proof will suggest how to prove Theorem 102.
We now have two methods for proving generalizations. The first method, which you used in earlier units, depends on the test-pattern principle. To use this method, you r.jd-ke up a testing pattern for the instances of the generalization. The second method involves the PMI [and applies only to generalizations about positive integers].
In Unit 2 you learned that you could often find a test-pattern for a generalization by first proving an instance of the generalization. For example, in order to find a proof for 4V x + x = x • 2' you might begin by trying to prove, say, '3 + 3 = 3*2'. Here is such aproof:
(1) (2) (3) (4) (5) (6) (7) (8) (9)
H + 12 = Q] + m
|
V X- 1 : X |
- X |
|
|
3 ' 1 : |
-® |
|
|
a + oi = |
- (II- 1 + QJ. |
1 |
|
x(y + z) = |
- xy + xz |
|
|
U(l + 1) : |
= [H-i + GO- |
1 |
|
EJ + [I] = |
= GOa + i) |
|
|
2 = |
= i + i |
|
|
E] + ,3 -- |
= 3 -2 |
[Identity] [pml] [(2)]
[(1), (3)] [idpma] [(5)]
[(4), (6)] [definition] [(7), (8)]
[7.04] [7-57]
Now, in order to obtain a proof of *V x + x = x • 2', all you need do is replace each boxed 43' by, say, an 'a', and add one more step:
(10) V x + x = x-2 [(1) - (9)]
This suggests that, in order to prove Theorem 102:
V V m + n € I+ , m n
we begin by trying to find a test-pattern for sentences of the form:
V p + n e r n r
And, it suggests that a proof of one such sentence, say:
(*) V 3 + n e I+
n
may indicate how to write such a test-pattern.
Let's look at the proof of (*) on page 7-52. This is an inductive proof, and the main problem was to prove:
3 + 1 e T, and: V [3 + n e 1+ => 3 + (n + 1) e I+ ]
n L J
What we now want to do is to get test-patterns ending with:
p + 1 6 I+, and: V [p + n e I+ => p + (n + 1) e I+ ]
For, if we can do this, we can conclude:
( ) Vn p + n e T [ , , and PMI]
Then, we shall have a test-pattern for sentences of the form:
V p + n e I+,
n
and, by the test-pattern principle, can complete the proof of Theorem 102 by writing :
( ) V V m + nel+ [(1) - ( )]
m n l\ / \ /j
[7-58] [7.04]
EXERCISES A. 1. Write a column proof of Theorem 102. 2. Write a paragraph proof of Theorem 102.
vU *t* o„ "lN *(* *v
If you followed the discussion on test-patterns, and looked at part (i) of the proof on page 7-52, your answer to Exercise 1 of Part A probably begins like this :
Part (i):
(1) V n + 1 e I+ [(!*)]
n
+ »
(2) p e T [theorem]
(3) p + 1 € I+ [(1), (2)]
Parts (i) , (ii), and (iii) make up a test-pattern for instances of
* VL, V_ m + n € I+ '--that is, for sentences of the form 'V p + n e I+ '. m n * n r
To test such an instance we substitute for 'p' a numeral for some positive integer. So, after making such a substitution, step (2) will be a theorem. We can somewhat simplify the proof by taking account of our convention that the domain of *p' is I+. Because of this, 'pel is a trivial theorem — step (3) is an immediate consequence of step (1).
K^ x»* >.** ■V "V 'i%
B_. 1. Complete the following proof of Theorem 10 3. [Important: First look at (5) and (13), and fill in (14) and the marginal comment for (15). After you have seen how to do this, com- plete part (i) and part (ii).]
Part (i) :
(1) V n e I+ [trivial theorem]
(2) P e I+ [(1)]
(3) [basic principle]
(4) [ ]
(5) pi e T [(2), (4)]
[7.04] [7-59]
Part (ii):
(6) pq e l+ [inductive hypothesis ]*
(7) V V x(y + 1) = xy + x [theorem]
(8) [ ]
(9) [ ]
(10) pq + p e r [ , (9)]
(11) [ ]
(12) [(H); *(6)]
(13) Vn [pnel+ => p(n+ l)e I+] [ - ]
Part <iii) :
(14) [ , , PMI]
(15) V V mn € I+
1 ' m n
2. Write a paragraph proof of Theorem 103.
MISCELLANEOUS EXERCISES
1. If the area of a rectangular enclosure is 48 square yards and the perimeter is 28 yards, what are the length and the width?
2. Mr. Jones is 24 years older than Bill. Eight years ago he was twice as old as Bill. How old are they now?
3. A can do a certain task in 8 days. If B works along with A, they can do it in 4 days. How long would it take B to do it alone?
4. One leg of a right triangle is 7 feet longer than the other leg. If the hypotenuse is 13 feet long, what is the area of the triangle?
5. Suppose that the vertices of the acute angles of a right triangle are A(-5, 0) and B(5, 0). Write a sentence whose graph contains just the points which can serve as the third vertex of this triangle.
[7-60] [7.04]
6. The average velocity of molecules of air at room temperature is about 5 X 104 cm/sec. About how many miles per hour is this?
7. A unit commonly used in measuring atomic particles is the Angstrom unit. It is a unit of length, and is defined to be 10~8 centimeters
o
long. If the average atom is 3. 5A in diameter, how many such atoms placed side by side would it take to span a 1 -inch distance?
8. Physicists in the 18th century discovered that the force of attraction between two particles with opposite electrical changes is inversely proportional to the square of the distance between them, and jointly proportional to the magnitude of the charges. How is the force of attraction between the charged particles changed (a) if the distance between them is doubled? (b) if the charge of one particle is doubled? (c) if the charges of both particles are doubled?
9. [A point Q is said to be a reflection of a point P with respect to a point R if and only if R is the midpoint of PQ. ] Suppose that quad- rilateral ABCD is a parallelogram and that P is a point in its plane. Let P2 be the reflection of Px with respect to A, P3 be the reflection of P2 with respect to B, P4 be the reflection of P3 with respect to C, and P5 be the reflection of P4 with respect to D. Prove that P5 = Px ,
10. (a) If V f(p) = *P + 1 then V f(p + 1) = and V f(p - 1) =
P ^P " 3 P P
(b) If Vpf(p) = p(p-l) then Vpf(p + 1) = andV f(p-l) =
(c) If V g(n) = n(n + l)(n + 2) then V g(n + 1) = and V g(n - 1) =
n n n
(d) If V g(p) = p2 - (p - l)2 then V g(p + 1) = and V g(p - 1) =
(e) If V S(n) = n2 then V S(n + 1) = and V S(2n + 1) =
n n n
11. A student looked at the statement *2X(3 + 4) = 2 + (3X4)' and thought it was false because it looked as if someone were trying to use a commutative principle on the multiplication and addition signs. But, of course, the statement is true. Find other integers x, y, and z such that x X (y + z) = x + (y X z).
[7.04] [7-61]
RECURSIVE DEFINITIONS
One of the mathematical pastimes of the ancient Greeks was the discovery of interesting generalizations concerning whole numbers. For example, consider the following diagram:
|
V |
|
|
V |
•\# |
|
A • |
. ,\. |
|
\ |
\ |
|
\* |
|
|
V |
•v |
|
••V |
• • • y • |
|
• • • * • |
* • • • v • |
\
If we count the dots in each of these "triangles" and in those we would get by continuing the obvious construction, we obtain a sequence of num- bers which begins
1, 3, 6, 10, 15, 21, 28, ... .
The Greeks called these whole numbers triangular numbers. For our purposes it will be more convenient to regard the corresponding positive integers as triangular numbers.
Suppose that we use 'T ' to name the first triangular number. Then T. = 1. Also, T0 = 3, T, = 6, T, = 10, and T = 15. What is T, ? T_ ?
1 ' 2 ' 3 ' 4 5 6 7
Suppose you are told that T is 55. Can you use this information to find TX1 ?
Given that T25 = 325, find T26.
As you see,
r T1 = 1, and
(1) IV T , = T + (n + 1).
V n n + l n
These formulas give a way of computing triangular numbers. For example,
T6 = T5 + 6
= (T4 + 5) + 6
= (T3 + 4) + 5 + 6
= (T2 + 3) + 4 + 5 + 6
= (T1 + 2) + 3 + 4 + 5 + 6
= 1 + 2+3 + 4+5 + 6 = 21.
[7-62]
[7.04]
The process of using T5 to compute Tfe, T4 to compute T5, , and T
to compute T is an example of recursion. Use recursion to compute T6.
Evidently, (1) gives us a way of computing any triangular number. That is, (1) gives us a procedure for computing the successive values of a function, T, whose domain is the set of positive integers and whose range is the set of triangular numbers.
Some of the ordered pairs in T are (1, 1), (2, 3), (3, 6), and (4, 10). What is the ordered pair in T with 8 as first component? With 9 as first component? [Notice that in the case of a function like T whose domain is 1+, it is customary to modify the usual functional notation and write, say, 4T10' instead of 'T(IO)' .]
The pair of formulas (1) is called a recursive definition of the func- tion T. Here are recursive definitions of two other functions:
Vn+l=(n+1>fn
rl = 1
V r = |r +
n n+ l \ n r
n
/2
Compute the first four values of each function. Complete
V f
n n + 2
-< >fn+1 = < >< >£n
In working with functions in earlier units, you became accustomed to a different way of defining functions - -explicit definition. For example, consider the sequence, S, of square numbers.
• •
• • •
• • • •
• • • •
An explicit definition of S is
n
S = n2 n
With this kind of definition, you can find any value of S directly without previously computing other values.
Can we discover an explicit definition for T? You might want to play with this problem before reading further.
[7.04]
[7-63]
Let's reconsider X. The following figure shows that T6 + Tfe = 6*7,
and suggests that (2)
\
V T = n(n + *) n n 2
We can check this guess against the recursive definition by noting that
1(1 + 1) = j
and that, for each n,
(n + l)[(n +!)+!] = n(n + 1) + (n + x) #
[Verify this last generalization by transforming the right side of the equation into the left. ]
This checking procedure shows that there is a function- -namely, the one defined by (2) --which satisfies the recursive definition. What we want to do now is to show that there is only one such function. This we can accomplish by deriving (2) from (1). Let's do so.
Our job is to prove:
V T n(n + 1)
n n
We shall use the principle of mathematical induction to prove this generalization about positive integers. Restating the generalization, we have :
w , ( -r m(m + 1) ■»
V ne {m: T = — ■ = -}
n m 2
As a help in formulating the proof we write:
...(... + 1)
T
<i) Ti = Ki + D
(ii) V
n
T = n(n + *) ==> T
2 n+ l
_ (n-H)[(n-H)+l]
n
[7-64] Part (i)
|
(1) |
T1= 1 |
|
(2) |
Kl + 1) . , 2 |
|
(3) |
* _ Id + 1) |
|
Part (ii): |
(4) (5) (6) (7)
T =
V T , n n+ l
q(q+ 1) ^
T + (n + 1) n
T L = T + (q + 1) q+ l q VM '
W-aafiUu + i)
(8) V i<i + i> + (x + 1) = <*+'>[<*+l> + l]
{9) ais^Ll) + (q + i) = la + m +ILLU
(10)
_ (q + l)[(q + 1) + 1] q + 1 " 2
(in t = q(q + l) => t = (q j D[(q UJLIJJ
7 q 2 q+ l 2
(12) V (t = n(n + *> => T = (n + l)Hn + l) + Ll
n n 2 n+ l 2
[7.04]
[recursive definition]
[theorem] [(1), (2)]
[inductive hypothesis]*
[recursive definition]
[(5)]
[(4), (6)] [theorem]
[(8)]
[(7), (9)] [(10); *<4)] [(4) -(H)]
Part (iii) (13)
V T = n(n + *)
n n
[(3),(12),PMI]
In the future we shall omit steps like (5) and label steps like (6) '[recur- sive definition]'.
[7.04]
[7-65]
In practice, one could replace steps (8), (9), and (10) by
|
q(q |
+ 1) + 2 |
(q |
+ |
1) |
|
|
2 |
|||||
|
<q + |
D[(q + |
1) |
+ |
1] |
/ [algebra]
You might want to put in more manipulation steps than these to convince a reader that you knew what you were doing. Here is a paragraph proof of (2):
(i) Since, by the recursive definition of T, T = 1, and since
1(1 + 1) _ , T Kl + 1)
2 ' l 2
(ii) Suppose that T = ? -. Since, by the recursive defi-
nition, T = T + (q + 1), it follows that T , = q^q * l' + (q+ 1).
q+ l q q+ l 2 M '
But, stfL+Ji + (q + i) = aia + U + 2'q + U - <q + ^ + z> . s». if
T = q(q + 1) then T = (q+l>[(q+l) + l]
q+1
Consequently,
w fT _ n(n + 1) T _ (n + l)[(n + 1) + 1]"|
n pi ' 2 n+i 2 J '
(iii) From (i) and (ii) it follows, by the PMI, that V^ T^ = "^ ^
n n
Here is a tree-diagram of the proof on page 7-64.
(5) (8) (4) (6)
(9)
(7)
(1) (2)
(3)
(10)
(11)
(12) [PMI]
(13)
It shows clearly that (13) is a consequence of the theorems (2) and (8), the recursive definition consisting of (1) and (5), and the PMI.
[7-66]
[7.04]
Use either column proofs or paragraph proofs for the following exercises .
EXERCISES
A. 1. Consider the following recursive definition of a function E whose domain is I+:
E1 = 2
V E = E + 2
n n + i n
(a) Compute Ep, E , E , and E .
(b) Complete the following
V E n i
to obtain an explicit definition of E.
V E = n n
(c) By mathematical induction, derive the explicit definition of E from its recursive definition.
2. Give a recursive definition for the function O whose values are the successive odd positive integers, and repeat Exercise 1, using your recursive definition of O in place of the recursive definition of E.
3. Here is a recursive definition of a function S
s1= 1
V S , = S + (2n + 1)
n n + l n
Repeat Exercise 1 for the function S.
B_. 1. Consider the sequence of triangular numbers. Notice that the
10 15 21 28
T T
tP /p + i
4 9 16 25 36
sum of each two consecutive triangular numbers appears to be
[7.04] [7-67]
a square number. This suggests, as a theorem, a generalization which begins :
V S , = n n+ 1
Complete the generalization, and prove it by mathematical induction.
2. The explicit definition of S which you obtained in Exercise 3 of Part A is:
V S = n2 n n
(a) Use this definition to complete the following generalization:
(*) V S , =
v ' n 2n + l
(b) Use this result and the explicit definition of the triangular numbers to discover a relation between the odd square numbers and the triangular numbers. [Hint. Transforming the right side of (*) may help.] Express your discovery as a generali- zation beginning with:
V S , = n 2n + l
(c) Give a second proof- -this time by mathematical induction- -of the generalization you discovered in (b).
3.
|
Consider these three |
se |
qu |
ences |
: |
|
|
1 |
2 |
3 |
4 |
P |
|
|
1 |
3 |
6 |
10 . . . |
T P |
|
|
1 |
4 |
9 |
16 ... |
S P |
Discover how to find a term of the second sequence from the corresponding terms of the first and third sequences. Express this discovery in a generalization and prove it by mathematical induction.
4. Prove that, for each n, the nth even positive integer is the average . of the 1st and the 2nth odd positive integers.
[7-68] t7-04]
C. 1. Here is a recursive definition of a function f whose domain is I+:
~~* fn
f1 = 3, and Vnfn+1 = y^
Compute the sum of the "first ten" values of f .
2. If r± = 3, and Vp rp + ± = rp + ^p, then compute r 1Q.
3. If f3 = 7, and Vn £n+i = fn + 5 then i± = .
4. If i1 = 9, and Vm f m + x = fm + 10, then f 1T - f 16 = .
5. If gj. = 4, and vn gn + j_ = §n + n> then §5 = and §9 " §8 =
6. If c, = 1, and V c , = c + (3n2 + 3n + 1), then c5 =
1 n n + l n 3
7. If gl = 1, and Vn> ± gn = gn_ ± + (2n+ 1), then g4 = .
8. If f , = 2, and V f , = f -2, then f 1 m m + l m
lo
9. If t1= i,andVn>3tn_3= tn_2-i, then 1 10 = .
10. If f, = 1, and V f , = f • —rr> then f3 = and f,
1 nn+i nn+1 3 x
11. If f, = -p, and V f = f • " , , then f4 =
1 1 nn+i nn+1 4
and f
1
12. Suppose that k1 = 1, and that for each n, k - k + — ^
(a) Find the smallest m such that k > 1.11.
in
(b) Find the smallest m such that k > -^r-.
m 9
D. Here is a recursive definition for a function A -whose domain is the set of nonnegative integers.
AQ = 100
V A = 1.03A n n n - i
1. Compute A .
2. How much does $100 amount to if it is deposited in a savings bank for 4 years at 3% interest compounded annually?
^3. Guess an explicit definition for A.
[7.04]
[7-69]
E. Graph each function. [Plot at least 5 ordered pairs.]
Sample, f . = 3, and V f , = f + (5n + 1) v ■ i n n + l n
f Solution,
n 100 -
80 -
60 40 -
20 -
fl = 3' f2 = 9» f3 = 20
f4 = 36, f5 = 57, f6 = 83
[Note that the graph is a set of discrete dots.]
n
fi = °
V f = f + 1
n n + l n
fi = 2
V f . = f +4
n n + l n
fi = °
V f , = f + n n n + i n
fi = l
V f , = f + n
n n+ l n
5.
fi= 1
n n + l n
6.
£!= 1
n
V f , = f nn+i n n+1
7. r £, = 2
v f = l^lli4
n n + i 2f
n
i1 = 2
V f , , = 2f
n n+ i n
F. 1. Each function defined explicitly below has I+ as domain. Give a
recursive definition for each and then use mathematical induction to derive the given explicit definition from the recursive definition.
(a) f = 5n + 1 n
(b) f
n
-3n + 1
(c) f = 3n2 + 1 n
2. The oblong numbers are defined recursively by
B1 = Z
V„ Bn+1=Bn+2<n+1>
Use this and the recursive definition of the triangular numbers
as the basis of an inductive proof of the theorem: V B = 2T_
r n n n
[7-70]
[7.04]
G. 1. Besides triangular and square numbers, the Greeks studied pentagonal numbers, as well as polygonal numbers of still higher orders. Here are pictures showing how triangular, square, and pentagonal numbers are generated geometrically. Study the pictures and the recursive definitions of triangular and square numbers, and figure out a recursive definition for pentagonal numbers, Pn.
• «
V
y
\
' \* \# \"
r
• • •! •
7 n • i •
pl =
V P = P +
^ n n + i n
2. Use mathematical induction to prove:
V P = T + S
n n+i n n+i
3. Notice that the explicit definitions for T and S can be written:
T = _n(n + *)
V S = n(2n^+ °> n n " 2
n n 2 n n
Guess an explicit definition for the function P of Exercise 1, and use mathematical induction to derive it from the recursive definition of Exercise 1.
4. The polygonal numbers of order 3 are the triangular numbers, those of order 4 are the square numbers, those of order 5 are the pentagonal numbers, etc. Let's use 'P'3'' as a new name for T, 4p(4)' for S, lP(5^' for P, etc. So, for example, P(^ is the fourth hexagonal number. From your work on Exercise 1 you should see how to write a pattern for recursive definitions ">f polygonal number functions of all orders.
_,(m+2) _
v p(m+2) = p(m+2)
n
n+ l
n
[7.04] [7-71]
^5. Guess a pattern for an explicit definition of polygonal number functions of all orders:
V p(m+2) = n n
and derive it from the recursive definition you found in solving
Exercise 4.
H. 1. If, in a certain football league, each two teams play just one
game with each other, how many league games are played? For example, how many games are played if the league has 4 mem- bers? 5 members? 1 member?
2. Suppose that, for each n, G is the number of games played by an n-teamed league in which each two teams play together just once. Find a recursive definition for G. [What is Gx? How many additional league games must be played when a new team joins a league which formerly had n members?]
3. Use the recursive definition to compute some values of G. Guess
an explicit definition for G:
V G = n n
and prove your guess correct by deriving this explicit definition
from the recursive definition.
v», v"^ o^
«V *is <v
In solving Part H, above, you found the number of ways in which 2 teams can be chosen from a league with n members. More generally, you learned how to find out, for any n € I+, how many 2-membered sub- sets an n-membered set has. It is customary to abbreviate 'the number of 2-membered subsets of an n-membered set' by 'C(n, 2)' [or, some- times, by 'nC2']. So, the result of Exercise 3 of Part H could be written:
Vn C(n, 2) = n(ly "
In the next exercise you will work on the problem of finding the number, C(n, 3), of 3-membered subsets of an n-membered set.
vO si, si.
[7-72] [7.04]
I. Mark 6 points A, B, C, D, E, and F, no 3 of which are collinear. How many triangles are there each of whose vertices is one of these six points? [This is C(6, 3). Why?] One way of attacking this problem is to ask how many of the triangles have A as one vertex and how many do not. The sum of these two numbers is C(6, 3). [Why?]
Each triangle which has A as one vertex corresponds with some 2-membered subset of the 5-membered set {B, C, D, E, F}. So, the number of such triangles is C(5, 2)--that is, 10.
The number of triangles which do not have A as vertex is the number of 3-membered subsets of {B, C, D, E, F}. [Explain.] This number is C(5, 3). So,
C(6, 3) = C(5, 3) + C(5, 2) = C(5, 3) + 10.
Continue this recursive procedure until you have computed C(6, 3).
*!* «^ «J.
*-,>. *,•«. ^.v
Now, let's find a recursive procedure for computing values of 'C(n, p)'. Suppose that S is a set with n members, and that eQ is some particular member of S. Then S = SQ w {eQ}, where S0 is a particular (n - l)-membered subset of S [in fact, SQ = {eQ}].
Now, SQ has C(n- 1, p) p-membered subsets, and each of these is a p-membered subset of S.
What other p-membered subsets does S have? Obviously, each of the other p-membered subsets of S contains eQ and, in addition, contains p - 1 members of SQ. Since SQ has n - 1 members, S has exactly C(n - 1, p - 1) p-membered subsets which contain eQ.
So, the total number of p-membered subsets of S is
Hence,
C(n- 1, p) + C(n - 1, p - 1).
Vn Vp C(n, p) = C(n- 1, p) + C(n - 1, p- 1).
j^ -j- o-
[7.04]
[7-73]
J. Here is a table for values of 'C(n, p)\ The entry in the 6-row and
|
\ p |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
||||||||||
|
1 |
||||||||||
|
2 |
||||||||||
|
3 |
||||||||||
|
4 |
||||||||||
|
5 |
||||||||||
|
6 |
20 |
|||||||||
|
7 |
||||||||||
|
8 |
||||||||||
|
9 |
3-column is C(6, 3) which, as you discovered in Part E, is 20.
Note that, for the table, we have allowed 0 as a value of 4n* and *p'. What does 4C(5, 0)' mean? What is the proper entry for the 5-row and 0 -column?
What does 'C(0, 5)' mean? What is the proper entry for the 0-row and 5-column?
What is the proper entry for the 0-row and 0-column?
The recursion formula:
V V C(n, p) = C(n - 1, p) + C(n - 1, p - 1) n p
should help us to fill in the table. Try to use it to fill in the entries
in the 6-row. In that case, the instance of the formula is:
V C(6, p) = C(5, p) + C(5, p- 1)
So, to find an entry in the 6-row, you need entries in the 5-row.
To find these, you need entries in the 4-row. Etc Complete the table.
[7-74]
[7.04]
K. Let's recall problem VII of the Introduction, page 7-2:
Whatever route Milton takes in going from his home to Zabranch' burg High School, he has to walk at least nine blocks. How many routes are there which are just nine blocks long?
.Home
ZHS
|
r |
— — |
|||||||
|
1 |
L |
|||||||
|
p 1 1 |
r |
1 |
||||||
|
i i |
||||||||
|
r |
— - |
_i |
||||||
|
"1 |
N
S
-E
During each of his 9 -block walks to school, Milton walks south on each of four blocks and west on five. He has a special page of his notebook on which he keeps track of the routes he takes. The page is ruled into 9 columns headed '1st block', '2nd block', etc., and his record of the route pictured above looks like this :
s 1st ^ 2d b 3d ^ 4th ^ 5th ^ 6th > 7th > 8th ) 9th
W
I
w
S
w
y
w
i
I I
w
s
1. (a) Fill in the next line in Milton's table by writing 4S's in four of the columns [and 'W's in the remaining five].
(b) Mark the route you have described on the figure.
2. (a) In how many ways could you have answered Exercise 1(a)? (b) How many 9-block routes can Milton take?
[7.04] [7-75]
^3. How many 10-biock routes can Milton take from his home to Z.H.S. ?
"^4. How many 11 -block routes can Milton take from his home to Z.H.S. ?
*5. How many 11 -block routes are there in which no block is walked over more than once?
L. Here is another way to solve Milton's problem. During each of Mil- ton's 9-block walks to school he has to walk south for one block at each of 4 different times. He distributes these 4 times of southerly walking among 6 north-south streets. [For the route marked in the figure for Part G, none of his southerly walks took place on the 1st north-south street, 1 took place on the 2nd, none on the 3rd, 1 on the 4th, 2 on the 5th, and none on the 6th. ] So, Milton's problem can be solved by finding the number of ways in which 4 things of the same kind can be put into 6 boxes. Exercise 1 will help you do this.
1. Find a formula for the number of ways of distributing p things of the same kind in n boxes. [Hint. Think of the p things as laid out in a row on your desk. Then, putting them in n boxes amounts to erecting n- 1 partitions.]
2. Use your answer for Exercise 1 to solve Milton's problem.
3. In how many ways can you distribute six pennies among four pockets [right and left coat pockets, right and left trouser pockets]?
4. In how many ways can you distribute six pennies among four pockets so that there is at least one penny in each pocket?
5. How many selections of six coins can be made if each coin is either a penny, a nickel, a dime, or a quarter?
6. How many selections of six coins can be made if each coin is either a penny, a nickel, a dime, or a quarter, and each selec- tion contains at least one coin of each kind?
[7-76] [7.04]
^THE ARITHMETIC OF THE POSITIVE INTEGERS
In proving Theorem 102 we made use of (1*^, (I+2), (I+3) and a theorem about real numbers:
V V x + (y + 1) = (x + y) + 1 x y '
which is a consequence of the apa. [We used this same theorem when deriving the addition table in section 7.01.] Since we are dealing only with positive integers, we could have used a special case:
(I* ) V V m + (n + 1) = (m + n) + 1
\ 4/ m n
of this theorem. If we were unacquainted with the other real numbers, and with our basic principles for real numbers, we might adopt (I+4) as a recursive definition of addition of positive integers. In fact, using (I+ ) -(I+4), alone, it is possible to prove that addition of positive integers is commutative and associative.
Similarly, in proving Theorem 103 on page 7-58 we made use of Theorem 102, (1^), (I+2), U+3)> the pml, and a consequence [step (7)] of the idpma and the pml. [We used the last two when deriving the multiplication table in section 7.01.] Again, since we are dealing only with positive integers, we could have replaced the last two by:
(i*.)
Vm m 1 = m
V V m(n + 1) = mn + m m n
If we were to disregard our basic principles for real numbers, we might adopt (I+5 ) as a recursive definition of multiplication of positive integers. Using {l\) - U+5)» alone, we could prove that multiplication of positive integers is commutative and associative, and is distributive with respect to addition. In fact the whole arithmetic of the positive integers can be derived from (1^ ) - (I+5 ) together with one other pair of principles:
V m + 1 i 1 m
V V if m + 1 = n + 1 then m = n m n
[7.04]
[7-77]
^EXERCISES In answering the following exercises, use:
(I+2) (I+3)
tf+4>
l el+
V n + 1 € r
n
Vs [(1 € S and V [n € S => n + 1 e S]) then Vr n € S]
V V m + (n + 1) = (m + n) + 1 m n
and the logical principle 'V m + 1 = m + 1'. Of course, you may also use Theorem 102 [Why?].
n
^1. Complete the following proof of 'V^ 1 + n Part (i):
(1) (2) (3)
= n + 1\
1+1 = 1 + 1
Part (ii) (4) (5) (6) (7) (8) (9)
(10) V [l+n = n+l=> 1 + (n+ 1) = (n + 1) + 1]
1 + (p + 1) = (1 + p) + 1
Part (iii) (ID
logical principle]
] . 1
inductive hypothesis]
] ]
(5), (6)] (4), (7)]
(9)]
]
^2. Complete the following proof of 'V V V m + (n + p) = (m + n) + p*.
t- t>r mnp
[Hint. Up to the last step, the proof is a test-pattern for sentences of the form 4V in + (n + p) = (m + n) + p' . In completing the proof,
[7-78]
[7.04]
you will find it helpful to look, first, at (2) and (14). Then fill in (15) and (16). Look at ( 14) again. Then, fill in ( 1 3) and ( 12), except for the comment on (12). Finally, complete part (i), and part (ii).
Part (i):
(1) (2)
m + (n + 1) = (m + n) + 1
[U+J] [ 1
Part (ii)
m + (n + q) = (m + n) + q
(3) (4)
(5) n + q e I+
(6) m + ([n + q] + 1) = [m + (n + q)] + 1 (7)
(8) m + (n + [q + 1]) = [m + (n + q)] + 1
(9) (10)
(11) (m + n) + (q + 1) = [(m + n) + q] + 1 (12)
(13)
}
[(12); * ]
(14)
V [m + (n + p) = (m + n) + p =>
m + (n + [p + 1]) = (m + n) + [p + l]]
[(1),
Part (iii) : (15)
[ .
(16)
[(1) - (15)]
[7.04]
[7-79]
3. Complete the following proof of 4V V m + n = n + m'. [Hint. The proof is a straightforward inductive proof. First, fill in (1). Then, fill in (17), (16), (15), (14), and (13), except for the comment on (13).]
Part (i):
(1)
[theorem]
Part (ii)
(2) (3) (4) (5) (6) (7) (8) (9) (10)
(11) (12) (13) (14) (15) (16)
V q + n = n + q
n n n
q + p = p + q
q + (l + p) =(q+ I) +p 1 + p = p + 1
[ ] [theorem]
[ ]
I • 1 [ ] I . )
[(4)
[ [(4)
(5)]
1
(5)]
[ . ] [(1) -(13)] [(14); * ] [(1) -(15)1
Part (iii) (17)
[7-80] [7.04]
MISCELLANEOUS EXERCISES
1 . V V x6 • y6 =
x y '
(A) (xy)6 (B) xy12 (C) (xy)12 (D) (xy)36
2. If it takes x minutes to walk along two sides of a rectangular field 30 feet by 40 feet, how many minutes can be saved by walking diagonally across the field?
3. Find two positive integers whose sum is less than 29 and whose difference is less than 7.
4. Solve this system of equations.
3a - 4b + 1 = 0
a + 2b - 3 = 0
5. Ten pints of a certain liquid contain 70% disinfectant. The rest is water. If 2 quarts of this liquid are drawn off and replaced by
3 pints of disinfectant, what is the resulting ratio of disinfectant to total mixture?
6. Simplify.
(a) Sx3--^ (b) ab'-J^ (c) (a + b) • -y^--
lbx* a b a - b
4 /IT
7. Solve the equation /— = b for 'x'.
8. A grocer mixes coffee worth 88 cents a pound with coffee worth 6 8 cents a pound to make 20 pounds of blend worth 75 cents a pound. How many pounds of the 88 cent coffee should he use?
9. A cylindrical bar made of a certain metal is 5 feet long and 2 inches in radius. Another bar of the same metal is 4 feet long but 3 inches in radius. If the longer bar weighs 50 pounds, what is the weight of the shorter one?
[7.04] [7-81]
10. If A varies inversely as the square of B, and A = 1 when B = 9, then B = when A = 4.
11. Graph {(x, y): |x + 2| < ljf^} r\ {(x, y) : |x + 2| + y < 0}.
12. If a man was x years old y years ago, how old will he be z years from now?
13. Which of the given numbers is the largest?
IA\ l m\ 3 (C\ ^5 m, (0.5)2 ,E. 4/5
(A) j (B) io <c) -TT {D) "oTT" (E) 2
14. Simplify.
(a) (5a2 + ab + c) + (4c - 2az - ab)
(b) (7k2 + k - 2m2) + (5k - 3m2 - 2k2)
(c) (-5mn + n3 + m2) - (2m2 - n3 + 5mn)
15. T «_ ^S What is the sum of the meas-
r ures of the angles ZP, ZQ, ZR,
ZS, andZT?
16. What is the distance between the points (1, 9) and (6, -3)?
17. A nut mixture is l/3 peanuts, 3/l0 almonds, and l/5 cashews. The remainder is pecans, and there are five pounds of these. How many pounds does the mixture weigh?
18. How many pounds of filberts worth $1.03 a pound should be added to 10 pounds of pecans worth $. 76 a pound to make a mixture worth $. 85 a pound?
19. Solve this system of equations. \ 6x + y+3 = 0
3x - 2y + 9 = 0
[7-82]
[7.04]
20.
21.
V
ioo
V.
t =
A
100(V-Vo)
V - V yioo o
^
Given: quadrilateral ABCD is a parallelogram,
AE = EB, DF = FC
Find: the ratio of the area-measure of the shaded region to that of the given parallelogram
Derive a formula for t in terms of A, V, and Vr
J
22. What is the greatest number of circular regions, each with an area of 13 square inches, which can be stamped from a rectangular sheet of steel 9 inches by 13 inches?
23. A motorist buys 14 gallons of gasoline to bring his tank from 20% full to 90% full. What is the capacity of the tank?
24. Simplify, (a)
m - 1
m + 1
(b)
4 -t
5 -t
(c)
10
+
2x - y y - 2x
25. A merchant who had a certain number of bags of flour passed
through thirteen gates of thirteen cities. The curious levy at each gate was one half of what he possessed at the moment. The officer in charge at each gate was his friend. After the levy was paid, each officer gave him one bag as a gift. To his surprise, he still had exactly the same number of bags after he had completed his journey. How many bags did he have? [Chih-yi Wang, Mathematics Magazine, Nov. - Dec, 1959]
26. When successive discounts of 30% and 10% are applied to the list price of an article, the selling price comes to $44. 10. What is the list price?
[7.04] [7-83]
27. A gardener uses 25 pounds of seed for a lawn 50 feet by 90 feet. How many pounds of seed is this per square yard?
28. Simplify.
<a> <!+!><t + t> <b> "-h&th -rrr>
29. Bill and Emily are traveling on their bicycles at 6 miles per hour and 5 miles per hour, respectively. They start at the same place and time, and travel in the same direction. If after traveling 3 hours, Bill turns back, how far from their starting point will they meet?
30. A rectangle and a circle have the same perimeter. Derive a for- mula for the area-measure, K, of the circle in terms of the dimen sions, S. and w, of the rectangle.
31. Complete: V — ^ — = ■=- -
0^ 0 . x + 62.008
32. Solve : x =
33. Simplify.
1.5749
I+i
2 „ v 4 3 , v 12 , 1% 125
(a) 0.8tJ (b) 1"1 (c) ~ (d)
T*4
5 *"' ~ 11 vw 74 v~' 375
1 - -rr'
34. Solve this system of equations.
-14y + 4x = 28 -2x + 7y = -14
35. If tangerines sell 5 for 16£, how much do Z\ dozen cost?
36. If a radius of a circle is x inches long and a side of a triangle with the same area is y inches long, how many inches long is the altitude to the given side?
[7-84]
[7.05]
7.05 The relation greater than for the positive integers. --From our basic principles for real numbers it is possible to prove that
and
(1) there is no least positive number,
(2) between any two positive numbers there is a third.
[Given a positive number, how can you find a smaller one? Given two positive numbers, how can you find one between them?]
Do (1) and (2) remain true if 'number' is replaced by 'integer'? Is there a positive integer less than 1? Is there a positive integer between, say, 5 and 6? Using our basic principles we can show that the answer to both of these questions is 'no'.
The first question is settled by the following theorem:
This theorem can be proved easily by mathematical induction. You will be asked to do so in the next set of exercises. The second question is settled by:
(*)
V V [n > m
m n L
n > m + 1]
For, according to (*), if a positive integer is greater than 5 then it is greater than or equal to 6- -that is, if it is greater than 5, it is not less than 6. So, 6 is the next positive integer after 5.
How can we prove (*)? We note that (*) is equivalent to:
V V [n > m => n - m : 1] m n L — J
And, we could use Theorem 104 to prove this once we have proved:
Theorem 105.
V V [n > m
m n L
n - m e I+]
[Explain.] [Theorem 105 is assumption (3) on page 7-47.]
[7.05] [7-85]
So, let's prove Theorem 105. A straight -forward induction will do the job. To do so, we must prove:
and:
(i) Vn [n > 1 => n - 1 el+]
(ii) V [V (n > m => n - m e T) => ' m L n
V (n > m + 1=> n - (m + 1) € I+)]
n
Consider (i). By Theorem 87, if p > 1 then p f 1. [Explain.] So, we could prove (i) if we could prove:
(a) Vn [n/* 1=> n - 1 el+]
And, we could prove this if we could prove:
(b) V [n = 1 or n - 1 € I+] [Explain.]
Now, (b) is easy to prove by induction. Here's how.
Clearly, since 1 = 1, it follows that
1=1 or 1 - 1 e I+ Also, since (p + 1) - 1 = p and p e I+, it follows that
p + 1 = 1 or (p + 1) - 1 € I+. Hence [by conditionalizing and generalizing],
V [(n = 1 or n - 1 e I+) => (n + 1 = 1 or (n + 1) - 1 e T)]
Thus, by mathematical induction, (b) .
SO;, we have established (i) . Now, on to (ii).
Suppose that Vn [n > p '■=> n - p € I+]. Further, suppose that q > p + 1. Then, q - 1 > p. Since p + 1 > p >L 1 , it also follows that q > 1. So, from (i), q - I e I+ and, from the inductive hypothesis, (q - 1) - p e I + . But, (q - 1) - p = q - (p + 1). So, q - (p + 1) e T. Hence, Vn [n > p + 1 => n - (p + 1) € I*]. Consequently, (ii).
So, from (i) and (ii), by mathematical induction, Theorem 105.
[7-86]
[7.05]
EXERCISES
A. Prove.
1. Theorem 104
V n + 1 > 1 n
B. 1. Show that (a) and (b) on page 7-8 5 are equivalent by deriving (b) from (a) and (a) from (b).
2. Prove: V if n 4 1 then n > 2 [Hint. Use (a) and Theorem 104.1
n ' — L J
3. Show that 1 is the only positive integer between 0 and 2. [Hint. Use Exercise 2.]
C. 1. Use Theorems 104 and 105 to prove (*) on page 7-84 2. Prove the converse of (*) .
J, «A. «A.
*-,v +,<*
V T *X
(*) and its converse give us :
Theorem 106.
V V [n > m + 1 <=> n > ml
m n L — J
o, *^ *•> 'iv *ix *in
D^. 1. You know how to prove '5 e I * and *6 e I '. Accepting these theo rems prove that, for each x, if 5 < x < 6 then x tf 1* .
2. Prove: VV [n < x < n + 1 "=> x fi' I+]
n x l * J
IS. Prove each of the following. 1. V n/t 1
n
2. V V [n < m + 1 <=> n < ml m n L — J
[Theorem 107a] [Theorem 107b]
rF_. Prove (1) and (2) on page 7-84.
[7.05] [7-87]
LOWER BOUNDS AND LEAST MEMBERS
Consider the set P of all positive numbers. We have noted earlier that P has no smallest member—that is, there is no positive number which is less than every other positive number. But, there is a real number x such that, for each y € P, x <_ y. Name one such real number. Name another. How many are there? Each such real number is called a lower bound of P .
You have seen that P does not have a least member but that it does have many lower bounds. Does P have a greatest lower bound?
Consider the set K of all positive integral multiples of 3. Does K have a least member? Does K have a lower bound?
Consider {x: x > 6}. Does this set have a least member? Does it have a lower bound?
Consider {n: n > 6}. Does this set have a lower bound? Does it have a least member? [Recall what the domain of 4n' is.]
Consider the set of negative integers. Does it have a least member? Do you think it has a lower bound? Do you think the set of positive integers has an upper bound? [To settle these last two questions, we'll need another basic principle.]
By now you probably have a good idea of what is meant by *a lower bound of a set of real numbers' and 'a least member of a set of real numbers'. But, for definiteness, here are formal definitions:
V.. V [x is a lower bound of S <==> V _ x < yl S x L y € S — 7i
VQ V [x is a least member of S <^=> o x
x is a lower bound of S and x e S]
Use the first definition to prove that each number which is less than some lower bound of a set is also a lower bound of the set.
Using both definitions and Theorem 93, you can prove that a set cannot have two least members. Do so.
Suppose that S is a set of real numbers. If S has a least member, must S have a lower bound? If S has a lower bound, must it have a least member?
Suppose that T and S are sets of real numbers such that T C_ S. If S has a lower bound, does T? If S has a least member, does T? If T has a lower bound, does S? If T has a least member, does S?
[7-88]
[7.05]
THE LEAST NUMBER THEOREM
A set which has a least member is certainly not empty. But, as you have seen, there are many nonempty sets of real numbers which do not have least members. One of the most useful theorems about I+ says that none of its subsets is of this kind:
Theorem 108.
Each nonempty set of positive integers has a least member.
This theorem is often called the least number theorem. [An equivalent formulation is: Each set of real numbers which contains a positive inte- ger contains a least positive integer.]
We shall prove the least number theorem by showing that the only set of positive integers which has no least member is the empty set.
Suppose that S is a set of positive integers which has no least mem- ber. Since 1 is the least positive integer, and since S is a set of positive integers, 1 is a lower bound of S. Since S has no least member, 1 i S. So,
(i) VjneS=> 1< n].
n
Suppose now that V [n e S ■=> p < n]. By Theorem 106, it follows [using the substitution rule for biconditional sentences] that
V [n e S => p + 1 < n]
n
--that is, that p + 1 is a lower bound of S. So, since S has no least member, it follows that p + 1 ( S. Hence, V [n e S ~=> p + 1 < n]. Consequently,
(ii) V [~V (n e S =s> m < n) => V (n e S => m + 1 < nfl. mLn n J
From (i) and (ii) it follows, by mathematical induction, that
' m < n].
In particular, V [n e S ==> n " n] . Since V x i- x, it follows that V n g S. --that is, that no positive integer belongs to S.
The least number theorem is assumption (5) on page 7-47. It is interesting to recall how we used this theorem back in Unit 4. We were
V V [n e S
m n L
[7.05] [7-89]
trying to show that there is no positive rational number whose square is 8. We argued that if there were such a rational number, V8, then there would be positive integers p and q such that v8 • q = p--that is, that {q: V"8 *q € I+} is not empty. From this supposition and Theorem 108 it follows that there is a least positive integer q such that V8 • q € I+. Then we proceeded to derive a contradiction, and so concluded that there is no positive rational number whose square is 8. [Notice that up to now we have not shown that there is any positive number whose square is 8. All we know is that, if there is such a number, it is not a rational num- ber. In a later unit we shall adopt a final basic principle which will make it possible to prove that each positive real number has a positive square root. ]
THE COFINALITY PRINCIPLE
A few paragraphs back we raised the question of whether there is a lower bound for the set of negative integers. By Theorem 94, this is equivalent to asking if there is an upper bound for the set of positive integers. And, from our intuitive knowledge of the real numbers, we would be inclined to say 'no'. That is, we believe that there is no real number which is greater than or equal to each of the positive integers. In still other words, we believe that, for each real number, there is a positive integer which is greater than it. As a matter of fact, this is so, but it cannot be deduced from the basic principles we have set down up to now. So, let us now take this as a basic principle.
Cofinality Principle
V 3 n > x x n
[How do you read '3 '?]
When, in a later unit, we adopt our final basic principle for the real numbers, we shall see that the cofinality principle then becomes a theorem.
From the cofinality principle it follows that V 3 n> -x. [Explain.] So, Vx3nx> -n. Hence, Vx3nx^-n. But, this is just to say that no real number is a lower bound of the set of negative integers.
[7-90] [7.05]
EXERCISES A. Give an example of a set S of real numbers which has
1. both an upper bound and a lower bound;
2. a lower bound but no upper bound;
3. an upper bound but no lower bound;
4. neither an upper nor a lower bound;
5. a greatest member but no upper bound;
6. an upper bound which belongs to S;
7. a least upper bound which does not belong to S; **&. a lower bound but not a greatest lower bound.
B. 1. Prove: V . n 3 x > -
— x > 0 n n
2. Suppose that &, = I+ and that, for each n, f = — . «*r f n n
(a) Does &f have an upper bound? A lower bound?
(b) Does (ft- have a greatest member? A least member?
» i i w nil,
1 ' ' (-1)
3. Repeat Exercise 2 with — replaced by
n n
• ■ *
1 * * n - 1 '
4. Repeat Exercise 2 with — replaced by
n n
C. 1. What does Theorem 108 tell you about (n: 3 xn = m) if x is
— } v m J
(a) a positive rational number? (b) an irrational number?
*2. Suppose that m > n. Show that there is a p such that 0 < m - np < n. [Hint . Consider {q: 3 q = m - np}.]
D. 1. Suppose that, for each n, f = n(n + 1) and g = (n + -=-)2.
(a) Prove: V „[f = g => f = g ]
n L n &n n + l en + iJ
(b) In (a) you gave part (ii) of an inductive proof of the generali- zation 4Vnfn = gn'. Is f4 = g4? Does your answer contradict the result you obtained in (a)? Explain.
[7.05] [7-91]
2. Consider the following generalization:
(*) V V [n < m ^^ n = m]
x ' m n L — J
(a) Give a counter example for (#).
(b) Criticize the following purported proof of (*) :
(i) From Theorems 104 and 93 it follows that
V [n < 1=> n = l]<
n L — J
(ii) Suppose that V [n < p => n = p]. Further, suppose that q < p + 1. Then, q - 1 £ p. So, from the inductive hypothesis, q- 1 = p, and q = p + 1. Hence, V [n < p + 1 => n = p + 1], Consequently,
n
V
m
V [n < m=> n = ml => V [n < m + l=> n = m + l] n L — J n L — J
(iii) So, from (i) and (ii), by mathematical induction,
V V fn < m => n = m]. m n L — J
(c) Compare (b) with the proof of Theorem 105 on page 7-85.
MISCELLANEOUS EXERCISES
1. For each n, C is the number of subsets of an n-membered set.
n
(a) Find a recursive definition for C. [Hint . Suppose that SQ is an n-membered set and that eQ ^ SQ. Then, SQ w {eQ} is an
(n + l)-membered set, S. How many subsets of S do not contain eQ ? How many do contain eQ?]
(b) Show that each nonempty set has the same number of odd- membored subsets as it has even-membered ones. [Check this result in the table you completed on page 7-73.]
(c) A ladder which reaches just to the roof of a building has 10 rungs By how many routes can a beetle climb along the ladder, from the ground to the roof, supposing that, on each route, he never retraces his path?
[7-92] [7.05]
2. Each function defined below has I+ as domain. Give a recursive definition for each and then use mathematical induction to derive the given explicit definition from the recursive definition.
(a) f = 7n + 1 (b) fn = 7n + 9 (c) fR = -n
(d) f = 6 - 5n (e) f = n2 (f) f = 2n2 - 5
N ' n n n
3. Each of the following generalizations is false. Give a counter- example for each.
'^Vo^ = 5 (b) v*^-*-1
(c) Vo lZk + k =k (d» Vx/3 -IFTT = ~2
4. If the length- and width-measures of a rectangle are doubled, by what per cent does the area-measure increase?
5. The surface area-measure of a solid cube is 16 times that of a second cube. If the cubes are made of the same substance and the larger cube weighs 80 pounds, what does the smaller one weigh?
6. Simplify.
(a) 8rs - 2r2 + 7s2 + (2r2 - 3rs - s2) - (r2 - s2)
(b) 7x(2x2 - 3x + 2) - 5x(4x - 3x2 + 1) + (x - 2)2
(c) (3a - 2b)(a + b) - 4(a + 2b)(a - 3b) - 5(a - b)(a + b)
7. How much longer does it take a train to travel 1 mile at 55 miles per hour than at 60 miles per hour?
8. AABC and AADC are inscribed in a circle for which AC is a diam- eter. If AB = 1, AC = 5, and AD = 3, find CB and CD.
9. Find an ordered pair (x, y) such that x - y = 8 and 5x + 2y - 5 = 0.
[7.05] [7-93]
10. hn = E + -=-mv2 ) Derive a formula for V in
. / terms of h, n, E, and e.
eV = imv2 J
11. Solve the equation 'm = r- ' for ln'.
1 - -
n
3
12. Suppose that A = c"B. What is the value of A for an argument for
which A and B have the same value?
13. Find the coordinates of the midpoint of the segment whose endpoints have coordinates {y, -^-) and (-5-, y) .
x x 14. For each positive integer x, 3 • 9 =
(A) 27X (B) 272x (C) 33x (D) 93x (E) 32x
3 1
15. If you subtract ^- from a number and get -=-, what would you get if
3
you added — to the number?
7 4
16. If a pipe 3 inches in diameter can drain a tank in x minutes then a pipe 4 inches in diameter can drain the tank in minutes.
17. If it takes 24 days for 20 people to consume a certain stock of food, how long would it take 25 people to consume it?
18. Solve: x%(800) = 32
19. Simplify.
, . a2 + 7a + 12 ^ a2 + 4a - 5 ,. . rs + r . r2s + r2
(a) ^ + 2a - 3 X "im <b> — sT~ T ~ 3i~
20. If (0, 3) and (1. 5, 0) belong to a linear function f, which ordered pair of f has equal components?
[7-94]
[7.06]
7.06 The integers. --Up to now, in our study of real numbers, we have introduced some basic principles to single out the positive real numbers and some other basic principles to single out the positive integers. We also adopted the basic principle (G) in order to introduce the relation >, and the cofinality principle to help specify how the positive integers occur among the real numbers.
The next step in our program is to study the set, I, of integers -- positive, negative, and 0. We already know what real numbers these are, and we formulate this knowledge in a basic principle:
(I) V [x e I <=> (x e I+ or x = 0 or -x e I+)]
So, to say that a real number is an integer is to say that it is a positive integer, or is 0, or its opposite is a positive integer.
Our first theorem gives us another way of characterizing the set of integers. Read it carefully and see if you believe what it says.
|
Theorem 109. |
||
|
V [x e I <= x L |
-> 3 3 x = m ■ m n |
-n] |
This theorem tells us that a real number is an integer if and only if it is a difference of positive integers. Using the basic principle (1) it is easy to prove that this is so. Here is a proof.
In the first place, suppose that m and n are positive integers. If m > n then, by Theorem 105, m - n € I+; so, by (I), m-nel. If m = n then m - n = 0; so, by (I), m - n e I. Finally, if n > m then, by Theorem 105, n - m € I+. But, n - m = -(m - n) . So, if n > m then -(m - n) e I+. Hence, by (I), m - n € I. Since, in any case, m> norm = norn> m, it follows that each difference of positive integers belongs to I.
In the second place, suppose that a real number a is an integer. By (I), either a e I* or a = 0 or -a e I+. Suppose that a e 1* . Then, by (I+2), a + 1 € I+. Since, by (1^), 1 e I+, and since a = (a + 1) - 1, it follows that a is a difference of positive integers. Suppose that a = 0. Since 1 e I+
[7.06]
[7-95]
and 1 - 1 = 0, a is, again, a difference of positive integers. Finally, suppose that -a e I+. Then, as before, -a + 1 e I+, 1 € I+, and a = 1 - (-a + 1). So, again, a is a difference of positive integers. Hence, each integer is a difference of positive integers.
Just as, for the purpose of stating generalizations about positive integers, it was convenient to introduce special variables [4m', 4n', 4p', 4q'] whose domain is I+, so, in stating generalizations about integers it will be convenient to use special variables whose domain is I. For these we shall choose the letters 4i', 4j', and 4k'.
Among such generalizations are those which say that I is closed with respect to opposition, addition, subtraction, and multiplication. [Is I closed with respect to division?]
|
Th |
eorem |
110. |
||
|
a. |
V. J |
-j |
e I |
|
|
b. |
V. J |
\ |
k + j e |
I |
|
c . |
V. J |
\ |
k - je |
I |
|
d. |
V. J |
\ |
kj e I |
Let's prove the first two parts of this theorem.
Suppose that j is an integer. Then, by Theorem 109, there are positive integers m and n such that j = m - n. So [by Theorem 33], -j = n - m. Hence, by Theorem 109, -j € I. This completes the proof of part a.
Suppose that j and k are integers. Then, by Theorem 109, there are positive integers m, n, p, and q such that
k = m
n
and
j = p - q
So, k + j = (m - n) + (p - q) = (m + p) - (n + q). Since I+ is closed with respect to addition [Theorem 102], m + p e I+ and n + q e I+. Hence, by Theorem 109, k + j e I. This completes the proof of part b. Now, prove parts c and d.
[7-96]
[7.06]
Here are other theorems about integers which you can prove:
|
Theorem 112. |
|
|
V. V [k + 1 > i <= |
=> k > j] |
The proof of Theorem 111 involves the same techniques used in proving Theorem 110. To prove Theorem 112 use Theorems 111 and 104, and theorems on > .
EXPLORATION EXERCISES
A. 1. Suppose that S = {k: k > -7}. Describe the set, S , obtained by subtracting -5 from each member of S.
2. Let t be the function [mapping], whose domain is I, such that t (k) = k - -5. Complete this picture to show the mapping t_g.
-8-7-6-5-4-3-2-10 1 2 3 4 5 6 7 8 9
<e-| , 1 \ 1 , 1 1 1 1 , , , 1 1 1 1 ,_>
I*-!
H h
4->
-8-7-6-5-4-3-2-10 1 2 3 4 5 6 7 8 9
3. What is the range of t_ ? Does t have an inverse? Onto what set does t_5 map {k: k > -5}?
4. For a given integer j, let t. be the function such that, for each integer k, t. (k) = k - j.
(a) What is the range of t.?
(b) If i > k, what can you say about t. (i) and t. (k)?
J J
[7.06]
[7-97]
(c) Look at Part H on page 7-41. The results there hold just as well for functions whose domain is I. So, what do Exercises 1 and 2 of Part H tell you about t.?
5. (a) Describe the set obtained by applying t_10 to each member of {k: k > ~10}„
(b) Describe the set obtained by applying t27 to each member of {k: k > 27}.
(c) Describe the set obtained by applying t. to each member of {k: k > j}.
B. 1. Let r be the function, whose domain is I, such that r(j) = -j. Draw a picture like that in Exercise 2 of Part A to show the mapping r. Does r have an inverse?
2. For each set listed below, describe the set obtained by applying r to each of its members.
(b) {j: j < 5}
(d) {j: -6 < j < 5}
(0 0: j < k}
|
(a) {j: j > -1} |
|
|
(c) {j: -5 < j < |
-4} |
|
(e) {j: j < -8} |
3. Look at Theorem 94. Use it to complete the following statement
V V. [r(i) > r(j) ]
J
4. (a) Pick a real number. By the cofinality principle, you know that there is an integer which is greater than this real num- ber. Can you prove that there is an integer which is less than this real number? [You can do this by using the cofi- nality principle to get an integer which is greater than the opposite of the chosen real number. ]
(b) Suppose that a set S has a lower bound. Prove that it has an integral lower bound.
[7-98]
[7.06]
THE LEAST NUMBER THEOREM FOR INTEGERS
Consider a nonempty set S of integers. If S contains only positive integers then, as we have proved [Theorem 108], S has a least member.
On the other hand, we know that if S contains negative integers, it may not have a least member. Give an example of such a set. Now give an example of a set of integers, some of which are negative, which does have a least member. Can you guess a theorem?
Theorem 113.
Each nonempty set of integers which has a lower bound has a least member.
For, suppose that S is a nonempty set of integers which has a lower
bound. Then, by the cofinality principle, there is an integer j which is
less than each member of S. [Explain.]
Now, let t. be the function, whose domain is I, such that t-(k) = k- j. J J
Let S'f be the set obtained by applying t. to each member of S. Then,
S>c C^ I+ [Explain], So, by Theorem 108, S ,s has a least member m.
Since m e S*, there is a k 6 S such that t • (k) = m. Since m is a lower bound of S*, k is a lower bound of S [Why?]. So, S has a least member, k
The proof of Theorem 113 illustrates a general method for deducing theorems about integers from analogous theorems about positive integers. In Part A of the preceding Exploration Exercises you discovered certain properties of the functions t;. For a given integer j, the essential prop- erty of t- is that it maps the set of integers greater than j on the set of
positive integers in such a way that order is preserved. So, for example, lower bounds of a subset S of {k: k > j} are mapped onto lower bounds of the image of S. And, by Part H on page 7-41, it follows that each lower bound of the image of S is the image of some lower bound of S. In general,
[7.06]
[7-99]
because ti has this property, anything you can say about the positive integers which has only to do with their order, you can also say about the set of integers greater than j.
For example, the principle of mathematical induction gives us a method for proving theorems concerning {k: k > 0}. Using the prop- erties of the function t. , for any j, we can transform the principle
J of mathematical induction [see page 7-49] into a principle which enables
us to prove theorems concerning {k: k > j - 1 } --that is, {k: k _> j}. Theorem 112 tells us that, for each k, k + 1 is the least integer > k. So, the PMI tells us that, for each set S,
if
(the least integer > 0) € S and
k> 0
[k e S — > (the least integer > k) e S]
then
Vk>okeS'
It is easy to see that the validity of this result depends only on the way in which the positive integers are ordered. Since the members of {k: k > j - 1} are ordered in the same way, we may replace the 40's in the statement above by lj - l's. Since
(the least integer > j - 1) = j, k > j - 1 <=^> k > j, and (the least integer > k) = k + 1,
we have the following theorem:
Theorem 114.
(] e S and Vk >
±)
[k e S => k + 1 6 S])
V1S .keS
We can use this theorem to give us mathematical induction principles for proving theorems about all integers greater than or equal to some specified integer j. For example, in case j = 1 , the corresponding instance of Theorem 114 is equivalent to the PMI itself.
In Part B of the Exploration Exercises you worked with the function r such that, for each j, r(j) = -j . This function maps I onto itself in such
[7-100]
[7.06]
a way that order is reversed. So, for example, lower bounds of a set S of integers are mapped by r onto upper bounds of the image S of S. Similarly, upper bounds of S are mapped onto lower bounds of S*. From this and Theorem 113 we have:
Theorem 115.
Each nonempty set of integers which has an upper bound has a greatest member.
Also, since, as Theorem 114 tells us, we can do mathematical induction "upward" from any given integer, so we can do mathematical induction "downward" from any given integer. Using the order-revers ing property of r we can obtain from Theorem 114:
Theorem 116.
(jcSand Vk£j[keS=> k-1 eS])=> Vk<. keS
From Theorems 114 and 116 we obtain a theorem of mathematical induction for the set of all integers :
Theorem 117.
(0 € S and V, [k € S => (k + 1 € S and k - 1 e S)]) => V k e S
1.
EXERCISES
Complete the following recursive definition of the numbers, D , of diagonals of an n -sided polygon:
V . - D , =D + n >^ 3 n + i n
[Hint . Draw a diagonal joining a vertex to a next but one. ]
2. Discover an explicit definition of D:
n > 3 n
3. Use the appropriate instance of Theorem 114, and derive the explicit definition from the recursive one.
[7.06] [7-101]
MISCELLANEOUS EXERCISES A. 1. Here is a recursive definition for a function f:
= f
nn+i n n + 2
(a) Compute f2, f3, f4, and f5.
(b) Guess an explicit definition for f, and try to derive it from the recursive definition by mathematical induction.
n + 1
2. If, for each n, g = then, for each n, g = — JTT'
3. If, for each n, gn = n(n + 1) then, for each n, g = gn +
4. Complete these generalizations about the positive integers.
/ » ^ n 1
[*} n n+l (n+l)(n+2) " n+2
(b) V n+1 + I =
K ' n n + 2 (n+2)(n+3) n+ 3
. . w n + 2 j 1
n n + 3 (n+ 3)(n + 4)
u, w n + 3 , n + 4
n n + 4 n + d
B. 1. Complete.
(a) V x3 + 1 = (x + 1)( ) (b) Vv x3 - 1 = (x - 1)( )
■A. X
2. If — = — + — find the value of s which corresponds with the value
r s t r
6 for r and 4 for t .
3. If a cubic centimeter of water weighs 1 gram, how many kilograms of water will fill a rectangular container 45 cm. by 35 cm. by 8 cm.?
i
4. If the square of the sum of two numbers is 16 and the square of their difference is 4, find their product.
[7-102] [7.06]
THE GREATEST INTEGER FUNCTION
One consequence of the cofinality principle is that, given a real number, there is an integer less than or equal to it. That is, for each x, {k: k <. x} f 0. Since the nonempty set {k: k <^ x} has an upper bound [Explain.], it follows from Theorem 115 that it has a greatest member.
For each of the sets listed below, give its greatest member.
(1) {k: k < 4.3} (2) {k: k < 2y}
(3) {k: k < 13/3} (4) {k: k < tt}
(5) {k: k < 8} (6) {k: k < -1.3}
(7) {k: k<?r/2} (8) {k: k<2/3}
(9) {k: k< -0.5} (10) {k: k<2223/llll}
Instead of writing:
the greatest member of {k: k <^ x} it customary to write:
Read 'HxJ' as 'brackets x' or as 'the integral part of x'. So, for exam- ple, instead of asking: What is the greatest member of {k: k < 4.3}? we can ask: What is [4. 3 J?
Now complete the following sentences:
(H) [[7. I] = (12) [[0I| = (13) E-5.2D =
(14) [7T+ 1J = (15) I-6]| = (16) [[0. 62] =
Here is a list of the integers.
..., -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, ...
(17) Where would you draw a line to separate the integers which are less than or equal to ir from those which aren't?
(1.8) Where would you draw a line to separate the integers which are less than or equal to ([ -n J from those which aren't?
(19) Repeat (17) and (18) for the real numbers /I, >/l, V4, and -/IT.
[7.06] [7-103]
Questions (17) -(19) suggest the following theorem which follows immediately from the definition of '[[... ]]':
v \ [k 1 ttxH <==> kl xl [Theorem 118a]
EXERCISES
A. 1. What is the greatest member of {k: k < 4.3}? What is the greatest member of {x: x < 4. 3}?
2. Which of the following do not stand for integers?
(a) [[7.5]] (b) [[7.5 + 7.5] (c) [ 7. 5 ] + |[7. 5 ] (d) 19+2.7]) (e)9 + [2.7j (f)|[9] + 2.7
(g) 12.9.6] (h) 2[9.6] (i) Ij'9.61 (j) i|[9.6]
3. (a) Use Theorem 118a to prove: V [[ x ] < x
[Hint. By Theorem 118a, the integer [[ c ] is less than or
equal to c if and only if it is less than or equal to [[ c J. But, . . . ]
(b) Use part (a) to prove: V 2 {[ x ]] < 2x
(c) Use Theorem 1 1 8a and part (b) to prove : V 2[[xj£[[2x]]
A
(d) Use part (a) to prove: V y{[x]] < yx
(e) Prove or disprove: V y{[x]] £ Hyx]j
(f) Which of the following is a theorem?
(i) vx vk>0kttxli- HkxB
(") Vx Vy>Q ylx]< [yxl
(g) Tell which of the following is a theorem and prove it. (i) Vx Vk Jx]] + k < ffx + kj
(ii) V V [xj + y < Ix + y]
* y
(h) Prove or disprove: VV JxJ + dyJ^Ix + yJ
x y
[7-104] [7.06]
B. The set of ordered pairs,
{(x, y): y = [x]},
is a function which maps each real number onto the greatest integer not greater than the real number. So, it is sometimes called the greatest integer function.
1. Make a sketch of the greatest integer mapping.
_4 -.3 _2 -1 0 12 3 4 5 6
1 1 1 1 j , 1 1 1 , ,
H 1 h
-4-3-2-10123456 2. Graph 4y = [xj\ 3. Graph 4y = [x + 1 J'.
*'- <A, *J* T- T "lN
You probably discovered in Part A that
Vx j[x+ I]] = [x]|+ 1.
Let's try to prove this.
In Exercise 3(g) of Part A you used Theorem 118a to prove a theorem which tells you that
Vx [xj + 1 < |[x+ lj.
So, by Theorem 93, all we have to prove is that
Vjx] + 1 > Ix+ 1].
Evidently, to prove this, it would be helpful to have a theorem like Theo- rem 118a but which would start with:
VxVk[k> Ix] «=>
Theorem 118a, with the help of Tiieorem 88, tells us that, for any real number c and any integer k,
(*) k > [cj <=> k > c. [Explain.]
This tells us about > rather than >. But, > -sentences about integers can be translated into > -sentences with the help of Theorem 112. In fact, for integers k and j,
(**) k > j <=> k + 1 > j.
[7.06]
[7-105]
By (*), since k + 1 is an integer,
k+ 1 > [cj <=> k + 1 > c. [Explain.]
So, since [cj is an integer, it follows from (*) and (**) that
k > [cj <=> k + 1 > c.
Consequently,
Now we can prove :
V V, [k > |[x J <=> k + 1 > x]. [Theorem 118c]
x k
VxIx] + 1 > [x+ 1] Since, for any c, [[ c J + 1 is an integer,
He J + 1 > |[c + 1]
<==> ([c J + 1) + 1 > c + 1 <=> [[c] + 1 > c <=> II cj > Ic].
Theorem 118c
\ Why?
Theorem 1 18c, |[ c ]} is an integer
So, since each real number is greater than or equal to itself,
ffcj + 1 > Ic + I]].
Consequently, V [x]+l>[[x+l]|.
Notice that Theorems 118a and 118c can, with the help of Theorem 93, be combined into:
Theorem 118e.
VxVk[k = JxJ <=> k < x < k+ f)
This theorem gives us a quick way of proving that a given integer is the integral part of a given real number.
O- o^ «J, ■T* "V T
C. Use Theorem 118e to prove:
VVV. fl> + jB = [xj + j [Theorem 119]
[Hint. Since, for any real number c and any integer j, [[ c ]] + j is an integer, all you need, by Theorem 118e, is to show that
Ic] + j<c + j<(|[c]| + j) + l. Use Theorem 1 1 8e to show that [c]l<c<|[c]|+l.]
[7-106]
[7.06]
D. Exercise 3(h) of Part A tells you that the integral part of the sum of two real numbers is at least as great as the sum of the integral parts of the real numbers. Can it be greater? By how much? Prove this.
E. 1.
Consider the real numbers 93 and 18. It is possible to find an integer k such that
18k<93< 18(k+l). [Find it.]
In fact, given any real numbers a and b, b > 0, there exists an integer k such that
kb < a < (k + l)b
Prove that such an integer exists. [Hint. In the example about
(19 3"*
93 and 18, did you see that the sought -for integer is
18
?]
2.
In Exercise 1 you proved the following theorem:
V V . n 3, ky < x < (k + l)y x y > 0. k '
Now prove :
(a) VxVy>03k°^X-ky< V
(b) VxV > ^ 3z (x = ky + z and 0 < z < y) [Theorem 120]
3. Use the cofinality principle on page 7-89 to prove:
V V . „ 3 ny>x [Theorem 121]
x y > 0 n 7 L J
F. 1. Graph both *y = HxJT and *y = tt -*]' on the same chart
2. Graph 4y = -|[-x]|\
3. Complete:
Vx -ff-xj =the
integer k such that x [Theorem 122]
4. The U.S. Post Office has a book rate of 9 cents for the first
pound and 5 cents for each additional pound or fraction of a pound. Find the formula for the postage c, in cents, for a parcel of books which weighs w pounds.
[7.06]
[7-107]
G. On a picture of the number Line, graph the solution set of
[5.36J + [x] = [5.36 + xj
V«* VV ^l-
'Is "|> "1N
Since , for each x, [xje I and [ x ] < x < |[x]|+ 1, it follows that, for each x, there is an integer k, namely ffx]|, such that 0 < x - k < 1. Instead of writing 'x - [xj' it is customary to write '{[xj' [read as 'braces x' or as 'the fractional part of x'].
V x = [xj+ fxj, where [ x J € I and 0 < ffx} < 1
The set of ordered pairs,
{(x, y): y = « },
is a function, and is sometimes called the fractional part function
•Jt* O^ <J^ "T* "lx *jx
H. 1. Graph 'y = {fxj\
2. State, and prove, a theorem about the fractional part function analogous to the theorem about the greatest integer function which you proved in Part C.
I. Solve.
1. [5.36]) + [x] = [5.36 + xj
2. [5.36J + [xj < [5.36 + xj
-sir
J^. Compute .
75621'
1.
4.
10
[75621
I 104
10
10
7. V
k> 5
75621
2.
5.
75621
\L io^
75621 105
10
-]]
10
10
10
3.
6.
75621
'75621 106
10
10
Ox
[7-108]
[7.06]
8. Find the positive integer n which satisfies the following six sen- tences.
10]
10<
10
10
= 7
= 5
102
105
10
10
•j.
= 3
= 5
n
10:
k> 5
10
n 101
= 0
10
= 0
9. Complete without doing any dividing or multiplying.
(a)
357829630572164
10
n
10
(b)
1T68257934625TI . [I! 1035 jf
10. Repeat Exercises 1-6 with each *10' replaced by an 48'. Then, formulate a theorem like that in Exercise 7.
11. Recall the results of Exercises 1-6 and that
75621 = l_ + 2« 10 + 6/ 102 + 5_- 103 + 7- 104.
Now, interpret the result of Exercise 10 by completing and checking 75621 = 5 +
12. Use the facts that
15278 = 4+5-7 + 3- 72 + 2 • 73 + 6- 74
and that
15278 = 2 + 1 • 12 + 10 • 122 + 8- 123
to complete the following: 15 27811 -
(a)
(c)
15278
(b)
(d)
15278 123
15278 125
nL Vl^ O-p
T* "Jv *'l>
12
12
In doing the exercises in Part J you discovered a technique for 'splitting" each positive integer into multiples of powers of a given
[7.06]
[7-109]
integer greater than 1. When the given integer is 10, the splitting leads to the customary decimal notation for positive integers. As you probably guessed, or perhaps know, it is possible to use bases other than 10 in a place value system of names for integers. For example, the integer whose name in the decimal system is '75621' is named '223545' in the base-8 system. Let's find the base-6 name for this integer. According to the procedure illustrated in the exercises, the units digit is obtained by simplifying:
ilnty 0 ■ I2'" ♦ 0 '] ■
3
o"
= 3
The sixes digit is obtained by simplifying:
75621 62
Instead of computing 75621 v 36 directly by long division, we can make
use of the fact that 75621 4- 6 = 12603 + f .
o
75621
12603 +
2100 + £ + ^g-V
o" + 3o" 6
-!
= 3
Now there is a short cut here. Instead of computing
3
12603 +
we could have computed
12603
[Check this. ]
This suggests a very simple procedure for finding the digits.
[7-110]
[7.06]
6 6
75621
12603
2100
350
58
6
6
9
1 0
3 0 2 4 3 1
\ Remainders
j
So, the base-6 name for 75621 is * 13420 3 3' --that is,
75621 = 3+3-6 + 0-62 + 2-63 + 4-64+3'65+ 1 • 66
[Check this. ]
The short cut used here is a consequence of the theorem:
75621
1L6P " l M
Similarly, the digits obtained in Exercises 1-6 of Part J by evaluating
'75621
10'
10
for the values 1, 2, 3, . . . , 6 of 4p', can be obtained by evaluating, in- stead:
r~ tT
75621
]_10
p-1
J) /no
10
Evaluate the two expressions for the value 3 of 'p'.
The short cut, in general, depends on the theorem
V V x m
&
m
JIM.
m
m
To understand this theorem, consider a real number c and a positive
c integer p. Since — is the sum of its integral part and its fractional part,
(*)
I**©
— >>p and 0 <
[7.06]
[7-111]
In words: one can divide a real number c by a positive integer p in such a way as to obtain an integral partial quotient, — L and a nonnegative remainder, (f~T)p» less than p. [What has been said up to now holds for any positive number p, integral or not.] The theorem says that the integral part of the remainder on dividing a real number by a positive integer is the remainder on dividing the integral part of the real number by the positive integer.
To see why this is so, return to (*) and note that, since it follows from (*), by Theorem 119, that
pel,
(#*)
H-
c P
Now, since 0 < ((— )l,p < p. it follows that 0 <
0 <
< p, so that
l< i.
P
Hence, from (**) ["dividing by p"],
'gel
p
< M <
"" P
+ 1 . Conse-
quently,
From this and (**),
We combine these two results into two theorems:
|
Theorem 124. V V 0 < i x m — |
(fi*i\ |
}- |
= E«l - |
>- X m _ j |
m < m |
|
iml |
In a later unit we shall use the second of these two theorems to prove that, for each m > 1, each positive integer has a base-m place value name.
Use the algorithm based on Theorem 123 to find the base-9 name for 75621.
[7-112] [7.06]
MISCELLANEOUS EXERCISES A. 1. Complete and prove the generalizations about the positive integers (a) V n(n t l) + (n + 1) = t±±M 1
{b) V n(n * '><" + 2> + (n + l)(n + 2) = <n+1>< t H 1
<c) Vn n(n+l)(n+3)(nt4) + (ntl)|nH)(nt3) =
2. If, for each n, g = n(n + l)(2n + 1) then, for each n, g (n+l)( )( ).
3. If, for each,.p, f = p(2p - l)(2p + 1) then, for each p, f
( )( K ).
B. 1. The ancient Babylonians used the following incorrect formula for finding the area-measure of a quadrilateral:
K _ (a + c)(b + d)
where K is the area-measure, and a, b, c, and d are the meas- ures of consecutive sides.
(a) If the formula is applied to a parallelogram or a trapezoid, does it give an overestimate or an underestimate of the area -measure?
(b) For which class of quadrilaterals is the formula correct?
2. The number of television sets in a certain city is 48000. If this means that there are 13.9 television sets per 1000 of popu- lation, what is the population of the city ?
3. All but one of the following numerals stand for the same num- ber. Which one does not?
(A) | (B) 1.125 (C) ^ (D) |i (E) ||
[7.06] [7-U3]
4. The vertices of a triangle are A(0, 8), B(0, 4), and C(5, 1). What is the area -measure of AABC?
5. Simplify.
(a) (4&*b^(-3aV) (b) -3p2q7*7p4q6
(c) (20xy2z3)(4x2y3z) (d) -8r2s5t • -8s¥u
6. If 1 child is born every x seconds, how many children are born in a half -hour?
7. By selling an article at 30% above the cost price, a dealer makes a profit of % of the selling price.
8. 45 seconds is what per cent of 2 hours?
9. Simplify.
2 + 5 i+ I
(a) 0.6 * | (b) | + £ - 3L (c) L^ (d) ^JL
8
10. Solve this system of equations.
f x + y + 48
x = 1.474?9
6.3*4*0 = y+3-024
11. If 80 light bulbs cost k dollars, how many can you buy for 75 cents?
12. A team is scheduled to play 30 games during the season. If it loses 20% of the first 15 games, how many of the remaining games must it win to make the season win average at least 90% ?
13. Mr. Sanchez plans to travel 350 miles in 8 hours of driving. If he averages 40 miles per hour during the first 5 hours, what must he average during the remaining 3 hours?
[7-114] [7.06]
14. Solve the equation 4S = j (a + i)' for '*'.
15. Suppose that one amoeba divides into two every 30 seconds. Under these conditions, it takes 24 hours to fill a test tube. If you start with two amoebas, how long would it take to fill the same test tube?
16. Simplify. (a)(r^r-^]xTT^:T ,b) < * 2 >- *2-2
x-4 x-3J ll-2x '' la+1 a+2
4 1 1 1 ' 17, Solve the equation — = — + — for r'.
r p q
18. If a car travels x miles in y hours, what is its rate in feet per second?
19. One method used by the Egyptians to find the area-measure of a circle was to compute the area-measure of a square whose side- measure is 8/9 of the diameter of the circle. Does this method give an overestimate or an underestimate of the area-measure of the circle?
' ab
20. Solve the equation — = d for 4b*.
21. If the sum of two numbers is 10 and the sum of their reciprocals is 5, what is their product?
3
22. Which of the given numbers is not ■=- ?
(A)V? <b) 7f (c) 7f (D) i*? (E) ^
23. Give a geometric argument to show that, for each a > 0 and for each b > 0, Va* + b* < a + b.
24. If a first number is 40% of a second, what per cent of the second is 125% of the first?
[7.06]
[7-115]
DIVISIBILITY
You know that m is a factor of n with respect to I+ [or: m divides n, or: m|n] if and only if there is a positive integer p such that n = mp:
V V [m In <=> 3 n = mp] m n L ' p rj
So, 2 |4 and 6|l2, but 5^9- And, since n= 1 »n = n» 1, it follows that
Theorem 125.
V [1 Jn and n jn]
EXERCISES
A. True -or -false?
1. 5 130 2. l|78 6. 7|21 7. Zl j 168
11. 3|59 12. 3 (63 + 59 15. 2 1 103 • 104
3. 82|80 4. 80|82 5. 8| 17
8. 7 1 168 9. 8|80 + 888 10. 3 |63
13. 7|14'8273591 14. 2|94«95
16. 6|94-95«96 17. 6 1 103 • 104 • 105
B^. Prove each of the following.
Sample. V V [m |n=> m < n]
[Theorem 126a]
Solution. Suppose that m Jn. It follows that there is a q such that mq = n. By Theorem 104, 1 < q and, by Theorem 101, m > 0. Hence, using Theorem 86e, it follows that m = m • 1 < mq = n. So, if m jn then
■ m < n].
m '• n. Consequently, V V fm In
~ ^ J m n L '
1. V V V [(m|nandn|p) m n p L ' ,r
m
|p]
2. V V [(m |n and n |m) => m = n]
[Hint. Use the theorem in the Sample.]
[Theorem 126b] [Theorem 126c]
Exercises 1 and 2 say that I is transitive and antisymmetric
3. V V V [(mlnandmlp) m n p l ' ' r'
m (n + p]
[Theorem 126d]
[7-116]
[7.06]
4. 5. 6.
V V V [(m In and m In + p) m n p
V V V [m|n=> mp|np] m n p l '
m
|p]
[Theorem 126e] [Theorem 126f]
V 2|n(n + 1) [Hint . For part (ii) of an induction proof, note that (p + l)(p + 2) = p(p + 1) + 2(p + 1). Now, use Theorem 126d, above.]
7. Vn 6|n(n + l)(n + 2)
'8. V 6 n(n2 + 5) n '
*9. For each odd n, 24|n(n2 - 1)
THE DIVISIBILITY RELATION
The relation j has much in common with the relation <. :
V In
n ■
V n In
n '
V™ V« ^ Km ln and n Ip) m n p '
m
|p]
V V [( m I n and n | m) =i> m = n]
m n l ' ' J
V V V [mln < — > mplnp] m n p l ' r i rj
V 1 < n n ~
V n < n n ~~
V V V [(m <: n and n <: p) r=^> m <, p]
m n p l ~ ~~ r rj
V V f(m < n and n < m) => m = n]
m n ~"
V V (m < n or n < m)
m n "~ —
V VV [m «: n <=> m + p '■ n + p] mnpL— r — rj
V V V [m < n <=> mp *'■ np] mnpL_ r"_ r-j
The two gaps in the left column indicate two important differences between
j and <. Another difference is that there is no theorem about J which
corresponds with 4V V [m < n < — > m < n + 1]'. r m n L — J
In spite of these differences, the first four theorems about | do show
that, like <, J orders the positive integers in an interesting way. To see
what this means, note that <. orders the positive integers which are less
than or equal to a given one in a very simple way. For example, those
which are less than or equal to 6 are 1, 2, 3, 4, 5, and 6. Since 1 < 2,
2 <_ 3, 3 <_ 4, 4 <_ 5, and 5 < 6, we may, knowing that < is reflexive and
transitive, indicate the < -order of these integers schematically by:
On the other hand, the positive integers which are divisors of 6 are 1, 2, 3, and 6. Since 1 |2, l|3, 2|6, and 3|6, we may, knowing that j is
[7.06]
[7-117]
reflexive and transitive, indicate the (-order of these integers by:
2
1
The diagram tells us that 1 \Z, 1 |3, 2|6, and 3 J6. Knowing that | is transitive, we conclude that 1 J 6, and, knowing that j is reflexive, we conclude that 1 1 1, 2|2, 3J3 and 6 1 6 .
For certain choices of n [for example, for n = 8], j orders the factors^of n in the same simple way [linearly] in which <, orders the positive integers which are less than or equal to n. However, for "most'* choices of n this is not the case. As examples, consider 24, whose factors are 1, 2, 3, 4, 6, 8, 12, and 24:
30, whose divisors are 1, 2, 3, 5, 6, 10, 15, and 30
2 6.
1
0-
^30
15
and 60, whose factors are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, and 60
[7-118] [7.06]
EXERCISES
A. Here are the divisibility-ordering diagrams for the divisors of 8 and for the divisors of 243.
1 2 4 8
1 3 9 27 81 243
Give ten more examples of positive integers whose diagrams are linear.
B. The diagram for 6 is two-dimensional. So are the diagrams for 12 and 24. Draw the diagram for 48; it is two-dimensional, also. Other two-dimensional diagrams are those for 18, 54, 36, 108, and 215.
C. 1. Draw the diagram for 1125. [Hint. 1125 = 32 • 53]
2. Draw the diagram for 500.
3. Give three more examples of positive integers whose diagrams have the same shape as the diagrams in Exercises 1 and 2.
4. Draw the diagrams for 23 • 34 and 24» 54.
5. For each number listed below, tell how many factors it has. (a) 32-53 (b) 22-53 (c) 23 • 34 (d) 24-56 (e) 5b-73 (f) 251-380 (g) 751-1180 (h) 23 • 3 (i) 13-17 (j) 28 (k) 317 (i) 43 (m)43«105 (n) 142»73 (o) l4-25-32 (p) 24-35-52
D. The diagrams for 30 and 60 are three-dimensional. Characterize the positive integers whose diagrams are three-dimensional.
E_. If a positive integer has just two factors, its diagram looks like this:
1 D
[Such numbers are, of course, prime numbers.] If a positive
a
[7.06] [7-119]
integer has just four factors, its diagram looks either
like: 1 p p2 p3 or like : 1 ^ ^pq
q
[What are the smallest such positive integers?]
Give all possible diagrams for a positive integer which has just
1. three factors 2. five factors 3. six factors
4. eight factors 5. twelve factors 6. sixteen factors
HIGHEST COMMON FACTOR
It is one of the important properties of < that, given two positive integers, one is less than the other. So, by transitivity, the positive integers which are less than or equal to both of two positive integers are just those which are less than or equal to the smaller of the two. For example, since 12 < 30 [and since <. is transitive],
V [(p < 12 and p < 30) <=> p < 12].
The situation with regard to the relation j is less simple, and more interesting. Given two positive integers one of which divides the other, the positive integers which divide both are, by the same argument used above, just those which divide the smaller of the two. But, given two positive integers, it is not usually the case that one of them does divide the other. To see what happens, let's again consider 12 and 30. Since 12 1 60 and 30 1 60, all the divisors of 12 and all those of 30 are indicated in the diagram on page 7-117 which shows how j orders the divisors of 60. From this we see that the set of divisors of 12 is {1, 2, 3, 4, 6, 12} and the set of divisors of 30 is {1, 2, 3, 5, 6, 10, 15, 30}. The set of common divisors of 12 and 30 is the intersection of these two sets. So, it is
{1, 2, 3, 6}.
This is just the set of divisors of 6. So,
V [(p|l2 and p|30) <=> p|6].
[7-120] [7.06]
Just as 12 is the greatest integer less than or equal to both 12 and 30, 6 is the "most divisible" integer which divides both 12 and 30. 6 is called the highest common factor [HCF; or: the greatest common divisor, GCD] of 12 and 30.
Find the HCF of 15 and 24, of 25 and 50, of 21 and 27, of 14 and 33, and of 23 • 3s and 27 • 34.
A positive integer d is the HCF of m and n when
V [(p|m and p|n) <=> p|d].
Notice that this means [only if -part] that each common divisor of m and n divides d and [if -part] that d divides both m and n. Using Exercise 2 of Part B on page 7-115, it is easy to show that no two integers have more than one HCF. [Do so now, by showing that if each of d1 and d2 is an HCF of m and n then d1 |d2 and d2 j d. x . ] However, we have yet to show that each two integers do have an HCF. In doing so, we shall dis- cover an important property of highest common factors.
Exercises 3 and 4 of Part B on page 7-115 suggest a procedure to use in searching for the HCF of two positive integers. For they tell us that the divisors of
n + p and n are just the divisors of
n and p.
So, the HCF of n + p and n is the HCF of n and p.
For example, let's find the HCF of 30 and 12. Since 30 = 12 + 18,
HCF(30, 12) = HCF(12, 18).
Since 18=12 + 6, HCF(18, 12) = HCF(12, 6).
Since 6J12, HCF(12, 6) = 6.
So, HCF(30, 12) = 6.
In obtaining the first two of the displayed equations, we subtracted 12 from 30 twice and found that
30 - 12*2 = 6.
This told us that HCF(30, 12) = HCF(12, 6). Since
12-6*2 = 0,
HCF(12, 6) = 6. So, HCF(30, 12) = 6. [Notice that 30- 1 + 12 • -2 = HCF(30, 12).]
[7.06] [7-121]
Let's try this with some larger numbers, say 9672 and 4147. Since 9672 - 4147 X 2 = 1378,
we see that HCF(9672, 4147) = HCF(4147, 1378). Since 4147 - 1378 X 3 = 13,
it follows that HCF(4147, 1378) = HCF(1378, 13). But, 1378 - 13 X 106 = 0.
So, HCF(1378, 13) = 13. Hence, HCF(9672, 4147) = 13.
In finding HCF(30, 12) we discovered that there are integers i and j such that
HCF(30, 12) = 30i + 12j.
[These integers are 1 and -2, respectively.] In other words, HCF(30, 12) is an integral linear combination of 30 and 1 2 .
Is HCF(9672, 4147) an integral linear combination of 9672 and 4147? That is, are there integers i and j such that 13 = 9672i + 4147j? Our investigation of this question will suggest a method of proving that each two positive integers do have an HCF.
We begin by noting that both 9672 and 4147 are integral linear com- binations of 9672 and 4147.
9672 = 9672 X 1 + 4147 X 0 4147 = 9672 X 0 + 4147 X 1
We also note that 1378 is the remainder upon dividing 9672 by 4147, and that 13 is the remainder upon dividing 4147 by 1378. So, we can show that 13 is an integral linear combination of 9672 and 4147 if we can show that the remainder upon dividing one integral linear combination of these two numbers by a second such linear combination is, again, an integral linear combination of the two numbers [Explain.]
Let's show this. Suppose that p and q are integral linear combina- tions of some two integers m and n. That is, suppose that there are integers i, j, k, and l such that p = mi + nj and q = mk + ni . The remainder upon dividing p by q is
p - q£E] = (mi + »j> - (mk + nl)|[£] . m(i - k[| ]) + »(j - ||[£ }). Since ' *- € I and since I is closed with respect to multiplication and sub-
ILCU1
traction, it follows that the remainder is an integral linear combination
[7-122] [7.06]
of m and n.
So, since 1378 is the remainder upon dividing 9672 by 4147, both of which are integral linear combinations of 9672 and 4147, so is 1378. And, since 13 is the remainder upon dividing 4147 by 1378, both of which are integral linear combinations of 9672 and 4147, so is 13.
We have proved that there are integers i and j such that
13 = 9672i + 4147j. [Find two such integers.]
Our examples suggest to us that if two positive integers have a highest common factor then it is an integral linear combination of the two integers. To show that two positive integers m and n do have an HCF, let's consider the set S of all positive integers which are integral linear combinations of m and n.
S = {p: 3^- p = mi + nj}
As we have seen, m e S, n e S, and if p and q belong to S then if the remainder upon dividing p by q is positive, it also belongs to S.
Since S is a nonempty set of positive integers, it has a least member d. Suppose that p is any member of S. Since d e S, the remainder upon dividing p by d is either 0 or belongs to S. This remainder is p - d II ~ II. Since
0<p-d[|]<d,
it follows that the remainder is less than d. Since d is the least member of S, the remainder is 0. That is,
So, d|p. We have shown that d divides each member of S. In particular, d |m and d |n.
On the other hand, since d e S, there are integers i and j such that
d = mi + nj.
So, each common divisor of m and n divides d.
Hence, each two positive integers m and n do have a highest common factor. In fact, HCF(m, n) is the least member d of the set S of those positive integers which are integral linear combinations of m and n.
V V 3. 3. HCF(m, n) = mi + nj [Theorem 127]
m n i j j \. j
[7.06] [7-123]
The algorithm for computing the highest common factor of two positive integers m and n:
m - nq2 = r1 n - riq2= r2
ri " ^3= r3
is nothing more than a convenient way of getting smaller and smaller members of S until you finally find the one which divides each member of this set. This is the last nonzero remainder.
Example 1. Find HCF(3705, 2618).
Solution.
1_
2618) 3705 3705 - 2618*1 = 1087
2618
1087
2
1087)2618 2618 - 1087-2 = 444
2174
444
2
444) 1087 1087 - 444 • 2 = 199
888
199
2
199)144 444-199-2 = 46
398
46
46) 199 199 - 46-4 = 15
184
15
_3
15 ) 46 46 - 15 • 3 = 1 -< HCF
45
1
[7-124]
[7.06]
Example 2. In Example 1 we found that 1 is the highest common factor of 3705 and 2618. So, we know that 1 is an integral linear combination of 3705 and 2618. Find integers i and j such that
3705i + 2618j = 1.
Solution. The required integers can be found by using the
equations obtained in the Solution for Example 1 . One way is to substitute from the first equation into the second ['3705 - 2618* V for '1087'], then from the first and second equation into the third, etc.
Another way, perhaps easier, is the following:
3705 = 3705
2618 = 3705
3705 - 2618- 1 = 1087 = 3705
2618 - 1087- 2 = 444 = 3705
1087 - 444-2 = 199 = 3705
444 . 199-2 = 46 = 3705
199 - 46-4 = 15 = 3705
46 - 15-3 = 1 = 3705
1 + 2618-0
0 + 2618- 1
1 + 2618- -1 -2 + 2618- 3 5 + 2618- -7 -12 + 2618-17 53 + 2618- -75 -171 + 2618-242
t t
^EXERCISES
A. Use the algorithm to find the highest common factor for each pair of positive integers. [This algorithm is sometimes called Euclid's algorithm for finding greatest common divisors.]
1. 7469, 2387 2. 5320, 4389
3. 8749, 11143
4. 4147, 10672
B. Reduce each fraction to lowest terms.
1.
2387 7459
2.
4389 5320
3.
8749 11143
4.
2574 5049
[7.06] [7-125]
C. For each of the following equations, find a pair of integers which satisfy it.
1. 27i + 17j = 1 2. 38i + 43j = 1
3. 270i + 170j = 10 4. 38i - 43j = 1
5. 270i + 170j =11 6. 38i + 43j = 2
^EXPLORATION EXERCISES
A, For each of the following linear equations, tell whether its graph contains a point with integral coordinates. If it does, give the coor- dinates of one such point; if it doesn't, say so.
1. 13x+10y=l 2. 42x + 60y = 6
3. 13x + lOy = 2 4. 42x + 60y = 5
5. 525x + 231y = 42 6. 7469x + 2387y = 0
B. Each of the following linear equations is satisfied by (0, 0). For each equation, find several other pairs of integers which satisfy it.
1. 6x + lOy = 0 2. 3x + 5y = 0
3. 13x+17y = 0 4. 13x - 17y = 0
5. 17x+13y = 0 6. 1322x - 1263y = 0
C^. 1. (a) Is it the case that, for each integer k, (10k, -6k) satisfies the equation 46x + lOy = 0'?
(b) It is the case that, for each ordered pair of integers which satisfies 46x + lOy = 0*, there is an integer k such that the ordered pair is (10k, -6k)?
(c) Repeat (a) and (b) for the equation *3x + 5y = 0' and *(5k, -3k)*..
•^ *"i^
In answering Exercise 1(a) of Part C, you probably saw that the set of all ordered pairs (10k, -6k) is a subset of the set of ordered pairs of
[7-126]
[7.06]
integers which satisfy *6x + lOy = 0'. That is, you probably saw that
{(x, y): 3k (x = 10k and y = -6k)} C {(x, y) € I X I: 6x + lOy = 0}.
But, when you did Exercise 1(b), you should have discovered that
{(x, y): 3k (x = 10k and y = -6k)} /* {(x, y) e I XI: 6x + lOy = 0}.
For example, (5, -3) belongs to the second-named set but not to the first.
2. True-or -false?
[x,y): 3k(x= 12k and y = -15k)} C {(x,y)e IXI: 15x+12y = 0}
>, y): 3k(x= 12k and y= -15k)} = {(x, y) € I X I: 15x+12y = 0}
[x, y): 3k(x = 4k and y= -5k)} = {(x, y) € I X I: 15x + 12y = 0}
Ix, y): 3k(x=-4k and y = 5k)} = {(x,y) 6 I X I: 15x + 12y = 0}
[x,y): 3k(x = 4k and y = 5k)} = {(x, y) € I XI: 15x- 12y = 0}
;x,y): 3k(x = 584k and y= -626k} = {(x, y) e I XI: 626x + 584y=0}
|
(a) |
{( |
|
(b) |
{( |
|
(c) |
{( |
|
<d) |
{( |
|
<e) |
{( |
|
(£) |
{( |
3. Change the left side of the sentence in Exercise 2(f) to make a true sentence.
4. Complete the following statement:
{(x, y): 3k(x= and y = )} = {(x, y) 6 I X I: 1 162x + 938y = 0} [Hint. HCF(1162, 938) = 14]
_D. 1. How many ways can you make change for 75£ using nothing but nickels and dimes?
2. Repeat Exercise 1 for 73£.
3. Repeat Exercise 1 for $3.75, but this time use nothing but quarters and halves .
[7.06] [7-127]
^DIOPHANTINE PROBLEMS
In order to solve the exercises of Part D of the Exploration Exercises you had to find how many ordered pairs (x, y) of nonnegative integers satisfy:
(1) 5x + lOy = 75
(2) 5x + lOy = 73 and :
(3) 25x + 50y = 375
Problems which amount to finding the integral solutions of equations are called 'Diophantine problems' after the Greek mathematician, Diophantus [circa 250 A.D.].
Equation (1) is equivalent to 'x = 15 - 2y' and it is obvious, by sub- stitution, that the nonnegative integral solutions are (15, 0), (13, 1), (11, 2), (9, 3), (7, 4), (5, 5), (3, 6), and (1, 7). So, there are eight ways to make change for 75 £ using nothing but nickels and dimes.
In Exercise 2 of Part D, you probably answered, without having to do much thinking, that you can't make change for 73£ using nothing but nickels and dimes. Looking at equation (2) you see that, for all ordered pairs (x, y) of integers, 5J5x + lOy. Since 5/[73, there are no integers x and y such that 5x + lOy = 73.
Equation (3) is equivalent to equation (1)- -making change for 75£ using nickels and dimes is essentially the same problem as making change for $3.75 using quarters and halves.
Here is a fourth exercise like those of Part D:
A bit is a coin worth 12y£. In how many ways can you make change for 75£ using only nickels and bits?
This problem amounts to finding the number of nonnegative integral solutions of:
5x + 12~y = 75
This equation is equivalent to:
(4) 2x + 5y = 30
As we shall see, we can find all the integral solutions of equation (4). Then, we can solve the nickel-and-bit problem by counting the
[7-128] [7.06]
number of nonnegative integral solutions. The first step is to notice that (3, -1) is a solution of the equation:
2x + 5y = 1
So, (3 • 30, -1 • 30) is a solution of (4). Since 2 • 90 + 5 • -30 = 30, it follows that if 2x + 5y = 30 then
2x + 5y = 2*90 + 5* -30. So,
(5) 2(x - 90) + 5(y + 30) = 0.
Now, if x and y are integers, then so are x - 90 and y + 30. Your work in Part C of the Exploration Exercises suggests that, since HCF(2, 5) = 1, the integral solutions of (5) are just the solutions of:
3k (x - 90 = 5k and y + 30 = -2k)
In order that x > 0 and y > 0 we must have 90 + 5k > 0 and -30 - 2k > 0 --that is, k must be an integer such that
-18 < k < -15.
So, there are four ways to change 75£ using nothing but nickels and bits .
'•x *"|H *v
The key points in finding the integral solution of (4) were, first, finding some solution of:
2i + 5j = 1
and, second, finding all solutions of:
2i + 5j = 0
We have already proved that, because H(2, 5) = 1, the first equation does have solutions. And the Euclidean algorithm gives us a way of finding one. [It is often, as in this case, easier to guess solutions for such equations than it is to use the algorithm --but, one always has the algorithm to fall back on. ]
We now need to check that, again because H(2, 5) = 1, the second equation is equivalent to the sentence:
3, (i = 5k and j = -2k)
[7.06]
[7-129]
This is a consequence of
Theorem 129.
V V rHCF(m, n) = 1 m n L
V. V. [mi + nj = 0 <=> 3k(i = nk and j = -mk)]]
In order to prove Theorem 129, it is helpful to prove, first:
|
Theorem 128, |
|
|
V V V [(HCF(m, n) = 1 and m Ink) = m n k L ' |
> m|k] |
To say of two positive integers m and n that H(m, n) = 1 amounts to saying that m and n have no common factor other than 1. Two such integers are commonly said to be relatively prime. Theorem 128 says that if a positive integer divides a product and is relatively prime to one factor then it divides the other factor.
Notice that, in view of the application we wish to make of Theorem 129, we have extended the meaning of ' | ' so that, for example, 43j— 6* is to make sense. In fact, we shall define 4 |' so that it is true that 3|-6:
=> 3k J = mk]
V V. [m 1 j m j L ,J
Now, let's prove Theorem 128.
Suppose that HCF(m, n) = 1 and that m |nk. It follows that there are integers i and j such that
(*) mi + nj = 1
and an integer kQ such that
(**) nk = mk0.
From (*) it follows that mki + nkj = k.
From this and (**), mki + mkQj = k. So,
k = m(ki + k0j).
Hence [since I is closed with respect to multiplication and addition],
m k.
[7-130] [7.06]
We can now prove Theorem 129:
V V [HCF(m. n) = 1=>
m n <-
V. V. [mi + nj = 0 <=> 3k (i = nk and j = mk)]]
To begin with, we notice that, whether HCF(m, n) = 1 or not,
m(nk) + n(-mk) = mnk - mnk = 0.
So, for any integers i and j,
3, (i = nk and j = -mk)1^ mi + nj = 0.
Now, suppose that HCF(m, n) = 1 . Suppose that mi + nj = 0. Then, mi = n • -j and, since m Jmi, it follows that m jn ° -j. Since HCF(m, n) = 1, it follows, by Theorem 128, that mj-j. So, by definition, there is an integer k such that -j = mk. Since j = -mk and mi + nj = 0, mi - mnk = 0. Hence, since m ^ 0, i = nk. Consequently [assuming that HCF(m, n) = 1],
mi + nj = 0 ^=> 3, (i = nk and j = -mk).
Combining the two results displayed above, and generalizing, we have:
V. V. [mi + nj = 0 <=> 3 (i = nk and j = -mk)]
1 J ^
So, recalling the assumption that HCF(m, n) = 1 , we see that we have proved Theorem 129.
J, +.K .A. T» .y. ..,>
We have seen how the Euclidean algorithm and Theorem 129 can be used to find all integral solutions (x, y) of linear equations of the form:
mx + ny = p
Such an equation has an infinite number of integral solutions if HCF(m, n) |p, and no integral solutions if HCF(m, n)/j/p. [Finding integral solutions of such equations is sometimes called solving linear Diophantine equations . ]
Example. Solve: 35i - 42j = 14
Solution. The given equation is equivalent to: (1) 5i + 6--j = 2,
[7.06] [7-131]
and HCF(5, 6) = 1 . First, we find a solution of:
(2) 5i + 6--j = 1
Using this solution, we can immediately find a particular solution of (1). Then, Theorem 129 gives us all solutions of:
(3) 5i + 6- -j = 0
By combining these with the particular solution of (1), we get all solutions of (1).
By inspection [or the Euclidean algorithm],
(2') 5- -1 + 6- 1 = 1.
So,
(1') 5- -2 + 6-2 = 2.
Thus, (-2, -2) is a particular solution of (1). By Theorem 129, (3) is equivalent to:
(3') 3k (i = 6k and j = -5k)
Consequently, the solutions of (1) are
(-2 + 6k, -2 - 5k), for k € I.
^EXERCISES A. Find all solutions of each of the following equations.
1. 65i + 77j = 200 2. 50i - 63j = 75 3. 33i + 1 9 j = 250
B_. For each of the following equations tell how many of its solutions are pairs of positive integers.
1. 78x - 117y = 97 2. 51x + 85y = 1037
C^. Find the least integer p for which *5x + 7y = p* has just nine nonnegative integral solutions.
JD. Solve the following problems.
1. Mr. Schwartz hands a storekeeper a dollar bill and 4 pennies
when paying for a 49-cent article. The storekeeper has 7 nickels
[7-132] [7.06]
and 6 dimes. In how many ways can the change be arranged?
2. When Mr. Perez cashed a check at the bank, the teller mistook the number of dollars for the number of cents, and vice versa. Without noticing the error, Mr. Perez pocketed the money and left the bank. He purchased an article for $3.50 and then noticed that he had twice as much money left as the check had called for. For what amount had the check been written?
3. A stick is divided into sections, all of the same length, by drawing 36 red lines across it. It is also divided uniformly by 28 green lines. Counting from a given end of the stick, which red line comes the least distance after one of the green lines? Which red line comes the least distance before one of the green lines?
4. A manufacturer uses three kinds of components --googels, goggels, and gaggels--in assembling a biggel. For each kind of component, the unit cost is a whole number of cents. Four googels and five goggels, together, cost 25£ more than three gaggels. Two googels, four goggels, and three gaggels cost 38£. Each biggel contains seven googels, eleven goggels, and six gaggels. What is the total cost of the components of a biggel?
5. Three robbers stole a sack of spade guineas. As they were about to divide their loot, l/2 to the first man, l/3 to the second, and 1/6 to the third, they were surprised by the King's foresters. The robbers were able to escape with all the money, each man carrying a portion of it. Meeting again in a safer place, each robber turned over a part of what he had carried away; the first man kept half of what he had, the second, two-thirds, and the third, five-sixths. This money was then shared equally among all three. As it turned out, each robber got, in all, the same amount as he would have, if the foresters had not interfered. What is the smallest number of coins which the sack could have contained?
[7-133]
REVIEW EXERCISES
1. Consider the number system consisting of the set S of three numbers 0, 1, and 2, and the two operations ft and <I> which are defined in the following tables :
|
a |
0 |
1 |
2 |
|
0 |
0 |
1 |
2 |
|
l |
1 |
2 |
0 |
|
2 |
2 1 |
0 |
1 |
|
4> |
0 |
1 |
2 |
|
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
2 |
|
2 |
0 |
2 |
1 |
In the following questions, 'x\ 'y', and 'z' are variables whose domain is S.
(a) True-or-false? (1
(3
(4
(5
(6
(7
(8
(10
(12
(13
(14
V V x ■& y = y ft x x y 7 7
(2) VV x<ty=y4>x
x y 7 7
VVV x ft (y ft z) = (x ft v) ft z
x y z 7 7
VVV x «$• (y <t> z) = (x 4> y) <!> z
x y z 7 ' y 3 '
VVV (x ft y) 4> z = (x <fr z) ft (y <d> z)
V V V x <J> (y & z) = (x <t> y) ft (x <J> z)
X y Z
V V V (x <fc y) ft z = (x ft z) <t> (y ft z)
X y Z
3 V v ft x = V
x y 7 7
V V 3 x ft z = v x y z 7
V/nV3 x 4> z = y x/ 0 y z 7
VVV [x ft y = x ft z x y z '
VVV [x4>y = x<tz x y z L 7
(9) 3 V y 4> x = y
x y 7 7
(11) VV 3 x 4> z = y x y z 7
y = z] y = z]
(b) Notice that V V x ft y = the remainder on dividing x + y by 3.
X V
Complete: V V x <$> v -
r x y 7
[7-134]
2. Suppose that S = {0, 1, 2, 3, 4, 5} and that, for each xe S and each ye S,
x ft y = the remainder on dividing x + y by 6, and x & y = the remainder on dividing xy by 6.
(a) Complete the following tables
|
ft |
0 |
1 |
2 |
3 |
4 |
5 |
|
0 |
||||||
|
1 |
||||||
|
2 |
||||||
|
3 |
||||||
|
4 |
||||||
|
5 |
. , . |
. , . |
|
* |
0 |
1 |
2 |
3 |
4 |
5 |
|
0 |
||||||
|
1 |
||||||
|
2 |
||||||
|
3 |
||||||
|
4 |
||||||
|
5 |
(b) (1) Is ft commutative?
(2) Is <i> commutative?
(3) Is the same number in S listed twice in any row of the table for ft?
(4) Your answer for part (3) tells you of a principle for ft. What principle?
(5) Is each number in S listed in each row of the table for ft?
(6) Your answer for part (5) tells you of a theorem about ft, State
the theorem:
V V 3 x y z
(7) Find all solutions of each of the following equations.
(i) 5 <t> x = 3 (ii) 2 * x = 0 (iii) 2 4> x = 3
(8) Is there a cancellation principle for 4> ?
[7-135]
3. Simplify.
(a) (7x3 - 3x2 + 2x - 5) + (2x3 + 7X2 - 5x + 1)
(b) (8x4 + 2x2 - x + 3) + (9x4 + 3x3 - 2x + 7)
(c) (8y - 2y3 + 4y4 - 1) + (7 - 2y* + Qy* - 7y4)
(d) (9a3 - 3a2 + 2a - 5) - (7a3 + 5a2 - 6a + 7)
(e) (5x4 - 3x3 - 2) + (7x3 - 3x2 + 1) - (8X2 - 2x3 + 7)
(£) (3x2 - 2x + l)(5x2 + 3x - 2) - (3x - 2 + 5x2)(3x2 - 2x + 1)
4. Expand and simplify.
(a) (7x2 - 2x + l)(5x - 3) (b) (8x4 - x2 + 3)(2x3 - 3x + 1)
(c) (2y6 + 7y3 + 3y)(4y3 + 2^ + 7) (d) (5a4 + 3a + 4)(7a3 + 2a2 + 2)
(e) (5x3 + 3x + 2)( 10x2 +4) (f) (4x4 + 3X2 + x - 4)(5x3 + 8x + 2)
Simplify by using the division -with -remainder algorithm. lOx5 - 15x4+ 4x3 - 12x2 + 23x- 21
(g)
2x - 3
... 4x4 + 2X3 -8X2 + 2 (h) 2TT1
5.
If the volume-measure of a circular cone 2x . 3 is (16x3 - 28x2 - 24x + 45)tt and the radius of the base is 2x - 3, what is the measure of the height?
6. Show that 4x - 2' is a factor of *3x3 - 2X2 + 7x - 30' without using the division-with-remainder algorithm.
7. One factor of l6x4 + 15x3 - 8x2 - 6x + 35' is *2x + 5'. What is another?
8. The equation 46x4 - x3 - 82x2 + 81x + 36' has four roots. Two of them are 3 and -4. What are the other two?
9. Use definitions such as '4 = 3 + 1' and algebra theorems to prove each of the following.
(a) 3 + 2 = 5
(b) 5 - 2 € P
[7-136]
10. Prove these generalizations.
(a) V q(q + 4)(q + 5) + + 2) + 5) . (q + l)(q + 5)(q + 6)
(b) v (q - l>q(q + l)(q + 2) + q(q + 1)(q + 2) = q(q+lHq+2)(q+3)
, v q(q - l)(2q + 5) + {q + 1}2 . x = (q + DqUq + 7) q 6 o
(d) V q(q + l) + ya) q 2(2q + 1)
(q + IV
_ (q + l)(q + 2)
q 2(2q + 1) ' ( 2q + l)(2q + 3) 2(2q + 3)
(e) V q(6q2+15q+ll) + (3q + 4)2 = (q + D[6(q -H)2 + 15(q+l) + 11]
11. For each of the listed sets, tell whether or not it is closed with respect to each of the given operations.
(a) the set of positive integers
(b) the set of negative integers
(c) the set of nonzero rational numbers
(d) the set of nonnegative numbers
(e) the set of irrational numbers
(f) the set of nonzero integers
(g) the set of real numbers
+ X - -r
12. (a) Suppose the domain of 'x' and 4y' is the set of all people and '>' means the same thing as 'is older than'.
(1) Which of Theorems 86a, 86b, and and 86c still hold?
(2) Does Theorem 87 still hold?
(b) Suppose the domain of 'x' and 4y' is the set of all people and *>' means the same thing as 4is the father of.
(1) Which of Theorems 86a, 86b, and 86c still hold?
(2) Does Theorem 87 still hold?
[7-137]
13. Prove each of the following theorems.
(a) V V V V [(u - v)(x - y) < 0 <=> (v - u)(x - y) > 0] x y u v L '
<b> Vx>0Vy>0
1
1
=> - > X
y
14. True-or-false?
(a) V V not both u > v and v > u u v
(b) VxVy[x - 3 > y=> x - y > 0]
(c) V V V [(x > y and x < z) => z > y]
x y z L 7
(d) V 2x > x
x ~~
(e) y
x^O
Jl < I
x2 - x
"]
(f) V < , V . .
x< -2 y > 1
(g) Vu (u + 2)2 > u2
4-x2 > 4-x2 x xy
(h) V V u2 + v2 > uv
x ' U V ""
(i) Vu>0Vv>0 0) VuVvCu2> V
< => u " v > u " vl
VV VU J
U > V > -u J
2 <*-
15. Prove:
(a) V 1 - I + . *
n n (n + \)c
< 1 -
1
n+ 1
(b) V ~ - -r < -4t ' n n n* n + 1
(c) y
n
n n2+ 1
(d) y
1
1
<
1
n n+ 1 (n+ l)2 n+2
16. Suppose that quadrilateral ABCD is a nonsquare rectangle, and that quadrilateral BDEF is a square. Show that the area-measure of the rectangle is less than the area-measure of the square.
17. Prove that if a, b, c, and d are nonnegative and c + d < a < b then ad + be < ab.
[7-138]
18. Prove that the equation 'x2 + 1 = 0' is not satisfied by any real
number.
19. Prove: V V x4 + y4 > 2xV
x y 3 ~~ '
20. Arrange in order from largest to smallest.
1 l n "6 9 7 14 9 2 1
5' -5' ' 29' 25* 30' 50' 17' -7' 2
21. Solve each of the following inequations.
(a) 3x - 2 > 9 - 5x (b) 5(x - 2) < 3(4 - x)
(c) x2 + 7x > 44 (d) ^j < 2
22. In a basket of oranges and grapefruit, the number of grapefruit is 2 greater than the number of oranges. If the number of oranges were doubled, there would still be less than a dozen pieces of fruit in the basket, but if the number of grapefruit were doubled, there would be more than a dozen. How many oranges and grapefruit are there in the basket?
23. In each of the following exercises you are given a set S and a map- ping f. In each case consider the generalization:
Ve[eeS=^ f (e) € S],
and answer 'true' or 'false'.
(a) S is the set of even numbers; f : n -* n + 12
(b) S = {x: 3 x = 2n - 1}; f : n — n + 12
(c) S = {m: 3 m = 3n}; f : n — n + 20
n *
(d) S = {m: Vn m £ 3n}; f : n -* n + 20
(e) S = {i: 3 i = 3j}; £:i — i + 6
(f) S = {i: V if 3j}; f : i -* i - 6
(g) S = {x: x > 5}; f : x — x + 1
[7-139]
(h) S = {x: x is a prime number}; f : x -*- x + 2
1 + x
(i) S = 1, 3; f :x- i~-^
(j) S= {1}; f:x-I±*.
(k) S = {x: x < 0}; f : x — -i-j-*-
(i) S = {x: 3p 3q^Q qx = p}; f : x - i-±-*-
(m) S = {x: V / Q qx 4 I}; f : x — 2 *
(n) S = {(x, y) : x > 0 and y > 0}; f : (x, y) - (x, y + 2)
[Now, repeat part (n) for Quadrant II, Quadrant III, and Quadrant IV.]
(o) S = {(x, y) : x = 7}; f : (x, y) - (x, y + 2)
(p) S = {(x, y) : x < y and 3. y = 2i}; f : (x, y) - (x, y + 2)
(q) S = {(x, y): y > x2}; f : (x, y) - (2x, 4y)
(r) S = Quadrant I; f : (x, y) — (x - 2, y - 3)
[Repeat part (r) for each of the other three quadrants.]
(s) S= {(x, y): 2y-3x = 7}; f : (x, y) - (x - 2, y - 3)
(t) S = {(x, y): 2y-3x= 7} w {(x, y) : 3x - 2y = 9}; f : (x, y) - (x - 2, y - 3)
(u) S = {(x, y) : 4x - 5y = 7 or 4x - 5y = 14}; f : (x, y) — (x - 2, y - 3)
(v) S = {(x, y) : 4x - 5y = 7} r\ {<x, y) : 4x - 5y = 14}; f : (x, y) - (x - 2, y - 3)
(w) S = {(x, y) : 3p 4x - 5y = 7p}; f : (x, y) - (x - 2, y - 3)
(x) S = {(x, y): y > |x|}; f : (x, y) - (-x, 2y)
(y) S = {(x, y): x2 + y2 = l}; f : (x, y) - (^L+JL, *jJL\
(z) S = {(x, y): xy = 0 or y2 = x2}; f : (x, y) - (££4=I> ^j^)
[7-140]
24. Here are the first four numbers in the sequence C,
• » •
13
(a) Study the formation pattern and try to describe it in a recursive definition of C.
(b) Guess an explicit definition of C, and derive it by mathematical induction from the recursive definition.
25. Here are the first four numbers in the sequence D.
• •• •
• • •
• • •
• •♦• ••••••••
••••••••••
••••••
• • •
i
8
21
40
(a) D = 1 and, for each n, D = S , + 4T , where S and T are % ' l n+in+i n
the sequences of square numbers and triangular numbers, re- spectively. Use the recursive definitions of S and T to find the recursive definition of D:
Di = 1
V D = D +
n n + i n
(b) Derive an explicit definition of D.
26. Let f be a function which is defined recursively by:
V f . = f + 3
n n+ l n
[7-141]
(a) Compute f3, f6, and f12 - f10.
(b) Discover an explicit definition of f and derive it from the recur sive definition.
27. (a) Given n points on a circle, how many chords have these points
as end points ?
(b) Given 7 points on a circle, such that no three of the chords which have these as end points are concurrent inside the circle, how many intersections do the chords have inside the circle?
(c) Repeat part (b) with 'n' in place of 47'.
28. (a) In how many ways can you put seven silver dollars in three
pockets ?
(b) Solve part (a) under the additional condition that no pocket be empty.
135 29. Show that, for each n, n > -«- if and only if n > 5
30. Give an example of a set of real numbers which has
(a) a lower bound but no upper bound;
(b) a lower bound but no least member.
1 - n
31. Does {x: 3 x = — j—} have a least member? A greatest member? 1 n n* ' &
A least upper bound?
32. Suppose that f and g are defined by:
f x = 4 f Bl = 2
and: /
VfL=2f+3 V g L = 3g
nn+i n 1^ n fen + l &n
Prove each of the following theorems by mathematical induction
[or Theorem 114].
(a) V g > 2 (b) V w g - f > 1
n°n— * ' n > 4 &n n
[7-142]
33. Compute.
(a) 13.11 + 12.9] (c) [9. 28]] + 49.28}}
(b) J -3. 5 J - J 2*1 (d) H»]H + €1*11
34. What ordered pairs belong to {(x, y) : 4y - 3x = 0} r\ {(x, y) : y = [xj}?
35. Solve:
(a) [4.8] + 11*1 < 7.6
(b) J2.891 + Ixl < [2.89 + xl
36. Prove:
(a) Vx[xl < x+ 4- (b) V
X+ 2
X+ 2
< |[xl + 1
37. Solve: n|n2 + 1
38. For each number listed, tell how many factors it has.
(a) 23'34 (b) 1000 (c) 32 • 52 • 72
39. Find ail the integer solutions of *31x - 25y = 6'.
40. What is the highest common factor of 298 and 746?
41. A farmer's livestock consists of just cows and chickens. The total number of heads and legs is 699. If he has more than 200 chickens and more than 15 cows, how many of each animal does he have?
42. If a 10-ounce can of car wax costs 60 cents and a 26 -ounce can costs $1.43, how much do you save per ounce by buying the larger size?
43. Simplify.
(b) i-x
2y+ 1 3
[7-143]
2 7
44. Solve the equation: >2x. \)Z " (2x - 1) + ^ = °
s + 1 r
45. If r and s are positive integers, which is larger, — - — or , ?
s r t i
46. Suppose that AABC is right-angled at C. If the measures of the medians from A and B are 13 and 2V 34 , respectively, what is the perimeter and what is the measure of the third median?
<->
47. A yS^" "^Xt* Given: PT is a tangent,
PA = 12, PT = 6
Find: PB
48. A handtruck can hold either 10 boxes of plums or 15 boxes of cherries If a stock clerk wants to load it with as many boxes of plums as cher- ries, what is the largest number of boxes of each kind he can load?
49. Solve these equations:
(a) 24=0.25%(x) (b) ~%(l600)=x
o
50. Simplify, (a) £*Ll
i-i.i
y/Tl + V48 /u\"V/l 1 , \ 9 5
— — (b) V25 " TTq (c) 5
/8 + vT2 Lb lb9 1+4
18
51. The width of a rectangle is 75% of the length. If the dimensions are increased in such a way that the new rectangle is similar to the old one, but its perimeter is increased by 21 and its area-measure is increased by 63, find the dimensions of the original rectangle.
52. Solve these equations:
[7-144]
53. The hypotenuse of a right triangle is 1 foot longer than one of the legs and its perimeter is 6. What is its area?
54. Simplify.
, . 3 5 7
(a) 4 " II + 20
{b) T + —
3m
To"
(c)
1.2 X 0. 1 62
55. There are n players in an elimination -type checkers tournament. How many individual matches must be played to determine the winner?
56. r- ^-srT-^ The latitude of Chicago is approxi- mately 42° , and the radius of the earth is about 3960 miles. How far is Chicago from the earth's axis?
57. Pete walks from A to B at the rate of 4 miles per hour and rides from B to A at the rate of 7 miles per hour. If the round trip took Sj hours, what is the distance between A and B?
58. Find four consecutive integers such that the product of the two smallest differs from the product of the two largest by the sum of the four.
59. Solve the system
60. What is the area of an isosceles triangle whose base is 10 inches long and whose congruent sides are each 13 inches long?
61. A man inherits 1/3 of his father's estate, and his sister inherits
l/5 of it. The balance of $14000 was left to a charitable institution, How many dollars did the man inherit?
[7-145]
BASIC PRINCIPLES AND THEOREMS
Commutative principles for addition and multiplication
VVx + y = y + x VVxy=yx
x y 7 7 x y 7 7
Associative principles for addition and multiplication
VVVx+y+z = x+(y+z) VVV xyz = x(yz)
xyz 7 ' xyz7 7 '
Distributive principle [for multiplication over addition]
VVV (x + y)z = xz + yz xyz 7' 7
Principles for 0 and 1
|
V x x |
+ 0 = |
X |
V X |
Xl = |
= X |
1/0 |
||||
|
Principle |
of |
Opposites |
Principle for |
Subtraction |
||||||
|
V x X |
+ - |
x = 0 |
V V x - x y |
y = x + |
-y |
|||||
|
P: |
rinciple |
of Quotients |
||||||||
|
V V x y |
/o |
X 7y |
= X |
|||||||
|
* |
1- VxVy Vz x(y + z) = xy + xz [page 2-60]
2. Vx lx = x [2-61]
3- vv Y. V. V. ax + bx + ex = (a + b + c)x [2-61] x a d c
4' VxVy VaVb <ax><by> = <ab)<xY) [2-61]
5- VxVy Va Vb <a + x> + (t> + y) = (a + b) + (x + y) [2-61]
6' VxVyVz fx = y==> x + z = y + zl [2-64]
7' VxVyV2 tx+ z = y + z=> x = y] [2-65]
8* VxVyVz [x = y=:> z + *= z + y] [2-66]
[7-146]
9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30.
VVV fz + x = z + y^^ x = yl x y z L 7 ' J
V V [x = y =5> -x = -y]
x y L 7 /J
VVV fx = y =^> xz = yzl
x y z L 7 7 J
VVV fx = y =£» zx = zyl
x y z L 7 7J
V V V V [(u = v and x = y) => u + x u v x y L 7
V V V V f(u = v and u + x = v + y) — u v x y L J
V xO = 0 x
V V [x + y = 0 => -x = y]
x y L } J J
V X = X
X
V V -(x + y) = —x + -y
x y 7 7
V V -(x + -y) = y + -x
x y 7 7
V V -(xy) = x • — y x y ' ]
VxVy -(xy) = -xy
V V [x = — y => -x = yl
x y L J 7J
V V —x * — y = xy
x y ' J
V V — xy = x • — y
x y 7 '
VxVyVz -x(y + z) = -(xy) + -(xz)
VVV -x(-y + -z) = xy + xz x y z 7 ' 7
[page
v + y] x = y]
V x x
1 = -X
V -x = -lx
X
V V (x + y) + -y = x x y 7 7
VV (x + y)-y = x x y ' 7
|
2-66] |
|
[2-66] |
|
[2-66] |
|
[2-66] |
|
[2-66] |
|
[2-66] |
|
[2-66] |
|
[2-68] |
|
[2-69] |
|
[2-69] |
|
[2-69] |
|
[2-69] |
|
[2-69] |
|
[2-69] |
|
[2-70] |
|
[2-70] |
|
[2-70] |
|
[2-70] |
|
[2-70] |
|
[2-70] |
|
[2-71] |
|
[2-71] |
31. 32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
VVV x - yz = x + -yz x y z ' ]
V V x - y + y = x x y J J
V V -(x - y) = y - x x y " 7
VVV x+(y-z)=x + y-z x y z w # y
VVV x-(y+z)=x-v-z x y z ' 7
VVV x-(y-z)=x-y+z x y z w / 7
V V V x+(y-z)=x-z + y x y z 7 ' '
VV Vz x(y - z) = xy - xz Vx Vy Vz (x - y)z = xz - yz VxVy Vz x - (-y - z) = x + y + z
Vx Vy Vz Vu X " (y " Z " U) = x " V + z + u
V 0 - x = -x x
V x - 0 = x
X
VxVyVzX+ z " ^ + z) = x " y VxVy Vz X " Z " (y ' z) = x " V Va Vb Vc Vd (a " b) + (c " d) = (a + c> " <b + d)
VxVyVz'Z+y = X=^ z = x - y]
vxvyvz/o [xz = yz=> x = y]
V V ,rt V [zy = x=*> z = X 1
x y/0 z L y y J
w x
V — = x
x 1
Vo l = 1
VX
X - 1
[7-147]
[page 2-71] [2-72] [2-72] [2-73] [2-73] [2-73] [2-73] [2-74] [2-74] [2-74] [2-74] [2-75] [2-75] [2-75] [2-75] [2-75] [2-89] [2-90] [2-91] [2-91] [2-91] [2-91]
[7-148]
53. V ,n - = 0
54. 55. 56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
V V /n [- = 0=> x= 0] x y/0 Ly J
V V [(x /0andy/0)^>xy/0] x y
V V [xy = 0 => (x = 0 or y = 0)] x y
ww ww xiu xv + uy
x y/=0 u vfO y v yv
ww ww x u xv - uy
x y/*0 u v p 0 y v yv
x y^O u v^O y v
V V ,„ V V
yv
V V / V , — = —
xy/0 z/cOyz y
x y^O z^O y : yT"z
V V V ,n *£ = ly
x y Z/eO z z '
* w x 1
x y/*0 y y
x y/*0 y
V ,nV V xX±2£E = y+z
x/ 0 y z x '
V V , V V j V , ^ = (* * 2?u x y/*0 u v^O z/*0 yv (y -f z)v
v v v ,n £ + £ = ^±x
xyz/Oz z z
V V
V V
u
' V / V / V V / +
x y/0 z^O u vpQ yz vz
V V V ,n i - X= iUlX x y z/tO z z z
xv + uy yvz
70- VxVo V<)VUVW0 ^
71. V V V ,_ x+ i= *£±X x y z^O z z
u vz
xv - uv yvz
|
[page 2-91] |
|
[2-91] |
|
[2-91] |
|
[2-91] |
|
[2-92] |
|
[2-92] |
|
[2-93] |
|
[2-94] |
|
U-95] |
|
[2-96] |
|
[2-97] |
|
[2-97] |
|
[2-97] |
|
[2-98] |
|
[2-99] |
|
[2-99] |
|
[2-100] |
|
[2-100] |
|
[2-100] |
72. V V /n V /n x-r *- = x-
x y ^ 0 z ^ 0
73 V V / V / V / — fJ< x y^O u^O v^O y
74. V,^V,--!-=2- x ;= 0 y/=Ox/y x
75. V V ,n V ,. *- -r z
x y/= 0 Z/= 0 y
u
v
XV
yu
x
yz
76. V V /n x y/O
77. V V yn x y/*0
78. V V ,n x y/O
x
y
X
y
■X
•y
-X
y
X
^y
X
y
79. Vx[x^O=> -x/*0]
80. -0=0
Ox Ox Ox
'iN "j" "i"
(Px ) V^ [x ^ 0 => either x € P or -x € P] (P2 ) V^ not both x c P and -x e P (P^ ) V^ V„ [(x € P and y e P) => x + y e P]
> xy € P]
s' x-yi -y
(P4) VxVy [(xe P andyeP)
Ox Ox Ox T» "4X '4V
81. Of/P
82. 1 e P
fVxeP [i > o]
x^O]
[7-149]
[page 2-101]
[2-101]
[2-101]
[2-101]
[2-103]
[2-103]
[2-103]
[7-18]
[7-18]
[7-22] [7-22] [7-23] [7-24]
[7-23] [7-23]
Ox Ox Ox
*-,x *.,«. „,*
(G) V V [y > x x y LJ
y - x e P]
Jx Ox Ox
',* -v> „,.»
[7-30]
83. V [x > 0
==» x
€P]
84. V V [y > x <=> y - x > 0]
[7-30] [7-31]
[7-150]
85. V [x < 0 <=> -x > 0]
[page 7-32]
86 a. V V [x/y^>(x>yory>x)]
— x y c
b. V V not both x > y and y > x
— x y
c. V V V f(x > y and y > z)=> x > z]
— x y z L
d. VVV [x>y=>x+z>y+z]
— x y z L '
e. VVV [(z > 0 and x > y) =*> xz > yz]
— x y z
>
[7-32]
87. V x/x x
[VxVy(x = y=> x^ y)]
88. V V [y >. x <=> x^ y]
x y L/ —
89. VVV [x + z > y + z <=> x > y]
x y z L
90. V x + 1 > x x
[7-33] [7-33] [7-33] [7-35]
91. V V V V [(x > y and u>v)=>x + u>y + v]
x y u v
92. VVV f(x > y and y > z) => x > z]
x y z " """
93. V V [(x > y and y > x) => x = y]
x y — ' —
94. V V [-x > -y <=> y > x]
x y L
[7-35] [7-35] [7-35] [7-35]
95. a. VxVy Vz> Q [xz > yz <=> x > y] ^' VxVy Vz < 0 fXZ * yZ <=^> x > yl
[7-36]
96 a. V V [xy > 0 — x y L 7
( [x > 0 and y > 0] or [x < 0 and y < 0] ) ]
b. V V [xy < 0 <=> ( [x > 0 and y < 0] or [x < 0 and y > 0] ) ] — x y L '
[7-36]
97 a. V
x2 > 0
±' vx/0
b. VxVy [x/*y=S> x2 + y2> 2xy]
c, V^_x+i>2 — x> 0 x —
[7-38] [7-39] [7-40]
[7-151]
,2 _ ,,2
x = y]
98 *• Vx>0Vy>otX -*
b- V V . n [y2 > x2 => y > x > -y]
— x y > 0
c- V ^ n V [y > x=> y2 > x2]
— x> 0 y 7 7 J
*\
\ [page 7-38]
->
99 a. V V V ,n [- > £ — x y z/£ 0 L z z
^ xz > yz]
£" Vx^0 ([i > 0 <=> x > 0] and [~ < 0 <=> x <0])
[7-41]
100.
Vx>0Vy/0 Vz>0[y> Z^ I> ?J
j- vu o„
'IN «V 'lx
[7-41]
(V)
<V>
[domain of 'm', 4n', *p*, and 4q' is I+]
1 €l+
Vn n + 1 e I+
Vg [( 1 € S and Vr [n € S => n + 1 e S] ) => Vn n € S]
[7-49]
Oy „^ xU
*-j>. ^,X *•,>.
101. I+C P
102. V V m + n € I* m n
103. V V mneT m n
104. V n > 1 n —
105. V V [n > m => n - mc I+] m n L J
[Vn n € P]
106. V V [n > m + 1 m n l —
n > m]
[7-49] [7-56] [7-56] [7-84] [7-84] [7-86]
107 a. V n f- 1
— n
b. V V [n < m + 1 <=> n < m]
— ■ m n L — J
[7-86]
[7-152]
108.
Each nonempty set of positive integers has a least member.
[V [0 / S C I*=> 3m s Vn e s m < n] J [page 7-88]
O, 0' -J,
"ix ^r "ix
(C) V 3 n > x
x n
(I) Vx[xel
(x e I+ or x = 0 or -x € I+) ]
s.1, s,«, si,
•V 'J% 'lx
109. V [xe I <=> 3_ 3 x
x m n
= m - n ]
[domain of V, *j\ and 'k' is I]
110 a. V. -j e I
b. V. Vkk + jel
c . y. vk k - j € i
d. V.VkkjCI
[7-89] [7-94]
[7-94]
*\
> [7-95]
J
111. V. Vk[k> j
k-j€l*]
112. V. V. [k+ 1 > j <=> k > j]
[7-96] [7-96]
113. Each nonempty set of integers which has a lower bound [7-98] has a least member.
114. V. V [(j eS and Vfc > . [k e S => k + 1 e S] ) => Vk> . k e S] [7-99]
115. Each nonempty set of integers which has an upper bound [7-100] has a greatest member.
116. V. Vg [(j € S and Vk< . [k € S=> k- 1 e S})=> VR< . k e S] [7-100]
117. Vg[(0 e S and Vk[k € S^=> (k+ 1 € S and k - 1 e S)])
Ox Ox O.
*,% *,H. «y.
V |[x J = the greatest integer k such that k< x
Vx «xj = x-[xj
Ox Ox Ox
<-,N #-p X-,%
118 a. V V. [k < [xj <=> k < x]
•— • X K
b. VxVk[k> IxJ <=^ k> x]
c. VxVk [k > [xj <=> k + 1 > x]
d. V V, [k < ffxfl <=> k + 1 < x]
— * X K
e. V V. [k = [xj <=> k < x < k + 1]
— X K
[7-153]
Vkkes]^
[page 7-100]
[7-102] [7-107]
[7-103] [7-104]
"N
> [7-105]
J
119. VxV.([x + J]] = [xj+j
120. VV,ft3,3 [x = ky + z and 0 < z < y] xy>0kzL 7 — Ji
121. V V . A 3 ny > x x y> On7
122. V - j[ -xj = the least integer k such that k > x
123. V V x m
x
m
M
m
and
m
124. V
'x*mo<S¥}
m = [xj -
m
x
m
-m
m ^ m
Ox Ox Ox "ix *V T»
V V. [m I j <=> 3, j = mk]
m j l tJ k J J
*'x Ox Ox V" "<"* *V
125
V (1 In and n In)
[7-105] [7-106] [7-106] [7-106]
[7-111] [7-111]
[7-115 and 7-129] [7-115]
m
[7-154]
126 a. b.
£.
d. e. £.
V V [mln^^ m < n] m n L ' ~~ J
V V V [ (m I n and n I p) ==> m I p] m n p l ' ,r irj
V V [ ( m I n and n I m) => m = n] m n lx ' ' ' J
VmVnVp [(mln and mlp) ==c> mln + Pi
VmVnVp ^mln and mln + P) ^ mlpl VmVnVp [m|n=> mp|np]
"\
> [page 7-115]
y
[7-116]
127. V V 3. 3. HCF(m, n) = mi + nj m n l j
[7-122]
128. V V V. [(HCF(m, n) = 1 and mink) m n k L ' ' '
m
Ik]
[7-129]
129. V V [HCF(m, n) = 1 m n L
V. V. [mi + nj = 0 <=> 3 (i = nk and j = -mk)] ] [7-129] 1 J K
TABLE OF TRIGONOMETRIC RATIOS
[7-155]
|
Angle |
sin |
cos |
tan |
Angle |
sin |
cos |
tan |
|
1° |
.0175 |
.9998 |
.0175 |
46° |
.7193 |
.6947 |
1. 0355 |
|
2° |
.0349 |
.9994 |
.0349 |
47° |
.7314 |
.6820 |
1.0724 |
|
3° |
.05 23 |
.9986 |
.05 24 |
48° |
.7431 |
.6691 |
1. 1106 |
|
4° |
.0698 |
.9976 |
.0699 |
49° |
.7547 |
.6561 |
1. 1504 |
|
5° |
.0872 |
.9962 |
.0875 |
50° |
.7660 |
.6428 |
1. 1918 |
|
6° |
. 1045 |
.9945 |
. 105 1 |
51° |
.7771 |
.6293 |
1.2349 |
|
7° |
. 1219 |
.9925 |
. 1228 |
5 2° |
.7880 |
.6157 |
1.2799 |
|
8° |
. 1392 |
.9903 |
. 1405 |
53° |
.7986 |
.6018 |
1. 3270 |
|
9° |
. 15 64 |
.9877 |
. 15 84 |
54° |
.8090 |
.5878 |
1.3764 |
|
10° |
. 1736 |
.9848 |
. 1763 |
55° |
. 8192 |
.5736 |
1.4281 |
|
11° |
. 1908 |
.9816 |
. 1944 |
5 6° |
.8290 |
.5592 |
1.4826 |
|
12° |
.2079 |
.9781 |
.2126 |
57° |
.8387 |
.5446 |
1.5399 |
|
13° |
.2250 |
.9744 |
.2309 |
5 8° |
. 8480 |
.5 299 |
1. 6003 |
|
14° |
.2419 |
.9703 |
. 2493 |
59° |
.8572 |
.5150 |
i. 6643 |
|
15° |
.25 88 |
.9659 |
.2679 |
60° |
.8660 |
.5000 |
1. 7321 |
|
16° |
. 2756 |
.9613 |
.2867 |
61° |
.8746 |
.4848 |
1.8040 |
|
17° |
.2924 |
.95 63 |
.305 7 |
62° |
.8829 |
.4695 |
1. 8807 |
|
18° |
.3090 |
.9511 |
.3249 |
63° |
.8910 |
.4540 |
1.9626 |
|
19° |
.3256 |
.9455 |
.3443 |
64° |
.8988 |
.4384 |
2. 0503 |
|
20° |
.3420 |
.9397 |
.3640 |
65° |
.9063 |
.4226 |
2. 1445 |
|
21° |
.3584 |
.9336 |
.3839 |
66° |
.9135 |
.4067 |
2. 2460 |
|
22° |
.3746 |
.9272 |
.4040 |
67° |
.9205 |
.3907 |
2.3559 |
|
23° |
.3907 |
.9205 |
.4245 |
68° |
.9272 |
.3746 |
2.4751 |
|
24° |
.4067 |
.9135 |
.445 2 |
69° |
.9336 |
.3584 |
2. 605 1 |
|
25° |
.4226 |
.90 63 |
.4663 |
70° |
.9397 |
.3420 |
2. 7475 |
|
26° |
.4384 |
.8988 |
.4877 |
71° |
.9455 |
.3256 |
2.9042 |
|
27° |
.4540 |
.8910 |
.5095 |
72° |
.9511 |
.3090 |
3.0777 |
|
28° |
.4695 |
.8829 |
.5317 |
73° |
.9563 |
.2924 |
3.2709 |
|
29° |
.4848 |
.8746 |
.5543 |
74° |
.9613 |
.275 6 |
3.4874 |
|
30° |
.5000 |
.8660 |
.5774 |
75° |
.9659 |
.2588 |
3.7321 |
|
3Je |
.5150 |
.85 72 |
. 6009 |
76° |
.9703 |
.2419 |
4. 0108 |
|
32° |
.5299 |
. 8480 |
. 6249 |
77° |
.9744 |
.2250 |
4.3315 |
|
33° |
.5446 |
.8387 |
. 6494 |
78° |
.9781 |
.2079 |
4. 7046 |
|
34° |
.5592 |
.8290 |
. 6745 |
79° |
.9816 |
. 1908 |
5. 1446 |
|
35° |
.5736 |
.8192 |
.7002 |
80° |
.9848 |
.1736 |
5.6713 |
|
36° |
.5878 |
.8090 |
. 7265 |
81° |
.9877 |
. 1564 |
6. 3138 |
|
37° |
. 6018 |
.7986 |
.7536 |
82° |
.9903 |
.1392 |
7. 1154 |
|
38° |
.6157 |
.7880 |
.7813 |
83° |
.9925 |
. 1219 |
8. 1443 |
|
39° |
.6293 |
. 7771 |
.8098 |
84° |
.9945 |
.1045 |
9.5144 |
|
40° |
.6428 |
.7660 |
.8391 |
85' |
.9962 |
.0872 |
11.4301 |
|
41° |
.65 61 |
.7547 |
.8693 |
86° |
.9976 |
.0698 |
14.3007 |
|
42° |
.6691 |
.7431 |
.9004 |
87° |
.9986 |
.0523 |
19.0811 |
|
43° |
. 6820 |
.7314 |
.93 25 |
88° |
.9994 |
.0349 |
28. 6363 |
|
44° |
.6947 |
.7193 |
.9657 |
89° |
.9998 |
.0175 |
57. 2900 |
|
45° |
.7071 |
.7071 |
1.0000 |
[7-156]
TABLE OF SQUARES AND SQUARE ROOTS
n
1 2
3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
25 26 27 28 29
30 31 32 33 34
35 36 37 38 39
40 41 42 43 44
45 46 47 48 49
1
4
9
16
25 36 49 64 81
100 121 144 169 196
225
256 289 324 361
400 441 484 529 576
625 676 729 784 841
900
961
1024
1089
1156
1225 1296 1369 1444 1521
1600 1681 1764 1849 1936
2025 2116 2209 2304 2401
1.000 1.414 1.732 2.000
2. 236 2.449 2.646 2.828 3.000
3. 162 3.317
3.464 3.606 3.742
3.873 4.000
4. 123 4.243 4.359
4.472 4.583 4.690 4.796 4.899
5.000 5.099
5. 196 5.292 5.385
5.477 5.5 68
5. 657 5.745 5.831
5.916 6.000 6.083
6. 164 6. 245
6.325 6.403 6.481 6.557 6. 633
6.708 6.782 6.856 6.928 7.000
yflOn
3. 162 4.472 5.477 6.325
7.071 7.746 8.367 8.944 9.487
10.000 10.488 10.954 11.402 11.832
12.247 12. 649 13.038 13.416 13.784
14. 142 14.491 14.832 15. 166 15.492
15.811 16. 125 16.432 16.733 17.029
17.321 17.607 17.889 18. 166 18.439
18. 708 18.974 19.235 19.494 19.748
20.000 20. 248 20.494 20.736 20.976
21.213 21.448 21.679 21.909 22. 136
50 2500 7.071 22.361
n
51 52 53
54
55 56 57 58 59
60 61 62 63 64
65 66 67 68 69
70 71 72 73 74
75 76 77 78 79
80 81 82 83 84
85 86 87 88 89
90 91 92 93 94
95 96 97 98 99
n
2601 2704 2809 2916
3025 3136 3249 3364 3481
3600 3721 3844 3969 4096
4225 435 6 4489 4624 4761
4900 5041 5184 5329 5476
5625 5776 5929 6084 6241
6400 6561 6724 6889 705 6
7225 7396 75 69 7744 7921
8100 8281 8464 8649 8836
9025 9216 9409 9604 9801
7.141 7.211
7. 280 7.348
7.416 7.483 7.550 7.616 7.681
7.746 7.810 7.874 7.937 8.000
8.062
8. 124 8. 185 8.246 8.307
8.367 8.426 8.485 8.544 8. 602
8.660 8.718 8.775 8.832 8.888
8.944 9.000 9.055 9.110 9.165
9.220 9.274 9.327 9.381 9.434
9.487 9.539 9.592 9.644 9.695
9.747 9.798 9.849 9.899 9.950
VTOn
22.583 22.804 23.022 23.238
23.452 23.664 23.875 24.083 24.290
24.495 24.698 24.900 25. 100 25.298
25.495 25.690 25.884 26.077 26.268
26.458 26. 646 26.833 27.019 27.203
27.386 27.568 27.749 27.928 28. 107
28.284 28.460 28.636 28.810 28.983
29. 155 29.326 29.496 29.665 29.833
30.000 30. 166 30.332 30.496 30.659
30.822 30.984 31. 145 31.305 31.464
100 10000 10.000 31.623