Book of Proof
Page 41
i=1
2i−1 = F2n+1+F2n = F2n+2 = F2(n+1)
as desired.
■
283
29.
¡n¢
¢
¢
¢
¢
¢
Prove that 0 + ¡n−1
1
+ ¡n−2
2
+ ¡n−3
3
+ · · · + ¡ 1
n
+ ¡0 = F
−1
n
n+1.
Proof.
¡1¢
¢
(Strong Induction) For n = 1 this is 0 + ¡01 = 1 + 0 = 1 = F2 = F1+1. Thus
the assertion is true when n = 1.
¡k¢
¢
¢
¢
¢
¢
Now fix n and assume that 0 +¡k−1
1
+¡k−2
2
+¡k−3
3
+· · · + ¡ 1
k
+¡0 = F
−1
k
k+1 whenever
k < n
¡n¢
¢
¢
. In what follows we use the identity k = ¡n−1
k
+ ¡n−1
−1
k
. We also often use
¡a¢
b = 0 whenever it is untrue that 0 ≤ b ≤ a.
Ã
!
Ã
!
Ã
!
Ã
!
Ã
!
n
n − 1
n − 2
1
0
+
+
+ · · · +
+
0
1
2
n − 1
n
Ã
!
Ã
!
Ã
!
Ã
!
n
n − 1
n − 2
1
=
+
+
+ · · · +
0
1
2
n − 1
Ã
!
Ã
!
Ã
!
Ã
!
Ã
!
Ã
!
Ã
!
Ã
!
n − 1
n − 1
n − 2
n − 2
n − 3
n − 3
0
0
=
+
+
+
+
+
+ · · · +
+
−1
0
0
1
1
2
n − 1
n
Ã
!
Ã
!
Ã
!
Ã
!
Ã
!
Ã
!
Ã
!
n − 1
n − 2
n − 2
n − 3
n − 3
0
0
=
+
+
+
+
+ · · · +
+
0
0
1
1
2
n − 1
n
"Ã
!
Ã
!
Ã
!#
"Ã
!
Ã
!
Ã
!#
n − 1
n − 2
0
n − 2
n − 3
0
=
+
+ · · · +
+
+
+ · · · +
0
1
n − 1
0
1
n − 2
=
Fn + Fn−1 = Fn
This completes the proof.
■
31.
Pn
¡k¢
¢
Prove that
= ¡n+1 ,
k=0 r
r+1
where r ∈ N.
Hint: Use induction on the integer n. After doing the basis step, break up the
¡k¢
¡k¢
¢
¢
expression r as r = ¡k−1
r
+ ¡k−1
−1
r
. Then regroup, use the induction hypothesis,
and recombine using the above identity.
33. Suppose that n infinitely long straight lines lie on the plane in such a way that
no two are parallel, and no three intersect at a single point. Show that this
n2+n+2
arrangement divides the plane into
2
regions.
Proof. The proof is by induction. For the basis step, suppose n = 1. Then there
is one line, and it clearly divides the plane into 2 regions, one on either side of
the line. As 2 = 12+1+2
2
= n2+n+2
2
, the formula is correct when n = 1.
Now suppose there are n + 1 lines on the plane, and that the formula is correct
for when there are n lines on the plane. Single out one of the n + 1 lines on the
plane, and call it `. Remove line `, so that there are now n lines on the plane.
By the induction hypothesis, these n lines
`
n2+n+2
divide the plane into
5
2
regions. Now add
line ` back. Doing this adds an additional
4
n + 1 regions. (The diagram illustrates the
3
case where n + 1 = 5. Without `, there are
2
n = 4 lines. Adding ` back produces n + 1 = 5
new regions.)
1
284
Solutions
Thus, with n + 1 lines there are all together (n + 1) + n2+n+2
2
regions. Observe
n2 + n + 2
2n + 2 + n2 + n + 2
(n + 1)2 + (n + 1) + 2
(n + 1) +
=
=
.
2
2
2
(n+1)2+(n+1)+2
Thus, with n + 1 lines, we have
2
regions, which means that the
formula is true for when there are n + 1 lines. We have shown that if the
formula is true for n lines, it is also true for n + 1 lines. This completes the
proof by induction.
■
35.
¡n¢
If n, k ∈ N, and n is even and k is odd, then k is even.
Proof.
¡n¢
Notice that if k is not a value between 0 and n, then k = 0 is even; thus
from here on we can assume that 0 < k < n. We will use strong induction.
For the basis case, notice that the assertion is true for the even values n = 2
¡2¢
¡4¢
¡4¢
and n = 4: 1 = 2; 1 = 4; 3 = 4 (even in each case).
&
nbsp; ¡m¢
Now fix and even n assume that k is even whenever m is even, k is odd, and
m < n
¡n¢
¢
¢
. Using the identity k = ¡n−1
k
+ ¡n−1
−1
k
three times, we get
Ã
!
Ã
!
Ã
!
n
n − 1
n − 1
=
+
k
k − 1
k
Ã
!
Ã
!
Ã
!
Ã
!
n − 2
n − 2
n − 2
n − 2
=
+
+
+
k − 2
k − 1
k − 1
k
Ã
!
Ã
!
Ã
!
n − 2
n − 2
n − 2
=
+ 2
+
.
k − 2
k − 1
k
Now, n − 2 is even, and k and k − 2 are odd. By the inductive hypothesis, the
outer terms of the above expression are even, and the middle is clearly even;
¡n¢
thus we have expressed k as the sum of three even integers, so it is even.
■
Chapter 11 Exercises
Section 11.0 Exercises
1. Let A = {0,1,2,3,4,5}. Write out the relation R that expresses > on A. Then
illustrate it with a diagram.
2
1
R = ©(5,4),(5,3),(5,3),(5,3),(5,1),(5,0),(4,3),(4,2),(4,1),
(4, 0), (3, 2), (3, 1), (3, 0), (2, 1), (2, 0), (1, 0)ª
3
0
4
5
3. Let A = {0,1,2,3,4,5}. Write out the relation R that expresses ≥ on A. Then
illustrate it with a diagram.
285
2
1
R
=
©(5,5),(5,4),(5,3),(5,2),(5,1),(5,0),
(4, 4), (4, 3), (4, 2), (4, 1), (4, 0),
3
0
(3, 3), (3, 2), (3, 1), (3, 0),
(2, 2), (2, 1), (2, 0), (1, 1), (1, 0), (0, 0)ª
4
5
5. The following diagram represents a relation R on a set A. Write the sets A
and R. Answer: A = {0, 1, 2, 3, 4, 5}; R = {(3, 3), (4, 3), (4, 2), (1, 2), (2, 5), (5, 0)}
7. Write the relation < on the set A = Z as a subset R of Z × Z. This is an infinite
set, so you will have to use set-builder notation.
Answer: R = {(x, y) ∈ Z × Z : y − x ∈ N}
9. How many different relations are there on the set A = ©1,2,3,4,5,6ª?
Consider forming a relation R ⊆ A × A on A. For each ordered pair (x, y) ∈ A × A,
we have two choices: we can either include (x, y) in R or not include it. There
are 6 · 6 = 36 ordered pairs in A × A. By the multiplication principle, there are
thus 236 different subsets R and hence also this many relations on A.
11. Answer: 2(|A|2)
13. Answer: 6=
15. Answer: ≡ (mod 3)
Section 11.1 Exercises
1. Consider the relation R = {(a, a),(b, b),(c, c),(d, d),(a, b),(b, a)} on the set A = {a, b, c, d}.
Which of the properties reflexive, symmetric and transitive does R possess and
why? If a property does not hold, say why.
This is reflexive because (x, x) ∈ R (i.e., xR x )for every x ∈ A.
It is symmetric because it is impossible to find an (x, y) ∈ R for which ( y, x) ∉ R.
It is transitive because (xR y ∧ yR z) ⇒ xR z always holds.
3. Consider the relation R = {(a, b),(a, c),(c, b),(b, c)} on the set A = {a, b, c}. Which
of the properties reflexive, symmetric and transitive does R possess and why?
If a property does not hold, say why.
This is not reflexive because (a, a) ∉ R (for example).
It is not symmetric because (a, b) ∈ R but (b, a) ∉ R.
It is not transitive because cRb and bR c are true, but cR c is false.
p
p
p p
5. Consider the relation R = ©(0,0),( 2,0),(0, 2),( 2, 2)ª on R. Say whether this
relation is reflexive, symmetric and transitive. If a property does not hold, say
why.
This is not reflexive because (1, 1) ∉ R (for example).
It is symmetric because it is impossible to find an (x, y) ∈ R for which ( y, x) ∉ R.
It is transitive because (xR y ∧ yR z) ⇒ xR z always holds.
7. There are 16 possible different relations R on the set A = {a, b}. Describe all of
them. (A picture for each one will suffice, but don’t forget to label the nodes.)
Which ones are reflexive? Symmetric? Transitive?
286
Solutions
a
b
a
b
a
b
a
b
a
b
a
b
a
b
a
b
a
b
a
b
a
b
a
b
a
b
a
b
a
b
a
b
Only the four in the right column are reflexive. Only the eight in the first and
fourth rows are symmetric. All of them are transitive except the first three
on the fourth row.
9. Define a relation on Z by declaring xR y if and only if x and y have the same
parity. Say whether this relation is reflexive, symmetric and transitive. If a
property does not hold, say why. What familiar relation is this?
This is reflexive because xR x since x always has the same parity as x.
It is symmetric because if x and y have the same parity, then y and x must
have the same parity (that is, xR y ⇒ yR x).
It is transitive because if x and y have the same parity and y and z have the
same parity, then x and z must have the same parity. (That is (xR y∧ yR z) ⇒ xR z
always holds.)
The relation is congruence modulo 2.
11. Suppose A = {a, b, c, d} and R = {(a, a),(b, b),(c, c),(d, d)}. Say whether this relation
is reflexive, symmetric and transitive. If a property does not hold, say why.
This is reflexive because (x, x) ∈ R for every x ∈ A.
It is symmetric because it is impossible to find an (x, y) ∈ R for which ( y, x) ∉ R.
It is transitive because (xR y ∧ yR z) ⇒ xR z always holds.
(For example (aRa ∧ aRa) ⇒ aRa is true, etc.)
13. Consider the relation R = {(x, y) ∈ R × R : x − y ∈ Z} on R. Prove that this relation
is reflexive and symmetric, and transitive.
Proof. In this relation, xR y means x − y ∈ Z.
To see that R is reflexive, take any x ∈ R and observe that x − x = 0 ∈ Z, so xR x.
Therefore R is reflexive.
To see that R is symmetric, we need to prove xR y ⇒ yR x for all x, y ∈ R. We
use direct proof. Suppose xR y. This means x − y ∈ Z. Then it follows that
−(x − y) = y − x is also in Z. But y − x ∈ Z means yRx. We’ve
shown xR y implies
yR x, so R is symmetric.
To see that R is transitive, we need to prove (xR y ∧ yR z) ⇒ xR z is always
true. We prove this conditional statement with direct proof. Suppose xR y and
yR z. Since xR y, we know x − y ∈ Z. Since yRz, we know y − z ∈ Z. Thus x − y
and y − z are both integers; by adding these integers we get another integer
(x − y) +(y − z) = x − z. Thus x − z ∈ Z, and this means xRz. We’ve now shown that
if xR y and yR z, then xR z. Therefore R is transitive.
■
287
15. Prove or disprove: If a relation is symmetric and transitive, then it is also
reflexive.
This is false. For a counterexample, consider the relation R = {(a, a), (a, b), (b, a), (b, b)}
on the set A = {a, b, c}. This is symmetric and transitive but it is not reflexive.
17. Define a relation ∼ on Z as x ∼ y if and only if |x − y| ≤ 1. Say whether ∼ is
reflexive, symmetric and transitive.
This is reflexive because |x − x| = 0 ≤ 1 for all integers x. It is symmetric because
x ∼ y if and only if |x− y| ≤ 1, if and only if |y− x| ≤ 1, if and only if y ∼ x. It is not
transitive because, for example, 0 ∼ 1 and 1 ∼ 2, but is not the case that 0 ∼ 2.
Section 11.2 Exercises
1. Let A = {1,2,3,4,5,6}, and consider the following equivalence relation on A: R =
{(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (2, 3), (3, 2), (4, 5), (5, 4), (4, 6), (6, 4), (5, 6), (6, 5)}. List the equivalence classes of R.
The equivalence classes are: [1] = {1};
[2] = [3] = {2,3};
[4] = [5] = [6] = {4,5,6}.
3. Let A = {a, b, c, d, e}. Suppose R is an equivalence relation on A. Suppose R has
three equivalence classes. Also aRd and bR c. Write out R as a set.
Answer: R = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, d), (d, a), (b, c), (c, b)}.
5. There are two different equivalence relations on the set A = {a, b}. Describe
them all. Diagrams will suffice.
Answer: R = {(a, a), (b, b)} and R = {(a, a), (b, b), (a, b), (b, a)}
7. Define a relation R on Z as xR y if and only if 3x − 5y is even. Prove R is an
equivalence relation. Describe its equivalence classes.
To prove that R is an equivalence relation, we must show it’s reflexive, sym-
metric and transitive.
The relation R is reflexive for the following reason. If x ∈ Z, then 3x − 5x = −2x
is even. But then since 3x − 5x is even, we have xR x. Thus R is reflexive.
To see that R is symmetric, suppose xR y. We must show yR x. Since xR y, we
know 3x − 5 y is even, so 3x − 5 y = 2a for some integer a. Now reason as follows:
3x − 5y = 2a
3x − 5y + 8y − 8x = 2a + 8y − 8x
3 y − 5x = 2(a + 4y − 4x).
From this it follows that 3 y − 5x is even, so yR x. We’ve now shown xR y implies
yR x, so R is symmetric.
To prove that R is transitive, assume that xR y and yR z. (We will show that this
implies xR z.) Since xR y and yR z, it follows that 3x−5 y and 3 y−5z are both even,
so 3x−5 y = 2a and 3 y−5z = 2b for some integers a and b. Adding these equations,
we get (3x − 5 y) + (3 y − 5z) = 2a + 2b, and this simplifies to 3x − 5z = 2(a + b + y).
288
Solutions
Therefore 3x − 5z is even, so xR z. We’ve now shown that if xR y and yR z, then