(1) Let A be the set of people alive on earth. For each relation defined below, determine if it is an equivalence relation on A. If it is, describe the equivalence classes. If it is not, determine which properties of an equivalence relation fail.

(a) aH b ⇐⇒ a and b are the same age in (in years).

6

(b) aG b ⇐⇒ a and b have grandparent in common.

(2) Consider the relation S(x, y) : x is a brother or sister of y on the set, H, of living humans. (Here x is a brother of y will mean x is a male different from y with the same two parents as y, so don’t consider half brothers. Likewise, in general, don’t consider half siblings.) De- termine which of the three properties, reflexive, symmetric, transitive, hold for the relation S (explain your three answers). (Hint: Think carefully about transitive! Almost everyone gets this part wrong.) Is S an equivalence relation on H?

(3) There are many different equivalence relation possible on the set A = {a, b, c, d}. For ex- ample, here are just three different ones:

(a) E1 = {(a, a), (b, b), (c, c), (d, d), (a, c), (c, a), (b, d), (d, b)}.

(b) E2 = {(a, a), (b, b), (c, c), (d, d), (a, c), (c, a), (a, b), (b, a), (b, c), (c, b)}.

(c) E3 = {(a, a), (b, b), (c, c), (d, d)}.

E1 has 8 ordered pairs while E2 has 10 and E3 has 4. Question: Of all the possible equiv- alence relations on A, what is the largest number of ordered pairs possible in the relation?

(4) Let A be the set of all ordered pairs of positive integers. So some members of A are (3, 6), (7, 7), (11, 4), (1, 2981). A relation on A is defined by the rule (a, b)R(c, d) if and only if ad = bc. For example (3, 5)R(6, 10) is true since (3)(10) = (5)(6).

(a) Explain why R is an equivalence relation on A.

(b) List four ordered pairs in the equivalence class of (2, 3).

(5) Let A = {1, 2, 3, 4, 5, 6}. Form a partition of A using {1, 2}, {3, 4, 5}, and {6}. These are the equivalence classes for an equivalence relation, E, on A. Draw the digraph of E.

(6) (bonus) Let A = {1, 2, 3}. The relation E = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)} is an equiv- alence relation on A. F = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} is another equivalence relation on A. Compute the composition F ◦ E. Is F ◦ E and equivalence relation on A?

7. Lesson 7: Test #1

8. Lesson 8

(1) What is the 50th term of the arithmetic sequence with initial term 4 and common difference 3?

7

(2) Evaluate

4∑ k=−3

(2k + 5). (Hint: Since there are only eight terms in the sum, you can just

write them all out and add.)

(3) Evaluate

99∑ i=0

( −2

3

)i . (Hint: Since there are 100 terms in the sum, it isn’t a good idea to

write them all out and add. Use the formula for the sum of terms of a geometric sequence. Leave the answer with exponents rather than using a calculator to try to get a decimal approximation of the answer.)

(4) (a) List the first four terms of the sequence defined recursively by a0 = 2, and, for n ≥ 1, an = 2a

2 n−1 − 1.

(b) List the first five terms of the sequence with initial terms u1 = 1 and u2 = 5, and, for n ≥ 3, un = 5un−1 − 6un−2. Guess a closed form formula for the sequence. Hint: The terms are simple combinations of powers of 2 and powers of 3.

(5) Give a recursive definition of the geometric sequence with initial term a and common ratio r.

Hint: an = ar n−1 isn’t a correct answer since this formula isn’t recursive. Make sure you

write down a recursive formula: (1) give the initial term, and (2) give the rule for building new terms from previous terms.

(6) (bonus) Express in summation notation: 1

2 +

1

4 +

1

6 + · · ·+ 1

2n , the sum of the reciprocals

of the first n even positive integers. (Note that there are n terms in the sum.) Hint: A common mistake on this question is using the symbol n both as an index for

summation and to indicate the last term to be added in. To make sure you haven’t fallen into that trap, replace every n in your formula by a specific value, say 5. The result should

be a sum 1

2 +

1

4 +

1

6 +

1

8 +

1

10 .

9. Lesson 9

(1) A set S of integers is defined recursively by the rules:

(1) 1 ∈ S, and (2) If n ∈ S, then 2n + 1 ∈ S.

(a) Is 20 ∈ S?

(b) Is 175 ∈ S?

Explain your answers.

(2) A set, S, of strings over the alphabet Σ = {a, b, c} is defined recursively by (1) a ∈ S and (2) if x ∈ S then xbc ∈ S. List all the strings in S of length seven or less.

8

(3) A set, S, of positive integers is defined recursively by the rule:

(1) 3 ∈ S, and (2) If n ∈ S, then 2n− 3 ∈ S. List all the elements in the set S.

(4) Give a recursive definition of the set of positive integers that end with the digit 7.

(5) Describe the strings in the set S of strings over the alphabet Σ = {a, b, c} defined recursively by (1) c ∈ S and (2) if x ∈ S then xa ∈ S and xb ∈ S and cx ∈ S.

Hint: Your description should be a sentence that provides an easy test to check if a given string is in the set or not. An example of such a description is: S consists of all strings of a’s, b’s, and c’s, with more a’s than b’s. That isn’t a correct description since cab is in S and doesn’t have more a’s than b’s, and also baac isn’t in S, but does have more a’s than b’s. So that attempted description is really terrible. The best way to do this problem is to use the rules to build a bunch of strings in S until a suitable description becomes obvious.

(6) (bonus) A set S of ordered pairs of integers is defined recursively by (1) (1, 2) ∈ S and (2, 1) ∈ S, and (2) if (m,n) ∈ S, then (m+2, n) ∈ S, and (m,n+2) ∈ S, and (m+1, n+1) ∈ S. There is a simple description of the ordered pairs in S. What is it? Your description should be good enough so that you can instantly decide if (12236, 912242) is in S.

10. Lesson 10

Warning: It’s not unusual to find these problems really tough. One difficulty is that these problems

will make some demands on your algebra skills. Another difficulty is just getting the format of an

inductive proof correct. Here are a few suggestions concerning that: (1) Be sure to check the basis

case; (2) At the start of the inductive step, clearly state the inductive hypothesis; (3) After stating

the inductive hypothesis, write down what you need to prove; (4) Point out clearly where you apply

the inductive hypothesis in the proof of the inductive step.

(1) Use induction to prove: For every integer n ≥ 1,

1 · 2 + 2 · 3 + 3 · 4 + · · ·+ n(n + 1) = n(n + 1)(n + 2) 3

.

(2) Use the first form of induction (see example 16.5) to show that using only 4c/ stamps and 7c/ stamps, any postage amount 18c/ or greater can be formed.

(3) Redo the previous problem using the second form of induction (see example in the text). The basis step is just a bit messier this time, but the inductive step is much easier.

(4) A sequence is defined recursively by the rules: (1) a0 = 0, and (2) for n ≥ 1, an = 2an−1+2. Use induction to prove an = 2

n+1 − 2 for all n ≥ 0.

(5) Use induction to prove: For every integer n ≥ 1, the number n5 − n is a multiple of 5.

9

Hint: An integer is a multiple of 5 if it is 5 times some integer. For example, 165 = (5)(33) so 165 is a multiple of 5.

(6) (bonus) Here is a proof that for n ≥ 0, 1 + 2 + 22 + · · ·+ 2n = 2n+1.

Proof. Suppose 1 + 2 + 22 + · · ·+ 2n = 2n+1 for some n ≥ 0. Then 1 + 2 + 22 + · · ·+ 2n + 2n+1 = 2n+1 + 2n+1 using the inductive hypothesis

= 2(2n+1) = 2n+2 = 2(n+1)+1,

as we needed to show. �

Now, obviously there is something wrong with this proof by induction since, for example, 1 + 2 + 22 = 7, but 22+1 = 23 = 8. What specifically is wrong with the proof?