1.

2 Exercises

1. Let X be the set of all students at a university. Let A be the set of students
who are first-year students, B the set of students who are second-year
students, C the set of students who are in a discrete mathematics course,
D the set of students who are international relations majors, E the set
of students who went to a concert on Monday night, and F the set of
students who studied until 2 A.M. on Tuesday. Express in set theoretic
notation the following sets of students:
(a) All second-year students in the discrete mathematics course.
Sample Solution. {x ∈ X : x ∈ B and x ∈ C}.
(b) All first-year students who studied until 2 AM on Tuesday.
(c) All students who are international relations majors and went to the
concert on Monday night.
(d) All students who studied until 2 AM on Tuesday, are second-year
students, and are not international relations majors.
(e) All first- and second-year students who did not go to the concert on
Monday night but are international relations majors.
(f) All students who are first-year international relations majors or who
studied until 2 AM on Tuesday.
(g) All students who are first- or second-year students who went to a
concert on Monday night.
(h) All first-year students who are international relations majors or went
to a concert on Monday night.
1. (a) {x : x ∈ X and x ∈ B and x ∈ C}
1. (b) {x : x ∈ X and x ∈ A and x ∈ F }
1. (c) {x : x ∈ X and x ∈ D and x ∈ E}
1. (d) {x : x ∈ X and x ∈ F and x ∈ B and x 6∈ D}
1. (e) {x : x ∈ X and (x ∈ A or x ∈ B) and x 6∈ E and x ∈ D}
1. (f) {x ∈ X : (x ∈ A and x ∈ D) or x ∈ F }
1. (g) {x ∈ X : (x ∈ A or x ∈ B) and x ∈ E}
1. (h) {x ∈ X : x ∈ A and (x ∈ D or x ∈ E)}

3. Write three descriptions of the elements of the set {2, 5, 8, 11, 14}.
3. {2, 5, 8, 11, 14}; {n ∈ N : n = 3k − 1 for some k ∈ N such that 1 ≤ k ≤
5}; or {n ∈ Z; n = 3k + 2 for some k ∈ Z such that − 1 < k < 5}.
5. Which of the following pairs of sets are equal? For each pair that is
unequal, find an element that is in one but is not in the other.
(a) {0, 1, 2} and {0, 0, 1, 2, 2, 1}
(b) {0, 1, 3, {1, 2}} and {0, 1, 2, {2, 3}}
(c) {{1, 3, 5}, {2, 4, 6}, {5, 5, 1, 3}} and {{3, 5, 1}, {6, 4, 4, 4, 2}, {2, 4,
4, 2, 6}}
(d) {{5, 3, 5, 1, 5}, {2, 4, 6}, {5, 1, 3, 3}} and {{1, 3, 5, 1}, {6, 4, 2}, {6,
6, 4, 4, 6}}
(e) ∅ and {x ∈ N : x > 1 and x2 = x}
(f) ∅ and {∅}
5. (a) equal
5. (b) not equal; 3 is an element of the first but not the second; 2 is an
element of the second but not the first.
5. (c) equal
5. (d) not equal; {6,4} is an element of the second but not the first.
5. (e) equal
5. (f) not equal; ∅ is an element of the second but not the first.

7. Let A = {n : n ∈ N and n = 2k + 1 for some k ∈ N}, B = {n : n ∈

N and n = 4k +1 for some k ∈ N}, and C = {m ∈ N : m = 2k −1 and k ∈
N and k ≥ 1}. Prove the following:
(a) 35 ∈ A
(b) 35 ∈ C
(c) 35 6∈ B
(d) A = C
(e) B ⊆ A
(f) B ⊆ C
(g) B ⊂ A
(h) B ⊂ C
7. (a) Solve 35 = 2k + 1 and verify k ≥ 0.
7. (b) Solve 35 = 2k − 1 and verify k ≥ 1.
7. (c) Show that there is no solution for 35 = 4k + 1 with k ∈ N.
7. (d) (⊆) Let 2k0 + 1 ∈ A for some k0 ∈ N. Then 2k0 + 1 = 2(k0 + 1) − 1.
Since k0 ∈ N, we have k0 + 1 ∈ N − {0}. Therefore, A ⊆ C.
(⊇) Let 2k0 − 1 ∈ C for some k0 ∈ N − {0}. Then 2k0 − 1 = 2(k0 − 1) + 1.
Since k0 ∈ N − {0}, we have k0 − 1 ∈ N. Therefore, C ⊆ A.
Since A ⊆ C and C ⊆ A, we have proven that A = C.
7. (e) Let 4k0 + 1 ∈ B for some k0 ∈ N. 4k0 + 1 = 2(2k0 ) + 1. Since
k0 ∈ N, we have 2k0 ∈ N. Therefore, B ⊆ A.
7. (f) Let 4k0 + 1 ∈ B for some k0 ∈ N. 4k0 + 1 = 2(2k0 + 1) − 1. Since
k0 ∈ N, we have 2k0 + 1 ∈ N − {0}. Therefore, B ⊆ C.
7. (g) Use (e), (c), and (a).
7. (h) Use (f), (c), and (b).
 9. Describe in words the difference between ∅ and {∅}.
9. The set ∅ has no elements. The set {∅} is a one-element set – its
element is ∅.

1.4 Exercises

1. Let A = {1, 2, 3, . . . , 10}, B = {2, 3, 6, 8}, and C = {3, 5, 4, 8, 2}. Find the
following:
(a) B ∪ C
(b) B ∩ C
(c) B − C
(d) A − B
(e) A − C
1. (a) {2, 3, 4, 5, 6, 8}
1. (b) {2, 3, 8}
1. (c) {6}
1. (d) {1, 4, 5, 7, 9, 10}
1. (e) {1, 6, 7, 9, 10}

3. Let A = {0, 3} and B = {x, y, z}. Find the following:

(a) A × B
(b) A × A × B
(c) B × A
(d) B × A × B
3. (a) {(0, x), (0, y), (0, z), (3, x), (3, y), (3, z)}
3. (b) {(0, 0, x), (0, 0, y), (0, 0, z), (0, 3, x), (0, 3, y), (0, 3, z), (3, 0, x), (3, 0, y),
(3, 0, z), (3, 3, x), (3, 3, y), (3, 3, z)}
3. (c) {(x, 0), (x, 3), (y, 0), (y, 3), (z, 0), (z, 3)}
3. (d) {(x, 0, x), (x, 3, x), (y, 0, x), (y, 3, x), (z, 0, x), (z, 3, x), (x, 0, y), (x, 3, y),
(y, 0, y), (y, 3, y), (z, 0, y), (z, 3, y), (x, 0, z), (x, 3, z), (y, 0, z), (y, 3, z), (z, 0, z),
(z, 3, z)}

5. Prove Theorem 1(d).

5. We must prove (i) A ∪ (B ∪ C) ⊆ (A ∪ B) ∪ C and (ii) (A ∪ B) ∪ C ⊆
A ∪ (B ∪ C).
(i) Let x ∈ A ∪ (B ∪ C). Then either x ∈ A or x ∈ B ∪ C. In the first
case x ∈ A ∪ B (Theorem 1 (b)). Therefore, x ∈ (A ∪ B) ∪ C by Theorem
1(b). In the second case, either x ∈ B or x ∈ C. When x ∈ B, we have
x ∈ A ∪ B by Theorem 1 (b). Again by Theorem 1(b), x ∈ (A ∪ B) ∪ C.
When x ∈ C, x ∈ (A ∪ B) ∪ C by Theorem 1 (b). In any case, whenever
x ∈ A ∪ (B ∪ C), it follows that x ∈ (A ∪ B) ∪ C.
Part (ii) is analogous and is left to the reader.
7. (a) Draw Venn diagrams to illustrate Theorems 3(a) and 3(b).
(b) Prove Theorem 3(a).
(c) Prove Theorem 3(b).
7. (a)
A A A

U
=

B C
B C C
B

A U (B
U
C) AU B AUC

A A A

=
U

B B C B C
C

U U U
A (B U C) A B A C

7. (b) (⊆) Show that

Suppose x ∈ A∩(B ∪C). It is necessary to show that x ∈ (A∩B)∪(A∩C).
A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C)
Since x ∈ A ∩ (B ∪ C), x ∈ A and x ∈ B ∪ C. From x ∈ B ∪ C it follows
that x ∈ B or x ∈ C.
Case I, x ∈ B. Then, since x ∈ A and x ∈ B, x ∈ A ∩ B. By Theorem 2
(b),
A ∩ B ⊆ (A ∩ B) ∪ (A ∩ C).
Hence, x ∈ (A ∩ B) ∪ (A ∩ C).
Case II, x ∈ B. The proof that x ∈ (A ∩ B) ∪ (A ∩ C) is analogous to
Case I.
(⊇) Show that
(A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C)
So, suppose x ∈ (A ∩ B) ∪ (A ∩ C). It is necessary to show that x ∈
A ∩ (B ∪ C).
Since x ∈ (A ∩ B) ∪ (A ∩ C), x ∈ (A ∩ B) or x ∈ (A ∩ C).
Case I, x ∈ (A ∩ B). Then x ∈ A and x ∈ B. Since x ∈ B and B ⊆ B ∪ C
(Theorem 2(b)), x ∈ B ∪ C. Hence x ∈ A ∩ (B ∪ C).
Case II, x ∈ (A ∩ C). Analogous to Case I.
7. (c) Analogous to (b).

9. Find three sets A, B, and C where A ⊆ B ∪ C but A 6⊆ B and A 6⊆ C.

9. A = {2, 3, 4}. B = {1, 2, 3}. C = {3, 4, 5}.
11. Prove Theorem 7(c).
11. (⇒) Let A = B. If x ∈ A, then x 6∈ A. Since A = B, we conclude that
x 6∈ B. The proof in the other direction is analogous.
(⇐) Let A = B. If x ∈ A, then x 6∈ A. But A = B so x 6∈ B. But x 6∈ B
implies x ∈ B. Therefore, A ⊆ B. The proof in the other direction is
analogous.

13. Let A = {1, 2, {{1, 2}}}.

(a) How many elements does A have? How many elements does P(A)
have? How many elements does P(P(A)) have?
In parts (b)-(m) determine, whether each of the following is true, and if
not, explain why not.

(b) 1 ∈ A (c) {1, 2} ∈ A (d) {{1, 2}} ∈ A (e) ∅ ∈ A (f) 1 ∈ P(A) (g)
{1, 2} ∈ P(A) (h) {{1, 2}} ∈ P(A) (i) ∅ ∈ P(A) (j) 1 ∈ P(P(A)) (k)
{1, 2} ∈ P(P(A)) (l) {{1, 2}} ∈ P(P(A)) (m) ∅ ∈ P(P(A))
13. (a) 3, 8, 256
13. (b) T
13. (c) {{1, 2}} ∈ A not {1, 2}
13. (d) ∅ ⊆ A but ∅ 6∈ A
13. (e) {1} ∈ P(A) not 1
13. (f) T
13. (g) see (f)
13. (h) T
13. (i) T
13. (j) 1 ∈ A, {1} ∈ P(A) and {{1}} ∈ P(P(A))
13. (k) {{1, 2}} ∈ P(P(A))
13. (l) T
13. (m) T

15. Which of the following statements are correct? Prove each correct state-
ment. Disprove each incorrect statement by finding a counterexample.
(a) A and B are disjoint if and only if B and A are disjoint. (Read the
statement carefully – the order in which the sets are listed might matter!)
(b) A ∪ B and C are disjoint if and only if both the following are true: (i)
A and C are disjoint and (ii) B and C are disjoint.
(c) A ∩ B and C are disjoint if and only if both the following are true: (i)
A and C are disjoint and (ii) B and C are disjoint.
(d) A ∪ B and C are disjoint if and only if one of the following is true: (i)
A and C are disjoint or (ii) B and C are disjoint.
(e) A ∩ B and C are disjoint if and only if one of the following is true: (i)
A and C are disjoint or (ii) B and C are disjoint.
(f) Let U be a universal set with A, B ⊆ U. A and B are disjoint if and
only if A and B are disjoint.
 15. (a) True because intersection is commutative.
15. (b) Since (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C), the conclusion follows.
15. (c) A = {1, 2}; B = {3, 4}; C = {1, 3}
15. (d) A = {1, 2}; B = {2, 3, 4}; C = {4}
15. (e) (A ∩ B) ∩ C) = ∅, but A ∩ C = {1} and B ∩ C = {3} are not empty.
15. (f) U = {1, 2, 3}A = {1}; B = {2}

17. Given any four integers x1 , x2 , x3 , and x4 , none of which is even and none
of which is a multiple of 5, prove that some consecutive product of these
integers ends in the digit 1. A consecutive product is one term, two terms
in a row, three terms in a row, or all four terms using the order in which
the integers appear in the list x1 , x2 , x3 , x4 . (Hint. Use a proof by cases.)
17. We do a proof by contradiction. Suppose the statement is false. Then
if any of the integers ends in the digit 1, the consecutive product consisting
of just that one integer ends in the digit 1, as required. So from now on,
suppose none of the integers ends in the digit 1.
Suppose an integer ends in the digit 3. Then no integer ends in the digit
7, because 3 · 7 ends in the digit 1. Thus each of the other integers ends
in the digit 3 or 9. It is not possible that each of the four integers ends
in the digit 3. It is also not possible that three integers end in the digit
3, since the remaining integer would have to end in 9, and 3 · 3 · 9 ends in
1. If two integers end in 3, then the remaining two must end in 9, which
is not possible. If exactly one integer ends in 3, then the others must end
in 9, which is not possible. Therefore, no integer ends in 3.
Now we know that each integer ends in 7 or 9. Suppose that an integer
ends in 9. Then the others must end in 7, but this is impossible because
7 · 7 · 9 ends in 1. Thus all integers must end in 7, but this also is not
possible.
Thus assuming that no consecutive product ends in 1 has lead to an im-
possible situation in every case. Therefore, the statement is true.
√
19. Prove by contradiction that 2 is not a rational number.
√
19. Suppose it is true that 2 is a rational number. Without loss of
generality, we can assume there are integers m and n without common
factors such that √ m
2= .
n
Then
m2
2= 2.
n
Since m and n have no common factors, 2 must divide m. Therefore,
m = 2 · j for some integer j. This tells us that 2n2 = 4j 2 and we can now
conclude that 2 divides n. Therefore, m and n have a common √ factor,
which is a contradiction. We conclude that assuming√that 2 is a ratio-
nal number leads to a contradiction. Consequently, 2 is not a rational
number.
21. Complete the proof of Example 12.
21. x ∨ y = y ∨ x: The operation x ∨ y is to find the maximum of these
two elements. The operation y ∨ x asks to find the maximum of the same
two elements. Therefore, x ∨ y = y ∨ x.
x ∨ (x ∧ y) = x: The operation x ∧ y finds the minimum of x and y. If the
answer is x, you then find x ∨ x which is x. If the answer is y, then x is
less than y and the minimum of x and y is x.
x ∧ (y ∧ z) = (x ∧ y) ∧ z): The min{x, min{y, z}} is either x or min{y, z}.
If x, then
min{min{x, y}, z} = x
as x ≤ y and x ≤ z. If min{y, z} is the minimum, then min{min{x, y}, z} =
min{y, z} as y ≤ x.
x ∨ (y ∨ z) = (x ∨ y) ∨ z: max{x, max{y, z}} is either x or max{y, z}. If x,
then max{max{x, y}, z} = max{x, z} = x. If max{y, z} is the maximum,
then max{max{x, y}, z} = max{y, z}.
x∨(x∧y) = x: the minimum is min{x, max{x, y}} is either x or max{x, y}.
If x, then the result holds. If max{x, y}, then we still get x as x must be
greater than y so max{x, y} = x.

23. Let U be any set and let X = P(U ). Prove that X with the operations ∪
for meet and ∩ for join is a complemented lattice.
23. Use Example 13 with the interpretation of meet and join inter-
changed. For > use ∅ and for ⊥ use X.

25. Prove that in a boolean algebra

a ∨ (b ∧ c) = (a ∨ b) ∧ c

if and only if
a ∨ (b ∧ (a ∨ c)) = (a ∨ b) ∧ (a ∨ c)
and
a ∧ (b ∨ (a ∧ c)) = (a ∧ b) ∨ (a ∧ c)
This property of a boolean algebra is called modularity.
25. (⇐)

(a ∨ b) ∧ (a ∨ c) = ((a ∨ b) ∧ a) ∨ ((a ∨ b) ∧ c)
= (a ∨ (b ∧ a)) ∨ (a ∨ (b ∧ c))
= a ∨ ((b ∧ a) ∨ (b ∧ c))
= a ∨ (b ∧ (a ∨ c))
 The proof of
a ∧ (b ∨ (a ∧ c)) = (a ∧ b) ∨ (a ∧ c)
follows by substituting ∧ for ∨.
(⇒)

(a ∨ b) ∧ c = (a ∧ c) ∨ (b ∧ c)
= c ∧ (a ∨ (c ∧ b))
= c ∧ (a ∨ c) ∧ (a ∨ b)
= (c ∧ (a ∨ c)) ∧ (a ∨ b)
= c ∨ (a ∧ b)

27. Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} be a universal set. Let A, B, C ⊆ U

such that A = {1, 3, 4, 8}, B = {2, 3, 4, 5, 9, 10}, and C = {3, 5, 7, 9, 10}.
Use bit representations for A, B, and C together with U N ION, IN T ER,
DIF F , and COM P to find the bit representation for the following:
(a) A ∪ B
(b) A ∩ B ∩ C
(c) (A ∪ C) ∩ B
(d) (A − B) ∪ C
(e) A ∩ (B − (C ∩ B))
(f) A − (B − C)
(g) (A ∪ B) ∪ (C − B)
27. (a) 1111100111
27. (b) 0010000000
27. (c) 0011100011
27. (d) 1010101111
27. (e) 0001000000
27. (f) 1010000100
27. (g) 1111101111

1.6 Exercises
1. In a class of 35 students who are either biology majors or have blonde hair,
there are 27 biology majors and 21 blondes. How many biology majors
must be blonde?

1. Let A = {students who are biology majors}. B = {students who are

blondes}.

|A ∪ B| = |A| +|B|−|A ∩ B|
35 = 27 + 21 − | {biology majors who are blonde} |
| {biology majors who are blonde} | = 13
3. A tennis camp has 39 players. There are 25 left handed players and 22
players have a two-handed back stroke. How many left-handed players
have a two-handed back stroke if every player is represented in these two
counts?
3. Let A = {left handed players} and B = {players with a two-handed
back stroke}.

|A∪ B| = |A|+|B| −|A∩ B|

39 = 25 + 22 − | A ∩ B |
|A ∩ B| = 25 + 22 − 39
= 8

5. A marketing class did a survey of the number of fast food outlets near
campus. The results of the survey showed the following:

Type of Food Sold No. of Outlets

Hamburgers 15
Tacos 25
Pizza 21
Hamburgers and tacos 11
Hamburgers and pizza 10
Tacos and pizza 14
Hamburgers and tacos and pizza 9
Served none of these items 5

How many fast food outlets are there near campus?

5. Let A = {Outlets serving hamburgers}; B = {Outlets serving tacos};
and C = {Outlets serving pizza}. We will find | A ∪ B ∪ C | and then add
5 since there are five restaurants that do not fit in any of these categories.

|A ∪ B ∪ C | = |A|+|B| +|C |−|A ∩ B|−|A ∩ C |

−| B ∩ C | + | A ∩ B ∩ C |
= 15 + 25 + 21 − 11 − 10 − 14 + 9
= 35

The final answer is 40.

7. A marketing class did a sample survey to find out how many of a class
of 125 people owned CD’s of the Beatles, Alabama, or Bob Marley. The
results of the survey showed the following:

Recording Artist No. of Students Owning CD’s

Beatles 65
Alabama 46
Bob Marley 29
Beatles & Alabama 18
Beatles & Bob Marley 21
Bob Marley & Alabama 12
Beatles, Bob Marley, & Alabama 9

How many of the students owned no CD featuring these performers?

7. Let A = {Students who owned CD’s featuring the Beatles}; B =
{Students who owned CD’s featuring Alabama}; and C = {Students who
owned CD’s featuring Bob Marley}. We will first find | A ∪ B ∪ C |.

|A ∪ B ∪ C | = |A|+|B| +|C |
−|A ∩ B|−|A ∩ C |−|B ∩C |
+|A ∩ B ∩ C |
= 65 + 46 + 29 − 18 − 21 − 12 + 9
= 98

The answer we want is:

|A ∪ B ∪ C| = Total no. of Students − |A ∪ B ∪ C|

= 125 − 98
= 27

9. How many integers between 1 and 250 are divisible by 3 or 5?

9. Let D3 = {Integers in this range divisible by 3}; D5 = {Integers in this
range divisible by 5}; and D15 = {Integers in this range divisible by 15}.
| D3 | = 83. | D5 | = 50. | D3 ∩ D5 | = | D15 | = 16. The answer we want is
the number of distinct integers in this range that are divisible by either 3
or 5.
| D3 ∪ D5 | = | D3 | + | D5 | − | D15 | = 117
11. There are 76 students enrolled in Anth229, Intermediate Anthropology.
Each of these students is also required to enroll in either one or both of
Biol113, Physiology and Engl218, Victorian Poets. Of these 76 students
there are 35 in Biol313 and 49 in Engl218. How many students are enrolled
in all three classes?
11. Let A = {Anth229 students in Biol113} and B = {Anth229 students
in Engl218}.
|A ∪ B| = |A| +|B|−|A ∩ B|
76 = 35 + 49 − | A ∩ B |
| {Anth229 students taking Biol113 and Engl218} | = 8

13. How many numbers between 1 and 1000 are not divisible by 3, 7, or 9?
13. Let D3 = {Integers in this range divisible by 3}; D7 = {Integers
in this range divisible by 7}; D9 = {Integers in this range divisible by
9}; D21 = {Integers in this range divisible by 21}; and D63 = {Integers
in this range divisible by 63}. | D3 | = 333. | D7 | = 142. | D9 | = 111.
| D3 ∩ D7 | = | D21 | = 47. | D3 ∩ D9 | = | D9 | = 111. | D7 ∩ D9 | = | D63 | =
15. | D3 ∩ D7 ∩ D9 | = | D63 | = 15. We want to find | D3 ∪ D7 ∪ D9 |.
This will be: Total number of integers − | D3 ∪ D7 ∪ D9 |.

| D3 ∪ D 7 ∪ D 9 | = 1000 − (| D3 | + | D7 | + | D9 |
− | D21 | − | D9 | − | D63 | + | D63 |)
= 1000 − (333 + 142 + 111 − 47 − 111 − 15 + 15)
= 572

Easier: since D9 ⊆ D3 , we can just compute |D3 ∪ D7 | = 1000 − 333 −

142 + 47 = 572.

15. (a) How many numbers between 1 and 70,000,000, including 1 and
70,000,000, are divisible by 2, 5, or 7?
(b) How many numbers between 1 and 6,000,000, including 1 and 6,000,000,
are divisible by 4, 5, or 6?
15. (a) Let D2 = {Integers in this range divisible by 2}; D5 = {Integers
in this range divisible by 5}; D7 = {Integers in this range divisible by
7}; D10 = {Integers in this range divisible by 10}; D14 = {Integers in
this range divisible by 14}; and D35 = {Integers in this range divisible
by 35}. | D2 | = 35, 000, 000. | D5 | = 14, 000, 000. | D7 | = 10, 000, 000.
| D2 ∩ D5 | = | D10 | = 7, 000, 000. | D2 ∩ D7 | = | D14 | = 5, 000, 000.
| D5 ∩ D7 | = | D35 | = 2, 000, 000. | D2 ∩ D5 ∩ D7 | = | D70 | = 1, 000, 000.
The number of integers in this range that are divisible by 2, 5, or 7 is:

| D2 ∪ D5 ∪ D7 | = | D2 | + | D5 | + | D7 | − | D10 |
− | D14 | − | D35 | + | D70 |
 15. (b) Let D4 = {Integers in this range divisible by 4}; D5 = {Integers
in this range divisible by 5}; D6 = {Integers in this range divisible by
6}; D20 = {Integers in this range divisible by 20}; D12 = {Integers in
this range divisible by 12}; D30 = {Integers in this range divisible by 30};
and D60 = {Integers in this range divisible by 60}. | D4 | = 1, 500, 000.
| D5 | = 1, 200, 000. | D6 | = 1, 000, 000. | D4 ∩ D5 | = | D20 | = 300, 000.
| D4 ∩ D6 | = | D12 | = 500, 000. | D5 ∩ D6 | = | D30 | = 200, 000. | D4 ∩ D5 ∩
D6 | = | D60 | = 100, 000. The number of integers in this range divisible by
4, 5, or 6 is:

| D4 ∪ D5 ∪ D6 | = | D4 | + | D5 | + | D6 | − | D20 | − | D12 | − | D30 | + | D60 |.

17. How many numbers between 1 and 21,000,000, including 1 and 21,000,000,
are divisible by 2, 3, or 5 but not by 7?
17. Let D2 = {Integers in this range divisible by 2}; D3 = {Integers in
this range divisible by 3}; D5 = {Integers in this range divisible by 5};
and D7 = {Integers in this range divisible by 7}. The solution will be to
find the number of numbers divisible by 2, 3, or 5 that are not at the same
time multiples of 7.

|D2 ∪ D3 ∪ D5 | − (|D2 ∩ D7 | + |D3 ∩ D7 | + |D5 ∩ D7 |

− |D2 ∩ D3 ∩ D7 | − |D2 ∩ D5 ∩ D7 | − |D3 ∩ D5 ∩ D7 |)
+ |D2 ∩ D3 ∩ D5 ∩ D7 |
= 15366667 − 1500000 − 1000000 − 600000
+500000 + 300000 + 200000 − 100000
= 13266667

19. Find the number of integers between 1 and 1000, including 1 and 1000,
that are not divisible by any of 4, 5, or 6.
19. Let D4 = {Integers in this range divisible by 4}; D5 = {Integers in
this range divisible by 5}; D6 = {Integers in this range divisible by 6};
D20 = {Integers in this range divisible by 20}; D12 = {Integers in this
range divisible by 12}; D30 = {Integers in this range divisible by 30};
and D60 = {Integers in this range divisible by 60}. | D4 | = 250. | D5 | =
200. | D6 | = 166. | D4 ∩ D5 | = | D20 | = 50. | D4 ∩ D6 | = | D12 | = 83.
| D5 ∩ D6 | = | D30 | = 33. | D4 ∩ D5 ∩ D6 | = | D60 | = 16. In this case we
do not want to find | D4 ∪ D5 ∪ D6 | but the difference between this value
and the total number of integers in the range.

| D4 ∪ D 5 ∪ D 6 | = 1000 − (| D4 | + | D5 | + | D6 |
− | D20 | − | D12 | − | D30 | + | D60 |)
= 1000 − (250 + 200 + 166 − 50 − 83 − 33 + 16)
= 534
21. (a) Extend Example 9 to cover four Victorian gentlemen and four top
hats. With four gentlemen there are 4 × 3 × 2 × 1 = 24 ways to give the
hats back.
(b) Modify part (a) to ask the number of ways, with four gentlemen and
four hats, that at least two gentlemen can get their own hats back.
(c) Solve Example 9 using an alternate proof that counts the number of
ways no gentleman gets his own hat back and subtracts that value from
the total number of ways for the hats to be given back.
(d) Challenge: Solve part (b) using the same method as for part (c).

21. (a) Let H1 be the number of times person 1 receives the right hat; H2
be the number of times person 2 receives the right hat; H3 be the number
of times person 3 receives the right hat; and H4 be the number of times
person 4 receives the right hat.
The answer is:

|H1 ∪ H2 ∪ H3 ∪ H4 | = |H1 | + |H2 | + |H3 | + |H4 |

− |H1 ∩ H2 | − |H1 ∩ H3 | − |H1 ∩ H4 |
− |H2 ∩ H3 | − |H2 ∩ H4 | − |H3 ∩ H4 |
+ |H1 ∩ H2 ∩ H3 | + |H1 ∩ H2 ∩ H4 |
+ |H2 ∩ H3 ∩ H4 | − |H1 ∩ H2 ∩ H3 ∩ H4 |
=6+6+6+6−2−2−2−2−2−2
+1+1+1+1−1
= 15

21. (b) Calculate the number of ways at least one gentleman gets the right
hat back and subtract the number of ways exactly one gentleman gets the
right hat back. The answer is 7.
21. (c) Suppose the gentlemen and their respective hats are numbered 1,
2, 3, and 4. Each way of returning the hats gives rise to an ordered 4-tuple,
where the number in position i for 1 ≤ i ≤ 4 tells which hat was returned
to gentleman i. We will count the number of 4-tuples such that the number
of position i is not equal to i for any i such that 1 ≤ i ≤ 4. There are three
choices for the first position. If the first position is filled with 2, then there
are three choices for position 2. Whatever choice is made for position 2,
there is only one way to fill the remaining two positions because at least
one of the remaining hats belongs to either 3 or 4. Therefore there are
three possibilities if the first position receives 2.
If the first position receives either 3 or 4, there are two possibilities for
position 2 cannot be put in position 2 but either one 1 or x can be chosen
for position 2 where x is either 3 or 4 depending on which hat was put in
position 2. In the case 3 or 4 is put in the first two positions there are two
possibilities for position 3 since either hat 1 or 2 can be put in position
3. This leaves a single remaining possibility for position 4. If one of 3
or 4 is not put in position 1 or 2, there is only one way to fill positions
3 and 4. Altogether there are three ways to distribute the hats so that
no owner received the right hat if the first gentleman received hat 3. The
same statement is true if the first gentleman received hat 4. Since putting
hat 3 in the first position is a different case from putting hat 4 in the first
position, this reasoning leads to six possibilities for passing out the hats
so that no one receives the right one.
Therefore, there are 9 ways to pass out the hats so that no gentleman
receives the right one. Since there are 24 ways to pass out the hats, there
are 15 ways to pass out the hats so that at least one owner receives the
right hat.
21. (d) The solution comes in two parts. The first part is to count the
number of ways no one receives the right hat. This is 9 from (c). The
second part is to count the number of ways only one person receives the
right hat.
The number of assignments for which exactly one hat is given to the right
person can be counted as follows. Since one hat is given to the right
person, the idea is to solve a new problem and count how many ways
three hats can be assigned so that each hat goes to someone other than
the owner.
For the new problem, suppose there are three hats numbered 1, 2, and
3 that must be put in positions 1, 2, and 3 so that no hat is put in the
position of its number. Suppose 2 is put in position 1. There is only one
way to complete the assignment so that 1 and 3 are put in positions 2 and
3 and 3 is not put in position 3. There is also one possibility if 3 is put
in position 1. Thus for each assignment with exactly one hat in the right
place there are two ways to complete the assignment. Therefore there are
8 ways to assign four hats so that exactly one hat is given to its owner.
There are 9 ways to assign hats so that no one gets the right hat and 8
ways to assign hats so that only one person gets the right hat. Therefore
there are 17 ways to assign the hats so that at most one person gets the
right hat. The answer is 24 - 17 = 7.
1.9 Exercises
Assume all variables not given an explicit domain are elements of N.

1. Show that for n = 0, 1, 2 the following is true

12 + 22 + 32 + · · · + n2 = n(n + 1)(2n + 1)/6

1. When n = 0, a sum of the form F (1) + f (2) + · · · + f (n) is understood

to consist of just the f (n) term, which is f (0).

lhs rhs
0: 0 0
1: 1 1 = 1(2)(3)/6
2: 5 5 = 2 (3) (5) / 6

3. Write out the information that describes what the inductive step assumes
and what the step must prove for proving

12 + 22 + 32 + · · · + n2 = n(n + 1)(2n + 1)/6

with n0 given.
3. The inductive hypothesis is that n ∈ T , that is: n ≥ n0 and

12 + 22 + 32 + · · · + n2 = n(n + 1)(2n + 1)/6

What must be proven is that n + 1 ∈ T , that is, n + 1 ≥ n0 and that

12 + 22 + 32 + · · · + n2 + (n + 1)2 = (n + 1)((n + 1) + 1)(2(n + 1) + 1)/6

5. Write out the information that describes what the inductive step assumes
and what the step must prove for proving that 6 divides n3 + 5n with n0
given.
5. The inductive hypothesis is that n ∈ T , that is: n ≥ n0 and that
n ∈ T , that is, 6 | (n3 + 5n). What must now be proven is that n + 1 ∈ T ,
that is: n + 1 ≥ n0 and 6 | ((n + 1)3 + 5(n + 1)).

7. Show for n = 0, 1, 2 that

(n + 1)(2n + 1)(2n + 3)/3 + (2n + 3)2 = (n + 2)(2n + 3)(2n + 5)/3

7.
n (n + 1)(2n + 1)(2n + 3)/3 + (2n + 3)2 (n + 2)(2n + 3)(2n + 5)/3
0 10 10
1 35 35
2 84 84
 9. Show that
n2 + n + 2(n + 1) = (n + 1)2 + (n + 1)

9.

n2 + n + 2(n + 1) = n2 + n + 2n + 2
= n2 + 3n + 2
= n2 + 2n + 1 + (n + 1)
= (n + 1)2 + (n + 1)

11. For which elements n ∈ {0, 1, 2, 3, 4, 5} does 6 divide n3 + 5n?

11.
n n3 + 5n
0 0
1 6
2 18
3 42
4 84
5 150

13. Find the smallest n ∈ N such that 2n2 + 3n + 1 < n3 .

13.

n 2n2 + 3n + 1 n3
0 1 0
1 6 1
2 15 8
3 28 27
4 45 64

The answer is 4.

15. Prove by induction:

(a) 12 + 22 + 32 + · · · + n2 = n (n + 1) (2n + 1)/6 for n ≥ 0
(b) 13 + 23 + 33 + · · · + n3 = (1 + 2 + 3 + · · · + n)2 for n ≥ 0
(c) 14 + 24 + 34 + · · · + n4 = n(n + 1)(2n + 1)(3n2 + 3n − 1)/30 for n ≥ 0
(d) 15 + 25 + 35 + · · · + n5 = 16 n6 + 12 n5 + 5 4
12 n − 1 2
12 n for n ≥ 0
15. (a) Let n0 = 0. Let T = {n ∈ N : 1 + 2 + 3 + · · · + n2 = n (n +
2 2 2

1) (2n + 1)/6}. Note that 02 + 12 + · · · + n2 = 12 + 22 + · · · + n2 .

(Base step) For n = 0 the left-hand side and the right-hand side both
equal 0, so n0 ∈ T .
(Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 and that

n(n + 1)(2n + 1)
12 + 2 2 + 3 2 + · · · + n 2 =
6

is true and show that

(n + 1)(n + 2)(2n + 3)
12 + 22 + 32 + · · · + n2 + (n + 1)2 =
6

and that n + 1 ≥ n0 are true.

12 + 22 + · · · + n2 + (n + 1)2 = (12 + 22 + · · · + n2 ) + (n + 1)2

n(n + 1)(2n + 1)
= + (n + 1)2 (by ind. hyp.)
6
(n + 1)
= (n(2n + 1) + 6n + 6)
6
n+1
= (2n2 + 7n + 6)
6
n+1
= (n + 2)(2n + 3)
6
(n + 1)((n + 1) + 1)(2(n + 1) + 1)
=
6
Since n + 1 > n, it follows that n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N.
15. (b) Let n0 = 0. Let T = {n ∈ N : 13 + 23 + 33 + · · · + n3 =
(1 + 2 + 3 + · · · + n)2 }.
(Base step) For n = 0 the left-hand side and the right-hand side both
equal 0, so n0 ∈ T .
(Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 and that

13 + 23 + 33 + · · · + n3 = (1 + 2 + 3 + · · · + n)2

are true and prove that

13 + 23 + 33 + · · · + n3 + (n + 1)3 = (1 + 2 + 3 + · · · + n + (n + 1))2

and that n + 1 ≥ n0 are true.

13 + 23 + · · · n3 + (n + 1)3 = (13 + 23 + · · · n3 ) + (n + 1)3
= (1 + 2 + · · · + n)2 + (n + 1)3 (by ind. hyp.)
 2
n(n + 1)
= + (n + 1)3 (by Th. 1)
2
n2 (n + 1)2
= + (n + 1)3
4
(n + 1)2 2

= n + 4(n + 1)
4
(n + 1)2
= (n + 2)2
4
 2
(n + 1)(n + 2)
=
2
= (1 + 2 + · · · + n + (n + 1))2 (by Th. 1)

Since n + 1 > n, it follows that n + 1 ≥ n + 0. Therefore, n + 1 ∈ T .

By the Principle of Mathematical Induction, T = N.
15. (c) Let n0 = 0. Let

T = {n ∈ N : 14 + 24 + 34 + · · · + n4 = n(n + 1)(2n + 1)(3n2 + 3n − 1)/30}

(Base step) For n = 0 the left-hand side and the right-hand side both
equal 0, so 0 ∈ T .
(Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 and that

14 + 24 + 34 + · · · + n4 = n(n + 1)(2n + 1)(3n2 + 3n − 1)/30

are true and prove that

14 +24 +34 +· · ·+n4 +(n+1)4 = (n+1)(n+2)(2n+3)(3n+1)2+3(n+1)−1)/30

is true.

14 + 2 4 + 3 4 + · · · + n4 + (n + 1)4 = (14 + 24 + 34 + · · · + n4 ) + (n + 1)4

= n(n + 1)(2n + 1)(3n2 + 3n − 1)/30 + (n + 1)4 (by ind. hyp.)
= (n + 1)(6n4 + 39n3 + 91n2 + 89n + 30)/30
= (n + 1)(n + 2)(2n + 3)(3(n + 1)2 + 3(n + 1) − 1)/30

Of course, n + 1 > n ≥ n0 . Therefore, n + 1 ∈ T .

 By the Principle of Mathematical Induction, T = N.
15. (d) Let n0 = 0. Let
1 6 1 5 5 1
T = {n ∈ N : 15 + 25 + 35 + · · · + n5 = n + n + n4 − n2 }
6 2 12 12

(Base step) For n = 0 the left-hand side and the right-hand side both
equal 0, so 0 ∈ T .
(Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 and that
1 6 1 5 5 1
15 + 2 5 + 3 5 + · · · + n 5 = n + n + n4 − n2
6 2 12 12
are true and prove that
1 1 5 1
15 +25 +35 +· · ·+n5 +(n+1)5 = (n+1)6 + (n+1)5 + (n+1)4 − (n+1)2
6 2 12 12
and n + 1 ≥ n0 are true.

15 + 2 5 + 3 5 + · · · + n5 + (n + 1)5 = (15 + 25 + 35 + · · · + n5 ) + (n + 1)
1 6 1 5 5 1
= n + n + n4 − n2 + (n + 1)5 (by ind. hyp.)
6 2 12 12
5
= (2n6 + 18n5 + 65n4 + 120n3 + 119n2 + 60n + 12)/12
1 1 5 1
= (n + 1)6 + (n + 1)5 + (n + 1)4 − (n + 1)2
6 2 12 12

Of course n + 1 > n ≥ n0 . Therefore, n + 1 ∈ T .

By the Principle of Mathematical Induction, T = N.

Prove by induction:
(a)
1 1 1 n
+ +···+ =
17. 1·2 2·3 n (n + 1) n+1
for n ≥ 1
(b)
1 2 3 n n+2
+ + 3 +···+ n = 2− n
2 22 2 2 2
for n ≥ 1
17. (a) Let n0 = 1. Let
1 1 1 n
T = {n ∈ N : + +··· + = }
1·2 2·3 n(n + 1) n+1

(Base step) For n = 1 the left-hand side and the right-hand side both
equal 1/2, so 1 ∈ T .
(Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 = 1 and that
1 1 1 n
+ +···+ =
1·2 2·3 n(n + 1) n+1
are true and prove that
1 1 1 1 n+1
+ +···+ + =
1·2 2·3 n(n + 1) (n + 1)(n + 2) n+2
and n + 1 ≥ n0 = 1 are true.
1 1 1 1
+ +··· + +
1·2 2·3 n · (n + 1) (n + 1) · (n + 2)
 
1 1 1 1
= + +···+ +
1·2 2·3 n · (n + 1) (n + 1) · (n + 2)
n 1
= + (by ind. hyp.)
n + 1 (n + 1) · (n + 2)
 
1 1
= n+
n+1 n+2
 2 
1 n + 2n + 1
=
n+1 n+2
(n + 1)2
 
1
=
n+1 n+2
n+1
=
n+2
Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = {n ∈ N : n ≥ 1}.

17. (b) Let n0 = 0. Let

1 2 3 n n+2
T = {n ∈ N : + + 3 +···+ n = 2− n }
2 22 2 2 2
(Base step) For n = 1 the left-hand side and the right-hand side both
equal 1/2, so 1 ∈ T .
 (Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 and that
1 2 3 n n+2
+ 2 + 3 +··· + n = 2− n
2 2 2 2 2
are true and prove that
1 2 23 n n+1 (n + 1) + 2
+ 2+ + · · · + n + n+1 = 2 −
2 2 3 2 2 2n+1
and n + 1 ≥ n0 are true.
1 2 23 n n+1
+ 2 + 3 + · · · + n + n+1
2 2 2 2
23
 
1 2 n n+1
= + 2 + 3 + · · · + n + n+1
2 2 2 2
n+2 n+1
= 2 − n + n+1 (by ind. hyp.)
2 2
2n + 2 − n − 1
=2−
2n+1
(n + 1) + 2
=2−
2n+1

Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N.

19. Prove by induction for all n ≥ 0:

(a) 3 divides n3 + 2n
(b) 5 divides n5 − n
(c) 6 divides n3 − n
(d) 6 divides n3 + 5n
19. (a) Let n0 = 0. Let T = {n ∈ N : 3 | (n3 + 2n)}.
(Base step) Since 3|0, we have 0 ∈ T .
(Inductive step) Assume n ∈ T . Now prove n + 1 ∈ T . That is, assume
that n ≥ n0 and that 3 | (n3 + 2n) is true and prove that 3 | ((n + 1)3 +
2(n + 1)) and n + 1 ≥ n0 are true.

(n + 1)3 + 2(n + 1) = n3 + 3n2 + 3n + 1 + 2n + 2

= n3 + 3n2 + 5n + 3
= (n3 + 2n) + (3n2 + 3n + 3)
By the inductive hypothesis 3|(n3 + 2n). Clearly, 3|(3(n2 + n + 1)). Since
3 divides both terms of the sum, 3 divides the sum. Of course, n + 1 ≥ n0 .
Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N.
19. (b) Let n0 = 0. Let T = {n ∈ N : 5 | (n5 − n)}.
(Base step) Since 5|0, we have 0 ∈ T .
(Inductive step) Assume n ∈ T . Now prove n + 1 ∈ T . That is, assume
that n ≥ n0 and that 5 | (n5 − n) are true and prove that 5 | ((n + 1)5 −
(n + 1)) and n + 1 ≥ n0 are true.

(n + 1)5 − (n + 1) = n5 + 5n4 + 10n3 + 10n2 + 5n + 1 − n − 1

= n5 + 5n4 + 10n3 + 10n2 + 4n
= (n5 − n) + (5n4 + 10n3 + 10n2 + 5n)

By the inductive hypothesis 5|(n5 −n). Clearly, 5|(5n4 +10n3 +10n2 +5n),
so 5 divides the sum. Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .

By the Principle of Mathematical Induction, T = N.

19. (c) Let n0 = 0. Let T = {n ∈ N : 6 | (n3 − n)}.

(Base step) Since 6|0, we have 0 ∈ T .
(Inductive step) Assume n ∈ T . Now prove n + 1 ∈ T . That is, assume
that n ≥ n0 and that 6 | (n3 − n) are true and prove that 6 | ((n + 1)3 −
(n + 1)) and n + 1 ≥ n0 are true.
(n + 1)3 − (n + 1) = n3 + 3n2 + 3n − n − 1
= (n3 − n) + (3n2 + 3n)

Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N.
19. (d) Let n0 = 0. Let T = {n ∈ N : 6 | (n3 + 5n)}.
(Base step) Since 6|0, we have 0 ∈ T .
(Inductive step) Assume n ∈ T . Now prove n + 1 ∈ T . That is, assume
that n ≥ n0 and that 6 | (n3 + 5n) are true and prove that 6 | ((n + 1)3 +
5(n + 1)) and n + 1 ≥ n0 are true.
(n + 1)3 + 5(n + 1) = n3 + 3n2 + 3n + 1 + 5n + 5
= (n3 + 5n) + 3n(n + 1) + 6

By the inductive hypothesis 6 | (n3 + 5n). Since 2 | n(n + 1) we have that

6 | 3n(n + 1), and clearly 6 | 6. Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N.
21. Prove by induction. The sum of the cubes of any three consecutive natural
numbers is divisible by 9.
21. Let n0 = 0. Let T = {n ∈ N : 9 | (n3 + (n + 1)3 + (n + 2)3 )}.
(Base step) For n = 0, (03 + 13 + 23 ) = 9. Clearly, 9|9 so 0 ∈ T .
(Inductive step) Assume n ∈ T . Now prove n + 1 ∈ T . That is, assume
that n ≥ n0 and that 9 | (n3 + (n + 1)3 + (n + 2)3 ) are true and prove that
9 | ((n + 1)3 + (n + 2)3 + (n + 3)3 ) and n + 1 ≥ n0 are true.

(n + 1)3 + (n + 2)3 + (n + 3)3

= n3 + 3n2 + 3n + 1 + n3 + 6n2 + 12n + 8 + n3 + 9n2 + 27n + 9
= 3n3 + 18n2 + 42n + 18
= (3n3 + 9n2 + 15n + 9) + (9n2 + 27n + 9)
= (n3 + (n + 1)3 + (n + 2)3 ) + (9n2 + 27n + 9)

By the inductive hypothesis 9|(n3 + (n + 1)3 + (n + 2)3 ). Clearly, 9|(9(n2 +

3n+1)). Therefore, 9|((n+1)3 +(n+2)3 +(n+3)3 ). Of course, n+1 ≥ n0 ,
Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N.

23. Prove by induction that the following identities are true for the Fibonacci
numbers.
(a) ni=0 F2i+1 = F2n+2 − 1 for n ≥ 0
P
Pn
(b) i=1 Fi2 = Fn · Fn+1 − 1 for n ≥ 1
(c) ni=0 Fi = Fn+2 − 1 for n ≥ 0
P
Pn
23. (a) Let n0 = 0. Let T = {n ∈ N : i=0 F2i+1 = F2n+2 − 1}.
(Base step) For n = 0 we have F1 = 1 and F2 − 1 = 1. Therefore, 0 ∈ T .
(Inductive step) Assume n P∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 and that ni=0 F2i+1 = F2n+2 − 1 are true and prove
Pn+1
that n + 1 ≥ n0 and i=0 F2i+1 = F2n+4 − 1 are true.

n+1
X n
X
F2i+1 = F2i+1 + F2n+3
i=0 i=0
= F2n+2 − 1 + F2n+3 (by ind. hyp.)
= F2n+4 − 1

Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N.
 Pn
23. (b) Let n0 = 1. Let T = {n ∈ N : n ≥ 1 and i=1 Fi2 = Fn ·Fn+1 −1}.
(Base step) For n = 1 we have F12 = 1 and F1 · F2 − 1 = 1 · 2 − 1 = 1, so
1∈T.

P n ∈ T . Now prove that n + 1 ∈ T . That is,

(Inductive step) Assume
assume that n ≥ n0 and ni=1 Fi2 = Fn · Fn+1 − 1 are true and prove that

Pn+1
i=1 Fi2 = Fn+1 · Fn+2 − 1 and n + 1 ≥ n0 are true.
n+1 n
!
X X
Fi2 = Fi2 2
+ Fn+1
i=1 i=1
2
= Fn · Fn+1 − 1 + Fn+1 (by ind. hyp.)
= Fn+1 (Fn + Fn+1 ) − 1
= Fn+1 · Fn+2 − 1

Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N − {0}.
Pn
23. (c) Let n0 = 0. Let T = {n ∈ N : i=0 Fi = Fn+2 − 1}.
(Base step) For n = 0 we have F0 = 1 and F2 − 1 = 1, so 0 ∈ T .
(Inductive step) AssumePn ∈ T . Now prove that n + 1 ∈ T . That is,
n
assume that n ≥ n0 and i=0 Fi = Fn+2 − 1 are true and prove that
Pn+1
i=0 Fi = Fn+3 − 1 and n + 1 ≥ n0 are true.

n+1
X n
X
Fi = Fi + Fn+1
i=0 i=0
= Fn+2 − 1 + Fn+1 (by ind. hyp.)
= Fn+3 − 1

Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N.

25. The Lucas numbers are defined as L0 = 2, L1 = 1, and Ln = Ln−1 +Ln−2

for n ≥ 2. Prove the following identities for Lucas numbers.
(a) L1 + L2 + · · · + Ln = Ln+2 − 3 for n ≥ 1
(b) L21 + L22 + L23 + · · · + L2n = Ln · Ln+1 − 2 for n ≥ 2
(c) L2 + L4 + · · · + L2 n = L2 n+1 − 1 for n ≥ 2
25. (a) Let n0 = 1. Let
T = {n ∈ N : n ≥ 1 and L1 + L2 + · · · + Ln = Ln+2 − 3}

(Base step) For n = 1 both the left-hand side and the right-hand side
equal 1, so 1 ∈ T .
(Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 and
L1 + L2 + · · · + Ln = Ln+2 − 3
are true and prove that
L1 + L2 + · · · + Ln + Ln+1 = Ln+3 − 3
and n + 1 ≥ n0 are true.
L1 + L2 + · · · + Ln + Ln+1 = (L1 + L2 + · · · + Ln ) + Ln+1
= Ln+2 − 3 + Ln+1 (by ind. hyp.)
= Ln+3 − 3

Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = {n ∈ N : n ≥ 1}.
25. (b) Let n0 = 2. Let
T = {n ∈ N : n ≥ 2 and L21 + L22 + L23 + · · · + L2n = Ln · Ln+1 − 2}

(Base step) For n = 2 both the left-hand side and the right-hand side
equal 10. Therefore, 2 ∈ T .
(Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 and L21 + L22 + L23 + · · · + L2n = Ln · Ln+1 − 2 are true
and prove that L21 + L22 + L23 + · · · + L2n + L2n+1 = Ln+1 · Ln+2 − 2 and
n + 1 ≥ n0 are true.
L21 + L22 + L23 + · · · + L2n + L2n+1 = (L21 + L22 + L23 + · · · + L2n ) + L2n+1
= Ln · Ln+1 − 2 + L2n+1 (by ind. hyp.)
= Ln+1 (Ln + Ln+1 ) − 2
= Ln+1 · Ln+2 − 2

Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = {n ∈ N : n ≥ 2}.
25. (c) Let n0 = 1. Let

T = {n ∈ N : n ≥ 1 and L2 + L4 + · · · + L2·n = L2·n+1 − 1}.

(Base step) For n = 1 both the left-hand side and the right-hand side
equal 3.
 (Inductive step) Choose n such that n ≥ n0 and assume n ∈ T . Now
prove that n+1 ∈ T . That is, assume that L2 +L4 +· · ·+L2n = L2n+1 −1
and prove that L2 + L4 + · · · + L2n + L2(n+1) = L2n+3 − 1.

L2 + L4 + · · · + L2n + L2(n+1) = (L2 + L4 + · · · + L2n ) + L2(n+1)

= L2n+1 − 1 + L2(n+1)
= L2n+1 − 1 + L2n+2
= L2n+3 − 1

Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = {n ∈ N : n ≥ 1}.

27. Find a rational number representing each of the following repeating deci-
mals.
(a) 0.537537537537537537537537537.. .
(b) 31.25469696969696969696969.. .
27. (a)
537
999
27. (b)
3094215
99000

29. (a) Prove by induction that 2n > n for n ≥ 0.

(b) Prove that 2n > n directly from Theorem 2 in Section 1.7.4 without
explicit use of induction. (That is, Theorem 2 in Section 1.7.4 itself was
proved using induction, but you should not have to do any additional
induction.)
(c) Prove by induction that 2n > n3 for n ≥ 10.
29. (a) Let n0 = 0. Let T = {n ∈ N : 2n > n}.
(Base step) 20 = 1 > 0 so 0 ∈ T .
(Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume n ≥ n0 and 2n > n are true and prove that 2n+1 > n + 1 and
n + 1 ≥ n0 are true.

2n+1 = 2n + 2n
≥ 2n + 1 for n ≥ 0
> n + 1 (by ind. hyp.)
 Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N.
29. (b) Theorem 2 says that for any n ∈ N there are 2n subsets in the
power set of a set with n elements. Since each element of the set can
be considered as a singleton subset and consequently one of the subsets,
the number of singleton subsets is less than the number of subsets. (The
empty set is a subset, but does not arise as a singleton subset.)Therefore,
n < 2n .
29. (c) Let n0 = 10. Let

T = {n ∈ N : n ≥ 10 and 2n > n3 }.

(Base step) Let n0 = 10. Clearly 1024 > 1000. Hence, 10 ∈ T .

(Inductive step) Assume n ∈ T . We assume that n ≥ n0 and 2n > n3
are true and we must prove 2n+1 > (n + 1)3 or n + 1 ∈ T and n + 1 ≥ n0
are true.

2n+1 = 2 · 2n
> (1 + 1/10)3 · 2n
≥ (1 + 1/n)3 · 2n
> ((n + 1)/n)3 · n3
= (n + 1)3

Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = {n ∈ N : n ≥ 10}.

31. Let T = {n ∈ N : sin (n · π) = 0}. Prove that T = N. (Hint: sin(a + b) =

sin(a) · cos(b) + cos(a) · sin(b).)
31. Let n0 = 0. Let T = {n ∈ N : sin( n · π) = 0}.
(Base step) sin( 0 · π) = 0. Therefore, 0 ∈ T .
(Inductive step) Assume that n ∈ T . That is, assume that n ≥ n0 and
sin(n · π) = 0 are true and prove that sin((n + 1) · π) = 0 and n + 1 ≥ n0
are true.

sin ((n + 1)π) = sin(nπ + π) = sin( nπ)cos(π) + cos( nπ)sin(π) = 0

Of course, n + 1 ≥ n0 . Therefore n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N.
33. (a) Suppose you take out a mortgage for A dollars at a monthly interest
rate I and a monthly payment P. (To calculate I : if the annual interest
rate is 12%, divide by 12 to get a monthly rate of 1%, then replace the
percentage with the decimal fraction 0.01.) Let An denote the amount
you have left to pay off after n months. So, A0 = A by definition. At the
end of each month, you are first charged interest on all the money you
owed during the month and then your payment is subtracted. So,

An+1 = An (1 + I) − P

Prove by induction that

 
P P
An = A− (1 + I)n +
I I

(b) Use this to calculate the monthly payment on a 30-year loan of $100,000
at 12% interest per year. (Note that the formula is inexact, since money
is always rounded off to a whole number of cents. The derivation here
does not do that. We use 12% to make the arithmetic easier. You should
consult a local bank to find a current value.)

33. (a) Let n0 = 0. Let

P P
T = {n ∈ N : n ≥ n0 and An = (A − )(1 + I)n + }
I I

(Base step) For n = 0 the left-hand side and the right-hand side both
equal A0 . Therefore, 0 ∈ T .
(Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 and
P P
An = (A − )(1 + I)n +
I I
are true and prove that
P P
An+1 = (A − )(1 + I)n+1 +
I I
and n + 1 ≥ n0 are true.

An+1 = An (1 + I) − P
P P
= ((A − )(1 + I)n + )(1 + I) − P
I I
P P
= (A − )(1 + I)n+1 + + P − P
I I
P P
= (A − )(1 + I)n+1 +
I I
 Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N.
33. (b) The key for part (b) is that after the last payment the amount
due is 0. In this case A360 = 0. The answer will be found by solving for P
in the following expression:

0 = (100000 − P/0.01)(0.01)360 + P/0.01

35. Prove Theorem 4 of Section 1.5.4, in full generality. You may use The-
orem 3 of Section 1.5.3, because it has already been proven. (Hint: Use
induction on the number of sets.)
35. The proof will be by induction on n the number of sets. Let n0 = 2,
and let

T = {n ∈ N : n ≥ 2 and the Principle of Inclusion-Exclusion holds for n sets}

(Base step) The result is true for n = 1, 2, 3 by Theorem 3 of Section

1.5.3, so 2 ∈ T .
(Inductive step) Assume n ∈ T and prove that n + 1 ∈ T . That is,
assume that n ≥ 2 and that the Principle of Inclusion-Exclusion holds for
n sets are true and prove that the Principle of Inclusion-Exclusion holds
for n + 1 sets and n + 1 ≥ n0 are true.

A1 ∪ A2 ∪ · · · ∪ An ∪ An+1 = (A1 ∪ · · · ∪ An ) ∪ An+1

Using the result for n = 2 gives

| A1 ∪ A2 ∪ · · · ∪ An ∪ An+1 |
= |( A1 ∪ A2 ∪ · · · ∪ An ) + An+1
= | A1 ∪ A2 ∪ · · · ∪ An | + | An+1 |
− | (A1 ∪ A2 ∪ · · · ∪ An ) ∩ An+1 |

but

| (A1 ∪ A2 ∪ · · · ∪ An ) ∩ An+1 | =
| (A1 ∩ An+1 ) ∪ (A2 ∩ An+1 ) ∪ · · · ∪ (An ∩ An+1 ) |

Therefore,

| A1 ∪ A2 ∪ · · · ∪ An ∪ An+1 | = | A1 ∪ A2 ∪ · · · ∪ An | + | An+1 |
− | (A1 ∩ An+1 ) ∪ (A2 ∩ An+1 ) ∪ · · · ∪ (An ∩ An+1 ) |
Two of the three expressions involve the union of n sets so the inductive
hypothesis can be applied to each of them. The subscripts shown and
always distinct between or among themselves.

| A1 ∪ A 2 ∪ · · · ∪ A n | =
Xn X
|Ai | − | Ai ∩ A j |
i=1 i,j≤n
X
+ | Ai ∩ A j ∩ A k | + · · ·
i,j,k≤n

+ (−1)n−1 | A1 ∩ A2 ∩ · · · ∩ An |

and

| (A1 ∩ An+1 ) ∪ (A2 ∩ An+1 ) ∪ · · · ∪ (An ∩ An+1 ) | =

Xn X
| Ai ∩ An+1 | − | (Ai ∩ An+1 ) ∩ (Aj ∩ An+1 ) |
i=1 i,j≤n
X
+ | (Ai ∩ An+1 ) ∩ (Aj ∩ An+1 ) ∩ (Ak ∩ An+1 ) | + · · ·
i,j,k≤n

+ (−1)n−1 | (A1 ∩ An+1 ) ∩ (A2 ∩ An+1 ) ∩ · · · ∩ (An ∩ An+1 ) |

Two simplifications. The first is that only one copy of An+1 need appear
in the intersections of pairs of sets as generated in the right-hand side
of the second equation above. The second simplification is to recognize
that when only one copy of An+1 appears, two terms combine to form a
subsum that can be simplified as follows:
 
X n
X X
 | Ai ∩ A j | + | Ai ∩ An+1 | = | Ai ∩ A j |
i,j≤n i=1 i,j≤n+1

Similarly, we have
X X X
| Ai ∩ A j ∩ A k | + Ai ∩ Aj ∩ An+1 | = |Ai ∩ Aj ∩ Ak |
i,j,k≤n i,j≤n i,j,k≤n+1

and so on. Carrying out the details of these simplifications yields the
result.
37. A common use of induction is to prove various facts that seem to be
fairly obvious but are otherwise awkward or impossible to prove. These
frequently involve expressions with ellipses. Use induction to show that
(a) X ∪ (X1 ∩ X2 ∩ X3 ∩ · · · ∩ Xn ) = (X ∪ X1 ) ∩ (X ∪ X2 ) ∩ · · · ∩ (X ∪ Xn ).
(b) X ∩ (X1 ∪ X2 ∪ X3 ∪ · · · ∪ Xn ) = (X ∩ X1 ) ∪ (X ∩ X2 ) ∪ · · · ∪ (X ∩ Xn ).
(c) (X1 ∩ X2 ∩ · · · ∩ Xn ) = X1 ∪ X2 ∪ · · · ∪ Xn .
(d) (X1 ∪ X2 ∪ · · · ∪ Xn ) = X1 ∩ X2 ∩ · · · ∩ Xn .
37. (a) Let n0 = 1. Let T = {n ∈ N : n ≥ 1 and X ∪ (X1 ∩ X2 ∩ X3 · · · ∩
Xn ) = (X ∪ X1 ) ∩ (X ∪ X2 ) ∩ · · · ∩ (X ∪ Xn )}
(Base step) For n = 1 the result is obvious, so 1 ∈ T .
(Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 and X ∪ (X1 ∩ X2 ∩ X3 · · · ∩ Xk ) = (X ∪ X1 ) ∩ (X ∪
X2 ) ∩ · · · ∩ (X ∪ Xn ) are true and prove that

X ∪ (X1 ∩ X2 ∩ X3 · · · ∩ Xn · · · ∩ Xn+1 ) =

(X ∪ X1 ) ∩ (X ∪ X2 ) ∩ · · · ∩ (X ∪ Xn ) ∩ (X ∪ Xn+1 )
and n + 1 ≥ n0 are true.

X ∪ (X1 ∩ X2 ∩ · · · ∩ Xn ∩ Xn+1 ) =
X ∪ ((X1 ∩ X2 ∩ · · · ∩ Xn ) ∩ Xn+1 ) =
(X ∪ (X1 ∩ X2 ∩ · · · ∩ Xn )) ∩ (X ∪ Xn+1 ) =
((X ∪ X1 ) ∩ (X ∪ X2 ) ∩ · · · ∩ (X ∪ Xn )) ∩ (X ∪ Xn+1 )

Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = {n ∈ N : n ≥ 1}.

37. (b) Let n0 = 1. Let T = {n ∈ N : n ≥ 1 and X ∩ (X1 ∪ X2 ∪ X3 ∪ · · · ∪

Xn ) = (X ∩ X1 ) ∪ (X ∩ X2 ) ∪ · · · ∪ (X ∩ Xn )}.

(Base step) The case n = 1 is obvious. Therefore, 1 ∈ T .

(Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 and X∩(X1 ∪X2 ∪X3 ∪· · ·∪Xn ) = (X∩X1 )∪(X∩X2 )∪
· · ·∪(X ∩Xn ) are true and prove that X ∩(X1 ∪X2 ∪X3 ∪· · ·∪Xn ∪Xn+1 ) =
(X ∩ X1 ) ∪ (X ∩ X2 ) ∪ · · · ∪ (X ∩ Xn ) ∪ (X ∩ Xn+1 ) and n + 1 > n0 are
true.

X ∩ (X1 ∪ X2 ∪ · · · ∪ Xn ∪ Xn+1 ) =
X ∩ ((X1 ∪ X2 ∪ · · · ∪ Xn ) ∪ Xn+1 ) =
(X ∩ (X1 ∪ X2 ∪ · · · ∪ Xn )) ∪ (X ∩ Xn+1 ) =
((X ∩ X1 ) ∪ (X ∩ X2 ) ∪ · · · ∪ (X ∩ Xn )) ∪ (X ∩ Xn+1 )

Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = {n ∈ N : n ≥ 1}.
37. (c) Let n0 = 1. Let

T = {n ∈ N : (X1 ∩ X2 ∩ · · · ∩ Xn ) = X1 ∪ X2 ∪ · · · ∪ Xn }

(Base step) Let n = 1. The proof is obvious. Therefore, 1 ∈ T .

(Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 and

(X1 ∩ X2 ∩ · · · ∩ Xn ) = X1 ∪ X2 ∪ · · · ∪ Xn

are true and prove that

(X1 ∩ X2 ∩ · · · ∩ Xn ∩ Xn+1 ) = X1 ∪ X2 ∪ · · · ∪ Xn ∪ Xn+1

and n + 1 ≥ n0 are true.

X1 ∩ X2 ∩ · · · ∩ Xn ∩ Xn+1 =
(X1 ∩ X2 ∩ · · · ∩ Xn ) ∩ Xn+1 =
(X1 ∩ X2 ∩ · · · ∩ Xn ) ∪ Xn+1 =
X1 ∪ X2 ∪ · · · ∪ Xn ∪ Xn+1

Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = {n ∈ N : n ≥ 1}.

37. (d) Let n0 = 1. Let

T = {n ∈ N : (X1 ∪ X2 ∪ · · · ∪ Xn ) = X1 ∩ X2 ∩ · · · ∩ Xn }

(Base step) The case n = 1 is obvious. Therefore, 1 ∈ T .

(Inductive step) Assume n ∈ T . Now prove that n + 1 ∈ T . That is,
assume that n ≥ n0 and
(X1 ∪ X2 ∪ · · · ∪ Xn ) = X1 ∩ X2 ∩ · · · ∩ Xn
are true and prove that
(X1 ∪ X2 ∪ · · · ∪ Xn ∪ Xn+1 ) = X1 ∩ X2 ∩ · · · ∩ Xn ∩ Xn+1
and n + 1 ≥ n0 are true.
X1 ∪ X2 ∪ · · · ∪ Xn ∪ Xn+1 =
(X1 ∪ X2 ∪ · · · ∪ Xn ) ∪ Xn+1 =
(X1 ∪ X2 ∪ · · · ∪ Xn ) ∩ Xn+1 =
X1 ∩ X2 ∩ · · · ∩ Xn ∩ Xn+1
Of course, n + 1 ≥ n0 . Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = {n : n ≥ 1}.
39. Refer to the Square Root II algorithm.
(a) Complete the proof of Theorem 5.
√
(b) Show that n+1 = −2n /(2Rn ). (Hint: Simplify 17−(Rn +(17/Rn))/2.)
√
(c) How close do you think the value printed is to the actual value of 17?
Approximately how many decimal digits accuracy is that?
39. (a) Solution Required
39. (b)
√
n+1 = 17 − Rn+1
√ Rn + R17n
= 17 −
2
√ Rn2 + 17
= 17 −
2Rn
√
2 17Rn − Rn2 − 17
=
2Rn
(Rn − 17)2
= −
2Rn
2

= − n
2Rn

39. (c) The problem is asking for an upper bound on | 8 |. By part (b),
1 8 1
| 8 | < ( )6·2 −3 = ( )1533
2 2

Thus log10 (| 8 |) is approximately −461.5. So, the approximation is cor-

rect to at least 461 decimal places past the decimal point. (Of course, if
you calculate this on the computer, you probably won’t get 461 decimal
places of accuracy. The problem is round-off error. Normally, a com-
puter rounds off each real number, producing round-off errors. So, there
is a programming-language induced limit on the accuracy of your answer.
Also, as calculations are made with rounded-off numbers, the round-off
errors may increase.) Note that this does not mean that if you print
out the number, the first 461 decimal places are accurate. For example,
0.99999, as an approximation to 1.00000, is accurate to 4 decimal places,
but the actual digits in all those decimal places are different from those of
1.0000. . . .

As before, let Rn denote

√ the value of Root after the loop has been executed
n times. Let n = 17 − Rn , the error in the calculation.
41. Using the Principle of Mathematical Induction, prove the following forms
of the Principle of Mathematical Induction:
(a) Induction with a possibly negative starting point: Suppose that S ⊆ Z,
that some integer n0 ∈ S, and that, for every n ∈ Z, if n ∈ S and n ≥ n0 ,
then n + 1 ∈ S. Then, every integer n ≥ n0 is in S.
(b) Induction downward: Suppose that S ⊆ Z, that some integer n0 ∈ S,
and that, for every n ∈ Z, if n ∈ S and n ≤ n0 , then n − 1 ∈ S. Then, for
every integer n ≤ n0 , we have n ∈ S.
(c) Finite induction upward: Let n0 , n1 ∈ Z, n0 ≤ n1 . Suppose that
S ⊆ Z, that n0 ∈ S, and that for every n ∈ Z, if n ∈ S and n0 ≤ n ≤ n1 ,
then n + 1 ∈ S. Then, every integer n where n0 ≤ n ≤ n1 is in S.
(d) Suppose S ⊆ N is infinite, and suppose that for every n ∈ N, if
n + 1 ∈ S, then n ∈ S. Prove that S = N.
41. (a) et S 0 = {n ∈ N : n0 + n ∈ S}. First prove by induction on that
S 0 = N.
(Base step) Since n0 ∈ S, 0 ∈ S 0 . Suppose k ∈ S 0 . So n0 + k ∈ S.
(Inductive step) By the assumption of the problem, n0 + k + 1 ∈ S.
Hence, k +1 ∈ S 0 . So, by the principle of mathematical induction, S 0 = N.

Now prove that every integer n ≥ n0 is in S. Pick any such n. Since

n ≥ n0 , n − n0 ∈ N. Hence, by the paragraph above, n − n0 ∈ S 0 . So, by
definition of S 0 , n ∈ S.
41. (b) Let S 0 = {n ∈ N : n0 − n ∈ S}. The proof is now analogous to
that in part (a).
41. (c) Let S 0 = {n ∈ N : n0 + n ∈ S or n0 + n > n1 }. The proof is
now analogous to that of part (a), with separate cases depending upon
whether n0 + n ≤ n1 or n0 + n > n1 .
41. (d) Let n ∈ N. Then some n0 ≥ n ∈ S, for otherwise S ⊆ {0, 1, . . . , n−
1}, and S would be finite. Let k = n0 − n.
Now let
S 0 = {m ∈ N : m > n0 or n0 − m ∈ S}
Prove, analogously to part (a), that S 0 = N. Then k ∈ S 0 , so n ∈ S.
1.11 Exercises
Assume all variables not given an explicit domain are elements of N.
1. The terms of a sequence are given recursively as a0 = 2, a1 = 6, and
an = 2 an−1 + 3 an−2 for n ≥ 2. Find the first eight terms of this sequence.
1.

n an
0 2
1 6
2 18
3 54
4 162
5 486
6 1458
7 4374

3. The terms of a sequence are given recursively as a0 = 0, a1 = 4, and

an = 8 an−1 −16 an−2 for n ≥ 2. Find the first eight terms of this sequence.
3.

n an
0 0
1 4
2 32
3 192
4 1024
5 5120
6 24,576
7 114,688

5. The terms of a sequence are given recursively as p0 = 1, p1 = 2, and

pn = 2 pn−1 −pn−2 for n ≥ 2. Write out the information that the inductive
step assumes and what the step must prove in proving bn = 2 · 3n is a
closed form for the sequence. Suppose n0 = 0 is given and the base cases
are 0 and 1.
5. There are two base cases. Let n > n0 + 1 so that n is not a base case
and assume that for all k such that n0 ≤ k < n that k ∈ T . That is, for
each such k, bk = 2 · 3k is a closed form for pk . Now prove that n ∈ T .
That is, bn = 2 · 3n is a closed form for pn = 2pn−1 − pn−2 .

7. The terms of a sequence are given recursively as a0 = 0, a1 = 4, and

an = 8 an−1 − 16 an−2 for n ≥ 2. Write out the information that the
inductive step assumes and what the step must prove in proving bn = n 4n
is a closed form for the sequence. Suppose n0 = 0 and the base cases are
0 and 1.
7. There are two base cases. Let n > n0 +1 so that n is not a base case and
assume that for all k such that n0 ≤ k < n that k ∈ T . That is, for each
such k, bk = k · 4k is a closed form for ak = 8ak−1 − 16ak−2 . Now prove
that n ∈ T . That is, bn = n · 4n is a closed form for an = 8an−1 − 16an−2 .
 9. Given that bn−1 = 2n+1 − 1 and bn−2 = 2n − 1, prove that if bn =
3bn−1 − 2bn−2 , then bn = 2n+2 − 1 provided n ≥ 2.
9.
bn = 3bn−1 − 2bn−2
= 3(2n+1 − 1) − 2(2n − 1) (by ind. hyp.)
= 3 · 2n+1 − 3 − 2n+1 + 2
= 2 · 2n+1 − 1
= 2n+2 − 1

11. The terms of a sequence are given recursively as a0 = 2, a1 = 6, and

an = 2an−1 + 3an−2 for n ≥ 2. Prove by induction that bn = 2 · 3n is a
closed form for the sequence.
11. Let n0 = 0. Let T = {n ∈ N : an = 2 · 3n gives the nth term of the
sequence}.
(Base step) b0 = 2 and b1 = 6. Since a0 = b0 and a1 = b1 , we have
0, 1 ∈ T .
(Inductive step) Now let n > n0 + 1 so that n is not a base case and
assume for all k such that n0 ≤ k < n we have k ∈ T . Prove n ∈ T .

an = 2 an−1 + 3 an−2
= 2 (2 · 3n−1 ) + 3 (2 · 3n−2 ) (by ind. hyp.)
= 4 · 3n−1 + 2 · 3n−1
= 6 · 3n−1 = 2 · 3n

Therefore, n ∈ T .
By the Strong Form of Mathematical Induction, T = N.

13. The terms of a sequence are given recursively as a0 = 0, a1 = 4, and

an = 8an−1 − 16an−2 for n ≥ 2. Prove by induction that bn = n 4n is a
closed form for the sequence.
13. Let n0 = 0. There are two base cases. Let T = {n ∈ N : an = n 4n
gives the nth term of the sequence}.
(Base step) b0 = 0 and b1 = 4. Since a0 = b0 and a1 = b1 , we have
0, 1 ∈ T .
(Inductive step) Now, let n > n0 + 1 so that n is not a base case and
assume for all k such that 1 ≤ k < n that k ∈ T . Prove n ∈ T .

an = 8 an−1 − 16 an−2
= 8 ((n − 1) 4n−1 ) − 16 ((n − 2) 4n−2 ) (by ind. hyp.)
= 8 n 4n−1 − 16 n 4n−2 − 8 4n−1 + 32 4n−2
= 2 n 4 n − n 4n − 2 4 n + 2 4 n
= n 4n

Therefore, n ∈ T .
By the Strong Form of Mathematical Induction, T = N.
15. (a) Prove that with just 3-cent and 5-cent stamps, you can make any
amount of postage (any natural number of cents) except 1 cent, 2 cents, 4
cents, and 7 cents. (Hint: That you can make 0-cent postage is obvious.
You need to prove two things: (i) that you can assemble any amount
of postage except 1 cent, 2 cents, 4 cents, and 7 cents, and (ii) that you
cannot assemble these four amounts. Be careful about whether you use the
Principle of Mathematical Induction or the Strong Form of Mathematical
Induction.)
(b) What amounts of postage can be assembled with 4-cent and 7-cent
stamps only?
(c) What amounts of postage can be assembled with 8-cent and 10-cent
stamps only?
(d) What amounts of postage can be assembled with 7-cent, 8-cent, and
10-cent stamps only?
(e) What amounts of postage can be assembled with 2-cent and 5-cent
stamps only?
15. (a) It is obvious that no sum of 3’s and 5’s can equal 1, 2, 4, or 7. It
is obvious that 8, 9, 10, 11, and 12 are possible. Let n0 = 8. There are
three base cases. Let T = {n ∈ N : you can make any amount of postage
greater than or equal 8 cents with only 3 and 5 cent stamps.}
(Base step) It is clear that 8, 9, 10 ∈ T .
(Inductive step) Choose n such that n > n0 + 2 = 10 so that it is not a
base case and assume for all k such that 7 ≤ k < n that k ∈ T . We must
now prove that n ∈ T . Use the inductive hypothesis for n − 3 and add one
more 3 cent stamp. Therefore, n ∈ T .
By the Strong Form of Mathematical Induction, T ⊇ {n ∈ N : n ≥
8}. Adding the other known initial cases gives T = {n ∈ N : n =
3, 5, 6, or n ≥ 8}.
15. (b) It is obvious that no sum of 4’s and 7’s can equal 1, 2, 3, 5, 6, 9,
10, 13, 17. It is obvious that 18, 19, 20, and 21 are possible. Let n0 = 18.
Let T = {n : you can make any amount of postage greater than or equal
18 cents with only 4 and 7 cent stamps.}
(Base step) It is clear that 18, 19, 20, and 21 ∈ T .
(Inductive step) Choose n such that 21 = n0 + 3 < n so that n is not a
base case and assume for all k such that n0 ≤ k < n that k ∈ T . We must
now prove that n ∈ T . Use the inductive hypothesis for n − 4 cents and
add one more 4 cent stamp. Therefore, n ∈ T .
By the Strong Form of Mathematical Induction, T ⊇ {n ∈ N : n ≥ 18}.
Adding the other initial cases gives

T = {n ∈ N : n = 4, 7, 8, 11, 12, 14, 15, 16, or n ≥ 18}

15. (c) It is clear that no odd amount of postage can be made with 8 and
10. It is easy to show that the even numbers 2, 4, 6, 12, 14, and 22 cannot
be formed as a sum of 8’s and 10’s.
 Let n0 = 12. Let T = {n ∈ N : n ≥ 12 and 2 · n can be formed as a sum
of 8’s and 10’s}.
(Base step) Clearly, 12, 13, 14, 15 ∈ T .
(Inductive step) Choose n such that n ≥ 12 and 15 = n0 + 3 < n so that
n is not a base case and assume for all integers k such that n0 ≤ k < n
that k ∈ T . We must now prove that n ∈ T . Consider 2 · n − 4. Since
24 ≤ 2·n−8 < 2·n since 2·n−8 is even and (n−4) ≥ n0 , by the inductive
hypothesis there is a solution for 2(n − 4). Use this solution together with
an additional 8 cent stamp to find a solution for 2 · n. Therefore, n ∈ T .
By the Strong Form of Mathematical Induction, T = {n ∈ N : n ≥ 12}.
Combining this with some small cases T = {n : n ≥ 12} ∪ {4, 5, 8, 9, 10}.
15. (d) It is obvious that no sum of 7’s, 8’s, and 10’s can equal 1, 2, 3, 4,
5, 6, 9, 11, 12, 13, or 19. It obvious that 7, 8, 10, 14, 15, 16, 17, 18, 20,
21, 22, 23, 24, 25, 26, and 27 are possible. Let n0 = 20. There are 7 base
cases. Let T = {n ∈ N : n and n ≥ 20 and n can be formed as a sum of
7’s, 8’s and 10’s}.
(Base step) Clearly, 20, 21, 22, 23, 24, 25, and 26 ∈ T .
(Inductive step) Choose n such that 26 = n0 + 6 ≤ n so that n is not a
base case and assume for all integers k such that n0 ≤ k < n that k ∈ T .
We must now prove that n ∈ T . Consider n − 7. Since 20 ≤ n − 7 < n,
by the inductive hypothesis there is a solution for n − 7. Use this solution
together with an additional 7 cent stamp to find a solution for n. Therefore,
n∈T.
By the Strong Form of Mathematical Induction, T = {n ∈ N : n ≥
20}. Combining this with the other initial cases T = {n ∈ N : n =
7, 8, 10, 14, 15, 16, 17, 18 or n ≥ 20}.
15. (e) It is obvious that no sum of 2’s and 5’s can equal 1 or 3. It obvious
that 2, 4, 5, and 6 are possible. Let n0 = 4. There are two base cases.
Let T = {n ∈ N : n ≥ 4 and n can be formed as a sum of 2’s and 5’s}.
(Base step) Clearly, 4, 5 ∈ T .
(Inductive step) Choose n such that 5 = n0 + 1 < n so that n is not a
base case and assume for all integers k such that n0 ≤ k < n that k ∈ T .
We must now prove that n ∈ T . Consider n−2. Since 4 ≤ n−2 < n, by the
inductive hypothesis there is a solution for n−2. Use this solution together
with an additional 2 cent stamp to find a solution for n. Therefore, n ∈ T .
By the Strong Form of Mathematical Induction, T = {n ∈ N : n ≥ 4}.
Combining this with some small case gives T = {n ∈ N : n = 2 or n ≥ 4}.

17. Prove that Fn+m = Fn · Fm + Fm−1 · Fn−1 for m ≥ 1. Prove the

following corollaries:
(a) Fn−1 | F2n−1
(b) Fn−1 | F3n−1
 (c) Fn2 + Fn+1
2
is a Fibonacci number
17. Fix n. Let n0 = 1. There are two base cases. Let T = {m ∈ N :
Fn+m = Fn · Fm + Fn−1 · Fm−1 and m ≥ 1}.
(Base step) m = 1. The lhs is Fn+1 . The rhs is Fn ·F1 +Fn−1 ·F0 = Fn+1 .
For m = 2 the lhs is Fn+2 . For the rhs

Fn · F2 + Fn−1 · F1 = 2Fn + Fn−1 = Fn + Fn+1 = Fn+2

Therefore, 1, 2 ∈ T .
(Inductive step) Choose m such that 2 = n0 + 1 < m so that n is not
a base case and assume for all k such that n0 ≤ k < m that k ∈ T . Now
prove that m ∈ T .

Fn+m = Fn+m−1 + Fn+m−2

= Fn Fm−1 + Fn−1 Fm−2 + Fn Fm−2 + Fn−1 Fm−3 (ind. hyp.)
= Fn (Fm−1 + Fm−2 ) + Fn−1 (Fm−2 + Fm−3 ) collecting terms)
= Fn Fm + Fn−1 Fm−1 (using Fibonacci relation)

Therefore, m ∈ T .
By the Strong Form of Mathematical Induction, T = N − {0}.
17. (a) F2n−1 = Fn−1 (Fn + Fn−2 )
17. (b) F3n−1 = F2n−1 Fn +F2n−2 Fn−1 . By part (a) the conclusion follows.
17. (c) Fn+n = Fn2 + Fn−1
2

19. The Lucas numbers are defined as L0 = 2, L1 = 1, and Ln = Ln−1 + Ln−2

for n ≥ 2. Prove that Ln+1 = Fn−1 + Fn+1 for n ≥ 2.
19. Let n = 2. There are two base cases. Let T = {n : n ≥ 2 and Ln =
Fn−1 + Fn+1 }.
(Base step) For n = 2 we have the lhs and the rhs equaling three. For
n = 3 we have
L3 = L 2 + L 1 = F 1 + F 3 + 1 = 4
Therefore, 2, 3 ∈ T .
(Inductive step) Choose n such that 3 = n0 + 1 < n so that n is not
a base case and assume for all k such that n0 ≤ k < n that k ∈ T . Now
prove that n ∈ T . That is, prove that Ln = Fn−1 + Fn+1 is true.

Ln+1 = Ln + Ln−1
= Fn−1 + Fn+1 + Fn−2 + Fn (ind. hyp.)
= Fn + Fn+2

Therefore, n ∈ T .
By the Strong Form of Mathematical Induction, T = {n ∈ N : n ≥ 2}.
 21. What exactly is wrong with the following “proof” that for every real num-
ber x ≥ 0, x = 2x.
Suppose the result is true for all real numbers y where 0 ≤ y < x.
Case 1: x = 0. Then, 2x = 2 · 0 = 0 = x.
Case 2: x > 0. Then, 0 < x/2 < x. So, by hypothesis, x/2 = 2(x/2) = x.
Doubling both sides, deduce that x = 2x. So, the result holds for every
real number x ≥ 0 by the Strong Form of Mathematical Induction.
21. Both forms of the Principle of Mathematical Induction refer to sets of
integers, not sets of reals. This exercise demonstrates that the analogous
principle for real numbers is false.

23. The Binary Search of Phone Directory algorithm in Section 1.10.4 looks for
any page (if any) containing a Name in a telephone book City. The portion
of the algorithm used in searching for the page is called BinarySearch.
Prove that the algorithm works correctly.
23 See the discussion in Chapter 9.

1.12 End of Chapter Materials

Starting to Review
1. Which of the following set descriptions gives the set {2, 8, 14, 20, 26, 32}?
(a) {n ∈ N : n = 2x + 6 for some integer x such that 1 ≤ x ≤ 6}
(b) {n ∈ N : n = 6x + 2 for some integer x such that 1 ≤ x ≤ 6}
(c) {n ∈ N : n = 6x + 2 for some integer x such that 0 ≤ x < 6}
(d) None of the above
1. c

3. What is the contrapositive of the statement “If the sun is shining, then it
is time to go outside.”
(a) If the sun is shining, then it is not time to go outside.
(b) If it is time to go outside, then the sun is shining.
(c) If it is not time to go outside, then the sun is not shining.
(d) None of the above
3. c
 5. Describe each of the following sets in the format {x : property of x}.
(a) A = {0, 2, 4, 6, 8, . . . }
(b) B = { 1, 2, 5, 10, 17, 26, 37, 50 , . . . }
(c) C = {1, 5, 9, 13, 17, 21, . . . }
(d) D ={ 1, 1/2, 1/3, 1/4, 1/5, . . . }
(e) E = {lemon, lime, 1, 3, 5, 7, . . . }
5. (a) {2j : j ∈ N}
5. (b) a1 = 1 and an = an−1 + 2n − 1 for n ≥ 1 and n ∈ N
5. (c) {1 + 4i : i ∈ N}
5. (d) {1/i : i ∈ N and i ≥ 1}
5. (e) {lemon, lime} ∪{j ∈ N : j = 1 + 2(i − 1), where i ∈ N}

7. List the subsets of each of the following sets:

(a) A = {1, 2, 3}
(b) B = {1, {2, 3}}
(c) C = {{1, 2, 3}}
7. (a) {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, ∅
7. (b) {1}, {{2, 3}}, {1, {2, 3}}, ∅
7. (c) ∅, {{1, 2, 3}}

9. List the first eight terms of the sequence defined as c0 = 1, c1 = 3, and cn =

cn−1 + 2cn−2 for n ≥ 2.
9. 1, 3, 5, 11, 21, 43, 85, 171

Review Questions
1. Let A = {1, 2, 4, 7, 8}, B = {1, 4, 5, 7, 9}, and C = {3, 7, 8, 9}. Let
U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Find set expressions using these sets
and the operations of union, intersection, absolute difference, and relative
difference to represent the following sets:
(a) {2, 7, 9}
(b) {3, 5, 6, 7, 9, 10}
1. (a) (A ∩ B ∩ C) ∪ (A ∩ B ∩ C) ∪ (B ∩ C)
1. (b) A ∪ (B ∩ C)
3. For sets A and B, prove that A ∪ (B − A) = A ∪ B.
3.

x ∈ A ∪ (B − A) ⇔ x ∈ A or x ∈ (B − A)
⇔ x ∈ A or (x ∈ B and x 6∈ A)
⇔ (x ∈ A or x ∈ B) and (x ∈ A or x 6∈ A)
⇔ (x ∈ A or x ∈ B) and x ∈ U
⇔ x ∈ A or x ∈ B
⇔ x∈A∪B

5. Prove by induction that 3 + 11 + · · · + (8n − 5) = 4n2 − n for n ∈ N and

n ≥ 1.
5. Let n0 = 1. Let
T = {n : n ≥ 1 and 3 + 11 + · · · + (8n − 5) = 4n2 − n}

(Base step) For n = 1, we have 4n2 − n = 4 − 1 = 3. Therefore, 1 ∈ T .

(Inductive step) Assume n ∈ T and prove that n + 1 ∈ T .
3 + 11 + · · · + 8n − 5 + 8(n + 1) − 5 = 3 + 11 + · · · + 8n − 5) + 8(n + 1) − 5
= 4n2 − n + 8n + 3
= 4n2 + 8n + 4
= 4(n2 + 2n + 1) = (n + 1)
= 4(n + 1)2 − (n + 1)

Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N − {0}.

7. Prove that for every n ∈ N that n3 + n is even.

7. Let n0 = 0. Let T = {n : n ∈ N and n3 + n is even}.
(Base step) For n = 0 we have n3 + n = 0, which is even. Therefore,
0∈T.
(Inductive step) Assume n ∈ T and prove that n + 1 ∈ T .
(n + 1)3 + (n + 1) = n3 + 3n2 + 3n + 1 + n + 1
= (n3 + n) + (3n2 + 3n + 2)
= (n3 + n) + 3n(n + 1) + 2

Since the first term is even by the induction hypothesis and the last term
is even, it remains to prove that 3n(n + 1) is even. This is obvious as with
any two consecutive integers one of them is even. Also the product of
an even number and an odd number is an even number so the conclusion
holds. Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction, T = N.
 9. Prove that bn = 5 · 2n + 1 is a closed form for the recursive relation
a0 = 6, a1 = 11, and an = 3an−1 − 2an−2 for n ≥ 2.
9. Let n0 = 0. Let T = {n : n ∈ N and 5 · 2n + 1 is a closed form for bn }.
(Base step) For n = 0, 1 the condition holds, so 0, 1 ∈ T .
(Inductive step) Choose n such that n is not a base case and n ≥ n0 .
Assume that n0 , n0 + 1, . . . , n − 1 ∈ T and prove that n ∈ T .

an = 3an−1 − 2an − 2 def. of An )

= 15 · 2n + 3 − 10 · 2n−1 + −2 ind. hyp.)
= 20 · 2n−1 + 1 (simplifying the algebra)
= 5 · 2n+1 + 1

Therefore, n ∈ T .
By the Strong Form of Mathematical Induction, T = N.

11. The country of Xabob uses currency consisting of coins with values of 3
zabots and 5 zabots. If you cannot combine some number of these coins
to pay a bill, the item is free. For what number of zabots are items free?
Prove your answer.
11. Find a sum of 3 zabot and 5 zabot coins to total n zabots. Prove by
induction that for all n such that n ≥ 10 that you can make change for
n zabots. In addition show that you can make change using just 3 and 5
zabot coins for {3, 5, 6, 7}. Show you cannot make change for n = 1, 2, 4,
and 7.

13. How many students are in Math 347? From the survey of all the students
in the course it was found that 43 had taken Econ103, 55 had taken
Soci213, 30 had taken Musi111, 8 had taken both Econ103 and Soci213, 13
had taken both Econ103 and Musi111, 15 had taken Soci213 and Musi111,
and 8 had taken none of the courses. No one had taken all three courses.

13. ECON103 SOCI213

22 8 32

0 15
13

MUSI111
Using Discrete Mathematics in Computer Science
1. Prove that the Largest Odd Divisor algorithm outputs the largest odd
divisor of N for all integers N > 0.
1. If N is odd, the while loop is not entered and N is printed as required.
If N is even, N = 2 · l. The first time through the while loop N is replaced
by l. Now since l < N the algorithm works correctly for l. Since the largest
odd divisor of l is the largest odd divisor of N the algorithm is correct.

3. Consider the Binary Search of Phone Directory algorithm. This algorithm

looks for the page (if any) containing a name Name in a telephone book
City. The portion of the algorithm used in searching for the page is called
BinarySearch. Prove that the algorithm works correctly.

3. The answer will be found by an induction on the number of pages in a

directory.
Base step If F irstP age = LastP age = 1 then the while loop will
be executed once during which code the N ame will be found or one
of F irstP age and LastP age will be decremented so that the condition
F irstP age ≤ LastP age will become false or the N ame will be found in
which case P ageF ound become TRUE and the loop terminates.
Inductive step Now suppose the algorithm works for all directories with
1 < k < N pages. The while loop will be entered with F irstP age ≤
LastP age and P ageF ound = F ALSE. If N ame is found on M iddleP age
the value of P ageF ound is changed to TRUE and the loop will terminate
with the correct answer. If N ame is not found on M iddleP age, the while
loop adjusts one of the parameters F irstP age and LastP age. Now when
the while loop condition is tested, the directory to be searched has fewer
than N pages so that the while loop either finds the N ame or makes the
condition F irstP age ≤ LastP age FALSE. Once the loop terminates, the
remainder of the code prints the correct message.

5. Show by induction on n that for b ∈ N, b ≥ 2,

n
X
(b − 1) · bi = bn+1 − 1
i=0

Interpret this identity in the context of number representation in the base

b using the standard positional notation. Start by seeing what this means
for b = 10 and n = 4.
5. This is simply the sum of the geometric series 1 + 10 + 102 + · · · + 10n .
The answer gives the largest number in base b that can be represented by
n digits in that base. For b = 10 and n = 4 we get

9(1 + 10 + 102 + 103 + 104 ) = 99, 999

This is the largest value for that number of digits as all coefficients in an
expansion are less than or equal to b − 1 = 9.
7. Let X and Y be two lists sorted in nondecreasing order. Suppose that for
some positive integer n, there is a combined total of n numbers in the two
lists. Prove that X and Y can be merged into a single list of n numbers
in nondecreasing order using at most n − 1 comparisons.
7. The proof will be by induction on n. Let Z be the merged list. Let
T = {n : two sorted lists of n elements can be sorted into a sorted merged
list using at most n − 1 comparisons}.
(Base step) If n = 1, then either X or Y must be an empty list. But
then the list Z, is obtained by making 0 = n − 1 comparisons. This proves
the case n = 1. Therefore, 1 ∈ T .
(Inductive step) Now suppose that the conclusion of the theorem holds
for some positive integer n > 1. Let X and Y consist of n elements and
show n ∈ T . Compare x and y, the first elements of X and Y , respectively.
CASE 1: x ≤ y : Let X 0 be the list obtained by deleting x from X. Then
X 0 and Y are sorted lists containing a total of n elements. So by the
induction hypothesis, X 0 and Y can be merged into a single sorted list Z 0
using at most n − 1 comparisons. Form the list Z by adjoining x to Z 0
as the first element. Then Z is in nondecreasing order because Z 0 is in
nondecreasing order and x preceded all the other numbers in X and Y .
Moreover, Z was formed using 1 comparison to find that x ≤ y and at
most n − 1 comparisons to form list Z 0 . Therefore, Z was formed using at
most n comparisons.
Case 2: x > y Delete y from Y to form a list Y 0 . Then use the induction
hypothesis as in case 1 to sort X and Y 0 into a list Z 0 using at most k − 1
comparisons. The list Z is then obtained by adjoining y to Z 0 as the first
element. As in case 1, Z is in nondecreasing order and was formed using
at most n comparisons.
Therefore, by the Principle of Mathematical Induction the result is proven.

9. Prove that, at most, n + 1 comparisons are required to determine if a

particular number is in a list of 2n numbers sorted in nondecreasing order.
9. The proof will be by induction on n. Let n0 = 0. Let T = {n : at most
n + 1 comparisons are required to determine if a particular number is in
a list of 2n numbers sorted in nondecreasing or order}
(Base step) For n = 0, we need to show that at most n0 + 1 = 1 com-
parison is required to see if a particular number m is in a list containing
20 = 1 number. Since the list contains only one number, clearly only one
comparison is needed to determine if this number is m.
(Inductive step) Choose n such that n ≥ n0 and assume that n ∈ T .
That is, assume that at most n + 1 comparisons are needed to determine
if a particular number is present in a sorted list of 2n numbers. Now
prove that n + 1 ∈ T . Suppose that we have a list of 2n+1 numbers in
nondecreasing order. We must show that it is possible to determine if a
particular number m is present in this list using at most (n+1)+1 = n+2
comparisons. To do so, we will compare m to the number p in position 2n
of the list.
Case 1: m = p : In this case we need only one comparison to find that m
is in the list. Since 1 ≤ n + 2, the result is true in this case.
Case 2: m < p : Since the list is in nondecreasing order, for m to be
present in the list it must lie in positions 1 through 2n . But the numbers
in positions 1 through 2n are a list of 2n numbers in nondecreasing order.
Hence, by the induction hypothesis we can determine if m is present in this
list by using at most n + 1 comparisons. Therefore, at most 1 + (n + 1) =
n + 2 comparisons are needed to determine if m is present in the original
list.
Case 3: m > p : Since the list is in nondecreasing order, for m to be
present in the list it must lie in positions 2n + 1 through 2n+1 . In this case
at most n + 2 comparisons are needed to determine if m is in the list.
Therefore, n + 1 ∈ T .
By the Principle of Mathematical Induction T = N.