Chapter 2 Review
155
c H A P t e R 2 review
teRMinoLogy
absolute value (p. 107)
basis step (p. 111)
composite number (p. 107)
contrapositive (p. 103)
converse (p. 103)
counterexample (p. 99)
deductive reasoning (p. 99)
direct proof (p. 101)
divides (p. 107)
Euclidean algorithm
(p. 133)
Euler phi function (p. 149)
even number (p. 101)
Fermat’s last theorem (p. 143)
first principle of mathematical
induction (p. 111)
fundamental theorem of arithmetic
(p. 144)
greatest common divisor (p. 133)
inductive assumption (p. 112)
inductive hypothesis (p. 112)
inductive reasoning (p. 99)
inductive step (p. 111)
linear combination (p. 144)
loop invariant (p. 130)
loop rule of inference (p. 131)
n factorial (p. 99)
number theory (p. 107)
odd number (p. 101)
partial correctness (p. 132)
perfect square (p. 107)
prime number (p. 107)
proof by cases (p. 104)
proof by contradiction (p. 104)
proof by contraposition (p. 103)
proof by exhaustion (p. 100)
rational number (p. 105)
relatively prime (p. 146)
second principle of mathematical
induction (p. 118)
well-ordering principle (p. 119)
section 2.1
1. A conjecture can never be proved merely by proving a finite number of cases.
2. A proof by contradiction of P S Q begins by assuming both P and Q′.
3. In the statement of the theorem, “twice an odd integer is even,” an existential quantifier is understood.
4. To prove the conjecture, “If Laramie is the capital,
then Wyoming is the state,” it is sufficient to prove,
“If Wyoming is the state, then Laramie is the capital.”
5. To prove, “A if and only if B,” requires a proof of
A S B and a proof of B S A.
section 2.2
1. Induction is an appropriate proof technique for
proving a statement about all the positive integers.
2. The basis step of an inductive proof requires proving a property true for n = 1.
3. If the truth of P(k + 1) depends on the truth of
other previous values besides P(k), then the second
principle of induction should be used.
4. The key to a proof by the first principle of induction is to see how the truth of P at the value k + 1
depends on the truth of P at value k.
5. The equation k
3
= k
2
(k+1)
2
/4 is the inductive hypothesis in an inductive proof of the statement
1
3
+ 2
3
+ c + n
3
= n
2
(n + 1)
2
∕4
section 2.3
1. A loop invariant remains true until the loop is exited, at which point it becomes false.
2. Partial correctness of a loop statement in a program
means that the loop behaves correctly for some input values but not for others.
3. The second principle of induction is used to prove
loop invariants because the loop can be executed an
arbitrary number of times.
4. If a loop statement has the form
while (condition B)
P
end while
then the loop invariant Q will be B′.
5. When computing the gcd(42, 30) by the Euclidean
algorithm, the computation of dividing 30 by 12 is
carried out.
section 2.4
1. gcd(a,b) can always be written as a linear combination of a and b.
2. Two integers a and b are relatively prime if there
exist integers i and j such that ia + jb = p where p
is a prime number.
3. If a positive integer n is not a prime number, then it
has at least one prime factor > !n.
4. φ(n) is a prime number for any integer n ≥ 2.
5. φ( p) = p − 1 for any prime number p.
SeLF-teSt
Answer the following true-false questions without looking back in the chapter.
155
c H A P t e R 2 review
teRMinoLogy
absolute value (p. 107)
basis step (p. 111)
composite number (p. 107)
contrapositive (p. 103)
converse (p. 103)
counterexample (p. 99)
deductive reasoning (p. 99)
direct proof (p. 101)
divides (p. 107)
Euclidean algorithm
(p. 133)
Euler phi function (p. 149)
even number (p. 101)
Fermat’s last theorem (p. 143)
first principle of mathematical
induction (p. 111)
fundamental theorem of arithmetic
(p. 144)
greatest common divisor (p. 133)
inductive assumption (p. 112)
inductive hypothesis (p. 112)
inductive reasoning (p. 99)
inductive step (p. 111)
linear combination (p. 144)
loop invariant (p. 130)
loop rule of inference (p. 131)
n factorial (p. 99)
number theory (p. 107)
odd number (p. 101)
partial correctness (p. 132)
perfect square (p. 107)
prime number (p. 107)
proof by cases (p. 104)
proof by contradiction (p. 104)
proof by contraposition (p. 103)
proof by exhaustion (p. 100)
rational number (p. 105)
relatively prime (p. 146)
second principle of mathematical
induction (p. 118)
well-ordering principle (p. 119)
section 2.1
1. A conjecture can never be proved merely by proving a finite number of cases.
2. A proof by contradiction of P S Q begins by assuming both P and Q′.
3. In the statement of the theorem, “twice an odd integer is even,” an existential quantifier is understood.
4. To prove the conjecture, “If Laramie is the capital,
then Wyoming is the state,” it is sufficient to prove,
“If Wyoming is the state, then Laramie is the capital.”
5. To prove, “A if and only if B,” requires a proof of
A S B and a proof of B S A.
section 2.2
1. Induction is an appropriate proof technique for
proving a statement about all the positive integers.
2. The basis step of an inductive proof requires proving a property true for n = 1.
3. If the truth of P(k + 1) depends on the truth of
other previous values besides P(k), then the second
principle of induction should be used.
4. The key to a proof by the first principle of induction is to see how the truth of P at the value k + 1
depends on the truth of P at value k.
5. The equation k
3
= k
2
(k+1)
2
/4 is the inductive hypothesis in an inductive proof of the statement
1
3
+ 2
3
+ c + n
3
= n
2
(n + 1)
2
∕4
section 2.3
1. A loop invariant remains true until the loop is exited, at which point it becomes false.
2. Partial correctness of a loop statement in a program
means that the loop behaves correctly for some input values but not for others.
3. The second principle of induction is used to prove
loop invariants because the loop can be executed an
arbitrary number of times.
4. If a loop statement has the form
while (condition B)
P
end while
then the loop invariant Q will be B′.
5. When computing the gcd(42, 30) by the Euclidean
algorithm, the computation of dividing 30 by 12 is
carried out.
section 2.4
1. gcd(a,b) can always be written as a linear combination of a and b.
2. Two integers a and b are relatively prime if there
exist integers i and j such that ia + jb = p where p
is a prime number.
3. If a positive integer n is not a prime number, then it
has at least one prime factor > !n.
4. φ(n) is a prime number for any integer n ≥ 2.
5. φ( p) = p − 1 for any prime number p.
SeLF-teSt
Answer the following true-false questions without looking back in the chapter.