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
Live Music Archive
Librivox Free Audio
Metropolitan Museum
Cleveland Museum of Art
Internet Arcade
Console Living Room
Books to Borrow
Open Library
TV News
Understanding 9/11