$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# Appendix C: Answers and Hints for Selected Exercises

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

Section 1.1

1. Sentences (a), (c),(e), (f), (j) and (k) are statements. Sentence (h) is a statement if we are assuming that $$n$$ is a prime number means that $$n$$ is an integer.
2.  Hypothesis Conclusion a. $$n$$ is a prime number. $$n^2$$ has three positive divisors. b. $$a$$ is an irrational number and $$b$$ is an irrational number. $$a \cdot b$$ is an irrational number. c. $$p$$ is a prime number. $$p = 2$$ or $$p$$ is an odd number. d. $$p$$ is a prime number and $$p \ne 2$$. $$p$$ is an odd number.
3. Statements (a), (c), and (d) are true.

4. (a) True when $$a \ne 3$$. (b) True when $$a = 3$$.

6. (a) This function has a maximum value when $$x = \dfrac{5}{16}$$.

9. (a) The set of rational numbers is not closed under division.
(b) The set of rational number sis not closed undre division since division by zero is not defined.
(c) The set of nonzero rational numbers is closed under division.
(d) The set of positive rational numbers is closed under division.
(e) The set of positive real numbers is not closed under subtraction.
(f)The set of negative rational numbers is not closed under division.
(g)The set of negative integers is closed under addition.

Section 1.2

1. (a)
 Step Know Reason $$P$$ $$m$$ is an even integer. Hypothesis $$P$$1 There exists an integers $$k$$ such that $$m = 2k$$. Definition of an even integer $$P$$2 $$m + 1 = 2k + 1$$ Algebra $$Q$$1 There exists an integer $$q$$ such that $$m + 1 = 2q + 1$$. Substitution of $$k = q$$ $$Q$$ $$m + 1$$ is an odd integer. Definition of an odd integer
2. (c) We assume that $$x$$ and $$y$$ are odd integers and will prove that $$x + y$$ is an even integer. Since $$x$$ and $$y$$ are odd, there exist integers $$m$$ and $$n$$ such that $$x = 2m + 1$$ and $$y = 2n + 1$$. Then
$\begin{array} {rcl} {x + y} &= & {(2m + 1) + (2n + 1)} \\ {} &= & {2m + 2n + 2} \\ {} &= & {2(m + n + 1).} \end{array}$
Since the integers are closed under addition, $$(m + n + 1)$$ is an integer, and hence the last equation shows that $$x + y$$ is even. Therefore, we have proven that if $$x$$ and $$y$$ are odd integers, then $$x + y$$ is an even integer.

3. (b) Use Part (a) to prove this.

6. (a) Prove that their difference is equal to zero or prove that they are not zero and their quotient is equal to 1.
(d) Provethattwoofthesideshavethesamelength.Provethatthetriangle has two congruent angles. Prove that an altitude of the triangle is a perpendicular bisector of a side of the triangle.

9. (a) Some examples of type 1 integers are -5, -2, 1, 4, 7, 10.
(c) All example should indicate the proposition is true.

10. (a) Let a and b be integers and assume that a and b are both type 1 integers. Then, there exist integers $$m$$ and $$n$$ such that $$a = 3m + 1$$ and $$b = 3n + 1$$. Now show that

$$a + b = 3 (m + n) + 2.$$

The closure properties of the integers imply that $$m + n$$ is an integer. Therefore, the last equation tells us that $$a + b$$ is a type 2 integer. Hence, we have proved that if $$a$$ and $$b$$ are both type 1 integers, then $$a + b$$ is a type 2 integer.

Section 2.1

1. The statement was true. When the hypothesis is false, the conditional statement is true.

2. (a) $$P$$ is false .
(b) $$P \wedge Q$$ is false.
(c) $$P \vee Q$$ is false.

4. (c) Cannot tell if $$P \wedge R$$ is true or false.

5. Statements (a) and (d) have the same truth table. Statements (b) and (c) have the same truth tables.

7. The two statements have the same truth table.

9. (c) The integer $$x$$ is even only if $$x^2$$ is even.
(d) The integer $$x^2$$ is even is necessary for $$x$$ to be even.

Section 2.2

1. (a) Converse: If $$a^2 = 25$$, then $$a = 5$$. Contrapositive: If $$a^2 \ne 25$$, then $$a \ne 5$$.
(b) Converse: If Laura is playing golf, then it is not raining. Contrapositive: If Laura is not playing golf, then it is raining.

2. (a) Disjunction: $$a \ne 5$$ or $$a^2 = 25$$. Negation: $$a = 5$$ and $$a^2 = 25$$.
(b) Disjunction: It is raining or Laura is playing golf. Negation: It is not raining and Laura is not playing golf.

3. (a) We will not win the first game or we will not win the second game.
(c) You mow the lawn and I will not pay you \$20.
(f) You graduate from college, and you will not get a job and you will not go to graduate school.

7. (a) In this case, it may be better to work with the right side first.

$$\begin{array} {rcl} {(P \to R) \vee (Q \to R)} &\equiv & {(\urcorner R \vee R) \vee (\urcorner Q \vee R)} \\ {} &\equiv & {(\urcorner R \vee \urcorner Q) \vee (R \vee R)} \\ {} &\equiv & {(\urcorner R \vee \urcorner Q) \vee R} {} &\equiv & {\urcorner (P \vee Q) \vee R} \\ {} &\equiv & {(P \wedge Q) \to R.} \end{array}$$

1. Statements (c) and (d) are logically equivalent to the given conditional statement. Statement (f) is the negation of the given conditional statement.

2. (d) This is the contrapositive of the given statement and hence, it is logically equivalent to the given statement.

Section 2.3

1. (a) $$\dfrac{1}{2}, -2\}$$
(d) $$\{1, 2, 3, 4\}$$|
(e) $$\{0.5, 4.5\}$$

2. $$A = \{n ^2\ |\ n \in \mathbb{N}$$
$$D = \{4n\ |\ n \text{is a nonnegative integer and } 0 \le n \le 25\}$$

3. The sets in (b) and (c) are equal to the given set.

5. (a) $$\{x \in \mathbb{Z}\ |\ x \le 5\}$$
(e) $$\{x \in \mathbb{R]\ |\ x^2 > 10\}$$

Section 2.4

1. (a) There exists a rational number x such that $$x^2 - 3x - 7 = 0$$. This statement is false since the solutions of the equation are $$x = \dfrac{3 \pm \sqrt{37}}{2}$$, which are irrational numbers.

2. (b) $$x = 0$$ is a counterexample. The negation is: There exists a real number $$x$$ such that $$x^2 \le 0$$.
(g) $$x = \dfrac{\pi}{2}$$ is a counterexample. The negation is: There exists a real number $$x$$ such that $$\text{tan}^2x + 1 \ne \text{sec}^2 x$$.

3. (a) There exists a rational number $$x$$ such that $$x > \sqrt{2}$$.
The negation is $$(\forall x \in \mathbb{Q})(x \le \sqrt{2})$$, which is, For each rational number $$x$$, $$x \le \sqrt{2}$$.

(c) For each integer $$x$$, $$x$$ is even or $$x$$ is odd.
The negation is $$(\exists x \in \mathbb{Z}$$ ($$x$$ is odd and $$x$$ is even), which is, There exists an integer $$x$$ such that $$x$$ is odd and $$x$$ is even.

(e) For each integer $$x$$, if $$x^2$$ is odd, then $$x$$ is odd.
The negation is $$(\exists x \in \mathbb{Z}$$ ($$x^2$$ is odd and $$x$$ is even), which is, There exists an integer $$x$$ such that $$x^2$$ is odd and $$x$$ is even.
(h) There exists a real number $$x$$ such that cos(2$$x$$) = 2 (cos$$x$$).
The negation is $$(\forall x \in \mathbb{R}$$ (cos(2$$x$$) $$\ne$$ 2(cos$$x$$)), which is, For each real number $$x$$, cos(2$$x$$) $$\ne$$ 2(cos$$x$$).

4. (a) There exist integers $$m$$ and $$n$$ such that $$m > n$$.
(c) There exists an integer $$n$$ such that for each ineger $$m$$, $$m^2 > n$$.

5. (a) $$(\forall m)(\forall n)(m \le n)$$.
For all inetgers $$m$$ and $$n$$, $$m \le n$$.
(e) $$(\forall n)(\exists m)(m^2 \le n)$$.
For each integer $$n$$, there exists an integer $$m$$ such that $$m^2 \le n$$.

10. (a) A function $$f$$ with domain $$\mathbb{R}$$ is strictly increasing provided that $$(\forall x, y \in \mathbb{R})[(x < y) \to (f(x) < f(y))]$$.

Section 3.1

1. (a) Remember that to prove that $$a\ |\ (b - c)$$, you need to prove that there exists an integer $$q$$ such that $$b - c = a \cdot q$$.
(b) What do you need to do in order to prove that $$n^3$$ is odd? Notice that ifn is an odd integer, then there exists an integer $$k$$ such that $$n = 2k + 1$$. Remember that to prove that $$n^3$$ is an odd integer, you need to prove that there exists an integer $$q$$ such that $$n^3 = 2q + 1$$.
Or you can approach this as follows: If $$n$$ is odd, then by Theorem 1.8, $$n^2$$ is odd. Now use the fact that $$n^3 = n \cdot n^2$$.
(c) If 4 divides $$(a - 1)$$, then there exists an integer $$k$$ such that $$a - 1 = 4k$$. Write $$a = 4k + 1$$ and then use algebra to rewrite $$(a^2 - 1)$$.

3. (e) Make sure you first try some examples. How do you prove that an integer is an odd integer?
(f) The following algebra may be useful.

$$4(2m + 1)^2 + 7(2m + 1) + 6 = 6m^2 + 30m + 17.$$

4. (a) If $$xy = 1$$, then $$x$$ and $$y$$ are both divisors of 1, and the only divisors of 1 are -1 and 1.|
(b) Part (a) is useful in proving this.

3. Let $$n \in \mathbb{N}$$. For $$a, b \in \mathbb{Z}$$, you need to prove that if $$a \equiv b$$ (mod $$n$$), then $$b \equiv a$$ (mod $$n$$). Remember that for $$x, y \in \mathbb{Z}$$, $$x \equiv y$$ (mod $$n$$) if and only if $$n\ |\ (x - y)$$.

5. Another hint: $$(4n + 3) - 2(2n + 1) = 1$$.

8. (a) Assuming $$a$$ and $$b$$ are both congruent to 2 modulo 3, there exist integers $$m$$ and $$n$$ such that $$a = 3m + 2$$ and $$b = 3n + 2$$. Then show that

$$a + b = 3(m + n + 1) + 1$$

12. The assumptions mean that $$n\ |\ (a - b)$$ and that $$n\ |\ (c - d)$$. Use these divisibility relations to obtain an expression that is equal to a and to obtain an expression that is equal to c. Then use algebra to rewrite the resulting expressions for $$a + c$$ and $$a \cdot c$$.

Section 3.2

1. (a) Let $$n$$ be an even integer. Since $$n$$ is even, there exists an integer $$k$$ such that $$n = 2k$$. Now use this to prove that $$n^3$$ must be even.
(b) Prove the contrapositive.
(c) Explain why Parts (a) and (b) prove this.
(d) Explain why Parts (a) and (b) prove this.

2. (a) The contrapositive is, For all integers $$a$$ and $$b$$, if $$ab \equiv 0$$ (mod 6), then $$a \equiv 0$$ (mod 6) or $$b \equiv 0$$ (mod 6).

4. (a) If $$a \equiv 2$$ (mod 5), then there exists an integer $$k$$ such that $$a - 2 = 5k$$. Then $$a^2 = (2 + 5k)^2 = 4 + 20k + 25k^2$$. This means that $$a^2 - 4 = 5(4k + 5k^2)$$.

6. One of the two conditional statements is true and one is false.

8. Prove both of the conditional statements: (1) If the area of the right triangle is $$c^2/4$$, then the right triangle is an isosceles triangle. (2) If the right triangle is an isosceles triange, then the area of the right triangle is $$c^2/4$$.

9. Prove the contrapositive.

10. Remember that there are two conditional statements associated with this biconditional statement. Be willing to consider the contrapositive of one of these conditional statements.

15. Define an appropriate function and use the Intermediate Value Theorem.

17. (b) Since 4 divides $$a$$, there exist an integer $$n$$ such that $$a = 4n$$. Using this, we see that $$b^3 = 16n^2$$. This means that b3 is even and hence by Exercise (1), $$b$$ is even. So there exists an integer $$m$$ such that $$b = 2m$$. Use this to prove that $$m^3$$ must be even and hence by Exercise (1), $$m$$ is even.

18. It may be necessary to factor a sum cubes. Recall that

$$u^3 + v^3 = (u + v)(u^2 - uv + v^2).$$

Section 3.3

1. (a) $$P \vee C$$

3. (a) Let $$r$$ be a real number such that $$r^2 = 18$$. We will prove that $$r$$ is irrational using a proof by contradiction. So we assume that $$r$$ is a rational number.
(b) Do not attempt to mimic the proof that the square root of 2 is irrational (Theorem 3.20). You should still use the definition of a rational number but then use the fact that $$\sqrt{18} = \sqrt{9 \cdot 2} = \sqrt{9} \sqrt{2} = 3\sqrt{2}$$.

5. In each part, what is the contrapositive of the proposition? Why does it seem like the contrapositive will not be a good approach? For each statement, try a proof by contradiction.

6. Two of the propositions are true and the other two are false.

11. Recall that $$\text{log}_2 32$$ is the real number $$a$$ such that $$2^{a} = 32$$. That is, $$a = \text{log}_2 32$$ means that $$2^{a} = 32$$. If we assume that $$a$$ is rational, then there exist integers $$m$$ and $$n$$, with $$n \ne 0$$, such that $$a = \dfrac{m}{n}$$.

12. Hint: The only factors of 7 are -1, 1, -7, and 7.

13. (a) What happens if you expand (sin$$\theta$$ + cos$$\theta$$)$$^2$$? Don’tforgetyourtrigono- metric identities.

14. Hint: Three consecutive natural numbers can be represented by $$n$$, $$n + 1$$, and $$n + 2$$, where $$n \in \mathbb{N}$$, or three consecutive natural numbers can be represented by $$m - 1$$, $$m$$ and $$m + 1$$, where $$m \in \mathbb{N}$$.

Section 3.4

1. Use the fact that $$n^2 + n = n(n + 1)$$.

2. Do not use the quadratic formula. Try a proof by contradiction. Hint: If there exists a solution of the equation that is an integer, then we can conclude that there exists an integer $$n$$ such that $$n^2 + n - u = 0$$.

3. First write $$n = 2m + 1$$ for some integer $$m$$. The integer $$m$$ can be even or odd.

5. (c) For all integers $$a$$, $$b$$, and $$d$$ with $$d \ne 0$$, if $$d$$ divides the product $$ab$$, then $$d$$ divides $$a$$ or $$d$$ divdes $$b$$.

8. Try a proof by contradiction with two cases: $$a$$ is even or $$a$$ is odd.

10. (a) One way is to use three cases: (i) $$x > 0$$; (ii) $$x = 0$$; and $$x < 0$$. For the first case, $$-x < 0$$ and $$|-x| = -(-x) = x = |x|$$.

11. (a) For each real number $$x$$, $$|x| \ge a$$ if and only if $$x \ge a$$ or $$x \le -a$$.

Section 3.5

2. (b) Factor $$n^3 - n$$.
(c) Consider using cases based on congruence modulo 6.

3. Let $$n \in \mathbb{N}$$. For $$a, b \in \mathbb{Z}$$, you need to prove that if $$a \equiv b$$ (mod $$n$$), then $$b \equiv a$$ (mod $$n$$). Remember that for $$a, b \in \mathbb{Z}$$, if $$a \equiv b$$ (mod $$n$$), then $$n\ |\ (a - b)$$. So there exists an integer $$k$$ such that $$a - b = nk$$.

4. (a) Use the definition of congruence.
(b) Let $$a \in \mathbb{Z}$$. Corollary 3.32 tell us that if $$a \not\equiv 0$$ (mod 3), then $$a \equiv 1$$ (mod 3) or $$a \equiv 2$$ (mod 3).
(c) For one of the conditional statements, Part (b) tells us we can use a proof by cases using the following two cases: (1) $$a \equiv 1$$ (mod 3); (2) $$a \equiv 2$$ (mod 3).

6. The result in Part (c) of Exercise (4) may be helpful in a proof by contradiction.

8. (a) Remember that $$3\ |\ k$$ if and only if $$k \equiv 0$$ (mod 3).

9. (a) Use a proof similar to the proof of Theorem 3.20. The result of Exercise (8) may be helpful.

12. (a) Use the results in Theorem 3.28 to prove that the remainder must be 1.

Section 4.1

1. The sets in Parts (a) and (b) are inductive.

2. A finite nonempty set is not inductive (why?) but the empty set is inductive (why?).

3. (a) For each $$n \in \mathbb{N}$$, let $$P(n)$$ be, $$2 + 5 + 8 + \cdot\cdot\cdot + (3n - 1) = \dfrac{n(3n + 1)}{2}.$$ Verify that $$P(1)$$ is true. The key to the inductive step is that if $$P(k)$$ is true, then

$$\begin{array} {rcl} {2 + 5 + 8 + \cdot\cdot\cdot + (3k - 1) + [3(k + 1) - 1]} &= & {(2 + 5 + 8 + \cdot\cdot\cdot + (3k - 1)) + (3k + 2)} \\ {} &= & {\dfrac{3k(k + 1)}{2} + (3k + 2).} \end{array}$$

Now use algebra to show that the last expression can be rewritten as $$\dfrac{(k + 1)(3k + 4)}{2}$$ and then explain why this completes the proof that if $$P(k)$$ is true, then $$P(k + 1)$$ is true.

6. The conjecture is that for each $$n \in \mathbb{N}$$, $$\sum_{j = 1}^{n} (2j - 1) = n^2$$. The key to the inductive step is that

$$\begin{array} {rcl} {\sum_{j = 1}^{k + 1} (2j - 1)} &= & {\sum_{j = 1}^{k} (2j - 1) + [2(k + 1) - 1]} \\ {} &= & {\sum_{j = 1}^{k} (2j - 1) + [2k + 1].} \end{array}$$

8. (a) The key to the inductive step is that if $$4^k = 1 + 3m$$, then $$4^{k} \cdot 4 = 4(1 + 3m)$$, which implies that

$$4^{k + 1} - 1 = 3(1 + 4m).$$

13. Let $$k$$ be a natural number. If $$a^k \equiv b^k$$ (mod $$n$$), then since we are also assuming that $$a \equiv b$$ (mod $$n$$), we can use Part (2) of Theorem 3 to conclude that $$a \cdot a^k \equiv b \cdot b^k$$ (mod $$n$$).

14. Three consecutive natural numbers maybe represent by $$n$$, $$n + 1$$, and $$n + 2$$, where $$n$$ is a natural number. For the inductive step, think before you try to do a lot of algebra. You should be able to complete a proof of the inductive step by expanding the cube of only one expression.

Section 4.2

1. (a) If $$P(k)$$ is true, then $$3^k > 1 + 2^k$$. Multiplying both sides of this inequality by 3 gives

$$3^{k + 1} > 3 + 3 \cdot 2^k$$

Now, since $$3 > 1$$ and $$3 \cdot 2^k > 2^{k + 1}$$, we see that $$3 + 3 \cdot 2^k > 1 + 2^{k + 1}$$ and hence, $$3^{k + 1} > 1 + 2^{k + 1}$$. Thus, if $$P(k)$$ is ture, then $$P(k + 1)$$ is true.

2. If $$n \ge 5$$, then $$n^2 < 2^n$$. For the inductive step, we assume that $$k^2 < 2^k$$ and that $$k \ge 5$$. With these assumptions, prove that

$$(k + 1)^2 = k^2 + 2k + 1 < 2^{k} + 2k + 1.$$

Now use the assumption that $$k > 4$$ to prove that $$2k + 1 < k^2$$ and combine this with the assumption that $$k^2 < 2^k$$.

5. Let $$P(n)$$ be the predicate, "$$8^n\ |\ (4n)!$$." Verify that $$P(0)$$, $$P(1)$$, $$P(2)$$, and $$P(3)$$ are true. For the inductive step, the following fact about factorials may be useful:

$$\begin{array} {rcl} {[4(k + 1)]!} &= & {(4k + 4)!} \\ {} &= & {(4k + 4)(4k + 3)(4k + 2)(4k + 1)(4k)!.} \end{array}$$

8. Let $$P(n)$$ be, "The natural number $$n$$ can be written as a sum of natural numbers, each of which is a 2 or a 3.” Verify that $$P(4)$$, $$P(5)$$, $$P(6)$$, and $$P(7)$$ are true.

To use the Second Principle of Mathematical Induction, assume that $$k \in \mathbb{N}$$, $$k \ge 5$$ and that $$P(4)$$, $$P(5)$$, ... $$P(k)$$ are true. Then notice that

$$k + 1 = (k - 1) + 2.$$

Since $$k - 1 \le 4$$, we have assume that $$P(k - 1)$$ is true. Use this to complete the inductive step.

12. Let $$P(n)$$ be, “Any set with $$n$$ elements has $$\dfrac{n(n - 1)}{2}$$ 2-element subsets.” $$P(1)$$ is true since any set with only one element has no 2-element subsets. Let $$k \in \mathbb{N}$$ and assume that $$P(k)$$ is true. This means that any set with $$k$$ elements has $$\dfrac{k(k - 1)}{2}$$ 2-element subsets. Let $$A$$ be a set with $$k + 1$$ elements, and let $$x \in A$$. Now use the inductive hypothesis on the set $$A - \{x\}$$, and determine how the 2-element subsets of $$A$$ are related to the set $$A - \{x\}$$.

16. (a) Use Theorem 4.9
(b) Assume $$k \ne q$$ and consider two cases: (i) $$k < q$$; (ii) $$k > q$$.

Section 4.3

1. For the inductive step, if $$a_k = k!$$, then

$$\begin{array} {rcl} {a_{k + 1}} &= & {(k + 1)a_{k}} \\ {} &= & {(k + 1)k!} \\ {} &= & {(k + 1)!.} \end{array}$$

2. (a) Let $$P(n)$$ be, " $$f_{4n}$$ is a multiple of 3." Since $$f_4 = 3$$, $$P(1)$$ is true. If $$P(k)$$ is true, then there exists an integer $$m$$ such that $$f_{4k} = 3m$$. Use the following:

$$\begin{array} {rcl} {f_{4(k + 1)}} &= & {f_{4k + 4}} \\ {} &= & {f_{4k + 3} + f_{4k + 2}} \\ {} &= & {(f_{4k + 2} + f_{4k + 1}) + (f_{4k + 1} + f_{4k})} \\ {} &= & {f_{4k + 2} + 2f_{4k + 1} + f_{4k}} \\ {} &= & {(f_{4k + 1} + f_{4k}) + 2f_{4k + 1} + f_{4k}.} \end{array}$$

(c) Let $$P(n)$$ be, "$$f_1 + f_2 + \cdot\cdot\cdot + f_{n - 1} = f_{n + 1} - 1$$." Since $$f_1 = f_3 - 1$$, $$P(2)$$ is true. For $$k \ge 2$$, if $$k \ge 2$$, if $$P(k)$$ is true, then $$f_1 + f_2 + \cdot\cdot\cdot + f_{k - 1} = f_{k + 1} - 1$$. Then

$$\begin{array} {rcl} {f_1 + f_2 + \cdot\cdot\cdot + f_{k - 1}) + f_{k}} &= & {(f_{k + 1} - 1) + f_{k}} \\ {} &= & {(f_{k + 1} + f_{k}) - 1} \\ {} &= & {f_{k + 2} - 1.} \end{array}$$

This proves that if $$P(k)$$ is true, then $$P(k + 1)$$ is true.

(f) Let $$P(n)$$ be, "$$f_{1}^{2} + f_{2}^{2} + \cdot\cdot\cdot + f_{n}^{2} = f_{n}f_{n + 1}$$." For the inductive step, use

$$\begin{array} {rcl} {(f_{1}^{2} + f_{2}^{2} + \cdot\cdot\cdot + f_{k}^{2}) + f_{k + 1}^2} &= & {f_{k}f_{k + 1} + f_{k + 1}^{2}} \\ {f_{1}^{2} + f_{2}^{2} + \cdot\cdot\cdot + f_{k}^{2} + f_{k + 1}^2} &= & {f_{k + 1}(f_{k} + f_{k + 1})} \\ {} &= & {f_{k + 1}f_{k + 2}.} \end{array}$$

6. For the inductive step, if $$a_k = a \cdot r^{k - 1}$$, then

$$\begin{array}{rcl} {a_{k + 1}} &= & {r \cdot a_{k}} \\ {} &= & {r(a \cdot r^{k - 1})} \\ {} &= & {a \cdot r^{k}.} \end{array}$$

8. For the inductive step, use the assumption that $$S_{k} = a(\dfrac{1 - r^{k}{1 - r})$$ and the recursive definition to write $$S_{k + 1} = a + r \cdot S_{k}$$.

9. (a) $$a_2 = 7$$, $$a_3 = 12$$, $$a_4 = 17$$, $$a_5 = 22$$, $$a_6 = 27$$.
(b) One possibility is: For each $$n \in \mathbb{N}$$, $$a_n = 2 + 5(n - 1)$$.

12. (a) $$a_2 = \sqrt{6}$$, $$a_3 = \sqrt{\sqrt{6} + 5} \thickapprox 2.729$$, $$a_4 \thickapprox 2.780$$, $$a_5 \thickapprox 2.789$$, $$a_6 \thickapprox 2.791$$
(b) Let $$P(n)$$ be, "$$a_n < 3$$." Since $$a_1 = 1$$, $$P(1)$$ is true. For $$k \in \mathbb{N}$$, if $$P(k)$$ is true, then $$a_{k} < 3$$. Now

$$a_{k + 1} = \sqrt{5 + a_k}.$$

Since $$a_{k} < 3$$, this implies that $$a_{k + 1} < \sqrt{8}$$ and hence, $$a_{k + 1} < 3$$. This proves that if $$P(k)$$ is true, then $$P(k + 1)$$ is true.

13. (a) $$a_3 = 7$$, $$a_4 = 15$$, $$a_5 =31$$, $$a_6 = 63$$
(b) Think in terms of powers of 2.

14. (a) $$a_3 = \dfrac{3}{2}$$, $$a_4 = \dfrac{7}{4}$$, $$a_5 = \dfrac{37}{24}$$, $$a_6 = \dfrac{451}{336}$$

16. (b) $$a_2 = 5$$ $$a_2 = 719$$ $$a_8 = 362879$$
$$a_3 = 23$$ $$a_2 = 5039$$ $$a_9 = 3628799$$
$$a_4 = 119$$ $$a_2 = 40319$$ $$a_{10} = 39916799$$

18. (a) Let $$P(n)$$ be, "$$L_{n} = 2f_{n + 1} - f_{n}$$." First, verify that $$P(1)$$ and $$P(2)$$ are true. Now let $$k$$ be a natural number with $$k \ge 2$$ and assume that $$P(1)$$, $$P(2)$$, ..., $$P(k)$$ are all true. Since $$P(k)$$ and $$P(k - 1)$$ are both assumed to be true, we can use them to help prove that $$P(k + 1)$$ must then be true as follows:

$$\begin{array} {rcl} {L_{k + 1}} &= & {L_{k} + L_{k - 1}} \\ {} &= & {(2f_{k + 1} - f_{k}) + (2f_{k} - f_{k - 1})} \\ {} &= & {2(f_{k + 1} + f_{k}) - (f_{k} + f_{k - 1}} \\ {} &= & {2f_{k + 2} - f_{k + 1}.} \end{array}$$

(b) Let $$P(n)$$ be, "$$5f_{n} = L_{n - 1} + L_{n + 1}$$." First, verify that $$P(2)$$ and $$P(3)$$ are true. Now let $$k$$ be a natural number with $$k \ge 3$$ and assume that $$P(2)$$, $$P(3)$$, ..., $$P(k)$$ are all true. Since $$P(k)$$ and $$P(k - 1)$$ are both assumed to be true, we can use them to help prove that $$P(k + 1)$$ must then be true as follows:

$$\begin{array} {rcl} {5f_{k + 1}} &= & {5f_{k} + 5_{k - 1}} \\ {} &= & {(L_{k - 1} + L_{k + 1}) + (L_{k - 2} + L{k})} \\ {} &= & {(L_{k - 1} + L_{k - 2}) - (L_{k} + L_{k + 1})} \\ {} &= & {L_{k} + L_{k + 2}.} \end{array}$$.

Section 5.1

1. (a) $$A = B$$ (c) $$C \ne D$$ (e) $$A \not\subseteq D$$
(b) $$A \subseteq B$$ (d) $$C \subseteq D$$

2. In both cases, the two sets have preceisely the same elements.

3.
$$\begin{array} {rclrcl} {A} &\subset, \subseteq, \ne & {B} {\emptyset} &\subset, \subseteq, \ne & {A} \\ {5} &\in & {C} {\{5\}} &\subset, \subseteq, \ne & {C} \\ {|A|} &= & {|D|} {A} &\in & {\mathcal{P}(b)} \end{array}$$
5. (a) The set $$\{a, b\}$$ is a not a subset of $$\{a, c, d, e\}$$ since $$b \in \{a, b\}$$ and $$b \in \{a, c, d, e\}$$.

7. (c) $$(A \cup B)^{c} = \{2, 8, 10\}$$ (h) $$(A \cap C) \cup (B \cap C) = \{3, 6, 9\}$$
(d) $$A^{c} \cap B^{c} = \{2, 8, 10\}$$ (n) $$(A \cup B) - D = \{1, 3, 5, 7, 9\}$$
(e) $$(A \cup B) \cap C = \{3, 6, 9\}$$

9. (b) There exists an $$x \in U$$ such that $$x \in (P - Q)$$ and $$x \notin (R \cap S)$$. This can be written as, There exists an $$x \in U$$ such that $$x \in P$$, $$x \notin Q$$, and $$x \notin R$$ or $$x \notin S$$.

10. (a) The given statement is a conditional statement. We can rewrite the subset relations in terms of conditional sentences: $$A \subseteq B$$ means, "For all $$x \in U$$, if $$x \in A$$, then $$x \in B$$," and $$B^{c} \subseteq A^{c}$$ means, "For all $$x \in U$$, if $$x \in B^{c}$$, then $$x \in A^{c}$$."

Section 5.2

1. (a) The set $$A$$ is a subset of $$B$$. A proof is required. The idea is that if $$x \in A$$, then $$-2 < x < 2$$. Since $$x < 2$$, we conclude that $$x \in B$$.
(b) The set $$B$$ is not a subset of $$A$$. Give an example of a real number that is in $$B$$ but not in $$A$$.

3. (b) $$A \subseteq B$$ $$B \not\subseteq A$$

7. (a) Start by letting $$x$$ be an element of $$A \cap B$$.
(b) Start by letting $$x$$ be an element of $$A$$.
(e) By Theorem 5.1, $$\emptyset \subseteq A \cap \emptyset$$. By Part (a), $$A \cap \emptyset \subseteq \emptyset$$. Therefore, $$A \cap \emptyset = \emptyset$$.

12. (a) Let $$x \in A \cap C$$. Then $$x \in A$$ and $$x \in C$$. Since we are assuming that $$A \subseteq B$$, we see that $$x \in B$$ and $$x \in C$$. This proves that $$A \cap C \subseteq B \cap C$$.

15. (a) "If $$A \subseteq B$$, then $$A \cap B^{c} = \emptyset$$" is Proposition 5.14. To prove the other conditional statement, start with, "Let $$x \in A$$." Then use the assumption that $$A \cap B^{c} = \emptyset$$ to prove that $$x$$ must be in $$B$$.
(b) To prove "If $$A subseteq B$$, then $$A \cup B = B$$," first note that if $$x \in B$$, then $$x \in A \cup B$$ and, hence, $$B \subseteq A \cup B$$. Now let $$x \in A \cup B$$ and note that since $$A \subseteq B$$, if $$x \in A$$, then $$x \in B$$. Use this to argue that under the assumption that $$A \subseteq B$$, $$A \cup B \subseteq B$$.

Tp prove "If $$A \cup B = B$$, then $$A \subseteq B$$," start with, Let $$x \in A$$ and use this asusmption to prove that $$x$$ must be an element of $$B$$.

Section 5.3

1. (a) Let $$x \in (A^{c})^{c}$$. Then $$x \notin A^{c}$$, which means $$x \in A$$. Hence, $$(A^{c})^{c} \subseteq A$$. Now prove that $$A \subseteq (A^{c})^{c}$$.
(c) Let $$x \in U$$. Then $$x \notin \emptyset$$ and so $$x \in \emptyset^{c}$$. Therefore, $$U \subseteq \emptyset^{c}$$. Also, since every set we deal with is a subset of the universal set, $$\emptyset^{c} \subseteq U$$.

2. We will first prove that $$A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$$. Let $$x \in A \cap (B \cup C)$$. Then $$x \in A$$ and $$x \in B \cup C$$. So we will use two cases: (1) $$x \in B$$; (2) $$x \in C$$. In Case (1), $$x \in A \cap B$$ and, hence $$x \in (A \cap B) \cup (A \cap C)$$. In Case (2), $$x \in A \cap C$$ and, hence, $$x \in (A \cap B) \cup (A \cap C)$$. This proves that $$A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$$.

Now prove that $$(A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C)$$.

4. (a) $$A - (B \cup C) = (A - B) \cap (A - C)$$.
(c) Using the algebra of sets, we obtain

$$\begin{array} {rcl} {(A - B) \cap (A - C)} &= & {(A \cap B^{c}) \cap (A \cap C^{c})} \\ {} &= & {(A \cap A) \cap (B^{c} \cap C^{c})} \\ {} &= & {A \cap (B \cup C)^{c}} \\ {} &= & {A - (B \cup C).} \end{array}$$

9. (a) Use a proof by contradiction. Assume the sets are not disjoint and let $$x \in A \cap (B - A)$$. Then $$x \in A$$ and $$x \in B - A$$, which implies that $$x \notin A$$.

Section 5.4

1, (a) $$A \times B = \{(1, a), (1, b), (1, c), (1, d), (2, a), (2, b), (2, c), (2, d)\}$$
(b) $$B \times A = \{(a, 1), (b, 1), (c, 1), (d, 1), (a, 2), (b, 2), (c, 2), (d, 2)\}$$
(c) $$A \times (B \cap C) = \{(1, a), (1, b), (2, a), (2, b)\}$$

3. Start of proof that $$A \times (B \cap C) \subseteq (A \times B) \cap (A \times C)$$:
Let $$u \in A \times (B \cap C)$$. Then there exists $$x \in A$$ and there exists $$y \in B \cap C$$ such that $$u = (x, y)$$. Since $$y \in B \cap C$$, we know that $$y \in B$$ and $$y \in C$$. So we have

$$u = (x, y)$$, where $$x \in A$$ and $$y \in B$$. This means that $$u \in A \times B$$.
$$u = (x, y)$$, where $$x \in A$$ and $$y \in C$$. This means that $$u \in A \times C$$.

4. Start of proof that $$(A \cup B) \times C \subseteq (A \times C) \cup (B \times C)$$:

let $$u \in (A \cup B) \times C$$. Then there exists $$x \in A \cup B$$ and there exists $$y \in C$$ such that $$u = (x, y)$$. Since $$x \in A \cup B$$, we know that $$x \in A$$ or $$x \in B$$.

Section 5.5

1. (a) {3, 4}
(d) {3, 4, 5, 6, 7, 8, 9, 10}

2. (a) {5, 6, 7, ...}
(c) $$\emptyset$$
(d) {1, 2, 3, 4}
(f) $$\emptyset$$

3. (a) $$\{x \in \mathbb{R}\ |\ -100 \le x \le 100\}$$
(b) $$\{x \in \mathbb{R}\ |\ -1 \le x \le 1\}$$

4. (a) We let $$\beta \in \Lambda$$ and let $$x \in A_{\beta}$$. Then $$x \in A_{\alpha}$$, for at lest one $$\alpha \in \Lambda$$ and, hence, $$x \in \bigcup_{\alpha \in \Lambda} A_{\alpha}$$. This proves that $$A_{\beta} \subseteq \bigcup_{\alpha \in \Lambda} A_{\alpha}$$.

5. (a) We first let $$x \in B \cap (\bigcup_{\alpha \in \Lambda} A_{\alpha})$$. Then $$x \in B$$ and $$x \in \bigcup_{\alpha \in \Lambda} A_{\alpha}$$. This means that there exists an $$\alpha \in \Lambda$$ such that $$x \in A_{\alpha}$$. Hence, $$x \in B \cap A_{\alpha}$$, which implies that $$x \in \bigcup_{\alpha \in \Lambda} (B \cap A_{\alpha})$$. This prove that $$B \cap (\bigcup_{\alpha \in \Lambda} A_{\alpha}) \subseteq \bigcup_{\alpha \in \Lambda} (B \cap A_{\alpha})$$, and we still need to prove that $$\bigcup_{\alpha \in \Lambda} (B \cap A_{\alpha}) \subseteq B \cap (\bigcup_{\alpha \in \Lambda} A_{\alpha})$$.

8. (a) Let $$x \in B$$. For each $$\alpha \in \Lambda$$, $$B \subseteq A_{\alpha}$$ and, hence, $$x \in A_{\alpha}$$. This means that for each $$\alpha \in \Lambda$$, $$x \in A_{\alpha}$$ and, hence, $$x \in \bigcap_{\alpha \in \Lambda} A_{\alpha}$$. Therefore, $$B \subseteq \bigcap_{\alpha \in \Lambda} A_{\alpha}$$

12. (a) We first rewrite the set difference and then use a distributive law.

$$\begin{array} {rcl} {(\bigcup_{\alpha \in \Lambda} A_{\alpha}) - B} &= & {(\bigcup_{\alpha \in \Lambda} A_{\alpha}) \cap B^{c}} \\ {} &= & {\bigcup_{\alpha \in \Lambda} (A_{\alpha} \cap B^{c})} \\ {} &= & {\bigcup_{\alpha \in \Lambda} (A_{\alpha} - B)} \end{array}$$

Section 6.1

1. (a) $$f(-3) = 15$$, $$f(-1) = 3$$, $$f(1) = -1$$, $$f(3) = 3$$.
(b) The set of preimages of 0 is {0, 2}. The set of preimages of 4 is {$$\dfrac{2 - \sqrt{20}}{2}, \dfrac{2 + \sqrt{20}}{2}$$}. (Use the quadratic formula.)
(d) range$$(f) = \{y \in \mathbb{R}\ |\ y \ge -1\}$$.

4. (b) The set of preimages of 5 is {2}. There set of preimages of 4 is $$\emptyset$$.
(c) The range of the function $$f$$ is the set of all odd integers.
(d) The graph of the function $$f$$ consists of an infinite set of discrete points.

5. (b) dom$$(F) = \{x \in \mathbb{R}\ |\ x > \dfrac{1}{2}\}$$, range$$(F) = \mathbb{R}$$
(d) dom$$(g) = \{x \in \mathbb{R}\ |\ x \ne 2 \text{ and } x \ne -2\}$$,
range$$(g) = \{y \in \mathbb{R}\ |\ y > 0\} \cup \{y \in \mathbb{R}\ |\ y \le -1\}$$

6. (a) $$d(1) = 1$$, $$d(2) = 2$$, $$d(3) = 2$$, $$d(4) = 3$$, $$d(8) = 4$$, $$d(9) = 3$$
(c) The only natural numbers $$n$$ such that $$d(n) = 2$$ are the prime numbers. The set of preimages of the natural number 2 is the set of prime numbers.
(e) $$d(2^{0}) = 1$$, $$d(2^{1}) = 2$$, $$d(2^{2}) = 3$$, $$d(2^{3}) = 4$$
(f) The divisors of $$2^{n}$$ are $$2^{0}$$, $$2^{1}$$, $$2^{2}$$, ..., $$2^{n - 1}$$, $$2^{n}$$.

7. (a) The domain of $$S$$ is $$\mathbb{N}$$. The power set of $$\mathbb{N}$$, $$[\mathcal{P}(\mathbb{N})]$$ can be the codomain. The rule for determining outputs is that for each $$n \in \mathbb{N}$$, $$S(n)$$ is the set of all distinct natural number factors of $$n$$.
(b) For example, $$S(8) = \{1, 2, 4, 8\}$$, $$S(15) = \{1, 3, 5, 15\}$$.
(c) For example, $$S(2) = \{1, 2\}$$, $$S(3) = \{1, 3\}$$, $$S(31) = \{1, 31\}$$.

Section 6.2

1. (a) $$f(0) = 4$$, $$f(1) = 0$$, $$f(2) = 3$$, $$f(3) = 3$$, $$f(4) = 0$$
(b) $$g(0) = 4$$, $$g(1) = 0$$, $$g(2) = 3$$, $$g(3) = 3$$, $$g(4) = 0$$
(c) The two functions are equal.

2. (c) The two functions are not equal. For example, $$f(1) = 5$$ and $$g(1) = 4$$.

4. (a) $$\langle a_{n} \rangle$$, where $$a_{n} = \text{cos}(n \pi)$$ for each $$n \in \mathbb{N}$$. The domain is $$\mathbb{N}$$, and {-1, 1} can be the codomain. This sequence is equal to the sequence in Part (c).

5. (a) $$p_{1} (1, x) = 1$$, $$p_{1} (1, y) = 1$$, $$p_{1} (1, z) = 1$$, $$p_{1} (2, x) = 2$$, $$p_{1} (2, y) = 2$$, $$p_{1} (2, z) = 2$$
(c) range$$(p_1) = A$$, range$$(p_2) = B$$

6. Start of the inductive step: Let $$P(n)$$ be “A convex polygon with $$n$$ sides has $$\dfrac{n(n - 3)}{2}$$ diagonals.” Let $$k \in D$$ and assume that $$P(k)$$ is true, that is, a convex polygon with $$k$$ sides has $$\dfrac{k(k - 3)}{2}$$ diagonals. Now let $$Q$$ be convex polygon with $$(k + 1)$$ sides. Let v be one of the $$(k + 1)$$ vertices of $$Q$$ and let $$u$$ and $$w$$ be the two vertices adjacent to $$v$$. By drawing the line segment from $$u$$ to $$w$$ and omitting the vertex v, we form a convex polygon with $$k$$ sides. Now complete the inductive step.

7. (a) $$f(-3, 4) = 9$$, $$f(-2, -7) = -23$$
(b) $$\{(m, n) \in \mathbb{Z} \times \mathbb{Z}\ |\ m = 4 - 3n\}$$

9. (a) det$$\left [{\begin{array} {cc} 3 & 5 \\ 4 & 1\\ \end{array}} \right]$$ = -17, det$$\left [{\begin{array} {cc} 1 & 0 \\ 0 & 7\\ \end{array}} \right]$$ = 7, and det$$\left [{\begin{array} {cc} 3 & -2 \\ 5 & 0\\ \end{array}} \right]$$ = 10.

Section 6.3

2. (a) The function $$f$$ is not an injection and is not a surjection.
(c) The function $$F$$ is an injection and is a surjection.

3. (a) The function $$f$$ is an injection and is not a surjection.
(b) The function $$F$$ is an injection and is a surjection.

4. (a) Let $$F: \mathbb{R} \to \mathbb{R}$$ be defined by $$F(x) = 5x + 3$$ for all $$x \in \mathbb{R}$$. Let $$x_1, x_2 \in \mathbb{R}$$ and assume that $$F(x_1) = F(x_2)$$. Then $$5x_1 + 3 = 5x_2 + 3$$. Show that this implies that $$x_1 = x_2$$ and, hence, $$F$$ is an injection.
Now let $$y \in \mathbb{R}$$. Then $$\dfrac{y - 3}{5} \in \mathbb{R}$$. Prove that $$F(\dfrac{y - 3}{5}) = y$$. Thus, $$F$$ is a sujection and hence $$F$$ is a bijection.
(b) Notice that for each $$x \in \mathbb{Z}$$, $$G(x) \equiv 3$$ (mod 5). Now explain why $$G$$ is not a surjection.

7. The birthday function is not an injection since there are two different people with the same birthday. The birthday function is a surjection since for each day of the year, there is a person that was born on that day.

9. (a) The function $$f$$ is an injection and a surjection.
(b) The function $$g$$ is an injection and is not a surjection.

Section 6.4

3. (a) $$F(x) = (g \circ f) (x)$$, $$f(x) = e^{x}$$, $$g(x) = \text{cos} x$$
(b) $$G(x) = (g \circ f) (x)$$, $$f(x) = \text{cos} x$$, $$g(x) = e^{x}$$

4. (a) For each $$x \in A$$. $$(f \circ I_{A}) (x) = f(I_{A}(x)) = f(x)$$. Therefore, $$f \circ I_{A} = f$$.

5. (a) $$[(h \circ g) \circ f] (x) = \sqrt[3]{\text{sin}(x^2)}$$; $$[h \circ (g \circ f)](x) \sqrt[3]{\text{sin}(x^2)}$$

6. Start of a proof: Let $$A$$, $$B$$, and $$C$$ be nonempty sets and let $$f: A \to B$$ and $$g: B \to C$$. Assume that $$f$$ and $$g$$ are both injections. Let $$x, y \in A$$ and assume that $$(g \circ f)(x) = (g \circ f)(y)$$.

7. (a) $$f: \mathbb{R} \to \mathbb{R}$$ by $$f(x) = x$$, $$g: \mathbb{R} \to \mathbb{R}$$ by $$g(x) = x^2$$. The function $$f$$ is a surjection, but $$g \circ f$$ is not a surjection.
(f) By Part (1) of Theorem 6.21, this is not possible since if $$g \circ f$$ is an injection, then $$f$$ is an injection.

Section 6.5

2. (b) $$f^{-1} = \{(c, a), (b, b), (d, c), (a, d)\}$$
(d) $$(f^{-1} \circ f) (x) = x = (f \circ f^{-1}) (x)$$. This illustrates Corollary 6.28.

4. Using the notation from Corollary 6.28, if $$y = f(x)$$ and $$x = f^{-1}(y)$$, then

$$\begin{array} {rcl} {(f \circ f^{-1} (y)} &= & {f(f^{-1} (y))} \\ {} &= & {f(x)} \\ {} &= & {y} \end{array}$$

6. (a) Let $$x, y \in A$$ and assume that $$f(x) = f(y)$$. Apply $$g$$ to both sides of this equation to prove that $$(g \circ f)(x) = (g \circ f)(y)$$. Since $$g \circ f = I_{A}$$, this impliies that $$x = y$$ and hence that $$f$$ is an injection.
(b) Start by assuming that $$f \circ g = I_{B}$$, and then let $$y \in B$$. You need to prove there exists an $$x \in A$$ such that $$f(x) = y$$.
(d) $$g: \mathbb{R}^{+} \to \mathbb{R}$$ by $$g(y) = \dfrac{1}{2}(\text{In} y + 1)$$

7. The inverse of $$f$$ is not a function and the inverse of $$g$$ is a function.

Section 6.6

1. (a) There exists an $$x \in A \cap B$$ such that $$f(x) = y$$.
(d) There exists an $$a \in A$$ such that $$f(a) = y$$ or there exists a $$b \in B$$ such that $$f(b) = y$$.
(f) $$f(x) \in C \cup D$$
(h) $$f(x) \in C$$ or $$f(x) \in D$$.

2. (b) $$f^{-1} (f(A)) = [2, 5]$$.
(e) $$f(A \cap B) = [-5, -3]$$
(d) $$f(f^{-1}(C)) = [-2, 3]$$
(f) $$f(A) \cap f(B) = [-5, -3]$$

3. (a) $$g(A \times A) = \{6, 12, 18, 24, 36, 54, 72, 108, 216\}$$
(b) $$g^{-1} (C) = \{(1, 1), (2, 1), (1, 2)\}$$

4. (a) range$$(F) = F(S) = \{1, 4, 9, 16\}$$

5. To prove $$f(A \cup B) \subseteq f(A) \cup f(B)$$, start by letting $$y \in f(A \cup B)$$. This means that there exists an $$x$$ in $$A \cup B$$ such that $$f(x) = y$$. How do you prove that $$y \in f(A) \cup f(B)$$?

6. To prove that $$f^{-1} (C \cap D) \subseteq f^{-1}(C) \cap f^{-1}(D)$$, let $$x \in f^{-1} (C \cap D)$$. Then $$f(x) \in C \cap D$$. How do you prove that $$x \in f^{-1}(C) \cap f^{-1}(D)$$?

9. Statement (a) is true and Statement (b) is false.

Section 7.1

1. (a) The set $$A \times B$$ contains nine ordered pairs. The set $$A \times B$$ is a relation from $$A$$ to $$B$$ since $$A \times B$$ is a subset of $$A \times B$$.
(b) The set $$R$$ is a relation from $$A$$ to $$B$$ since $$R \subseteq A \times B$$.
(c) dom$$(R) = A$$, range$$(R) = \{p, q\}$$
(d) $$R^{-1} = \{(p, a), (q, b), (p, c), (q, a)\}$$

2. Only the statement in Part (b) is true.

3. (a) The domain of $$D$$ consists of the female citizens of the United States whose mother is a female citizen of the United States.
(b) The range of $$D$$ consists of those female citizens of the United States who have a daughter that is a female citizen of the United States.

4. (a) $$(S, T) \in R$$ means that $$S \subseteq T$$.
(b) The domain of the subset relation is $$\mathcal{P}(U)$$.
(c) The range of the subsetr elation is $$\mathcal{P}(U)$$.
(d) $$R^{-1} = \{(T, S) \in \mathcal{P}(U) \times \mathcal{P}(U)\ |\ S \subseteq T\}$$.
(e) The relation $$R$$ is not a function from $$\mathcal{P}(U)$$ to $$\mathcal{P}(U)$$ since any proper subset of $$U$$ is a subset of more than one subset of $$U$$.

6. (a) $$\{x \in \mathbb{R}\ |\ (x, 6) \in S\} = \{-8, 8\}$$
$$\{x \in \mathbb{R}\ |\ (x, 9) \in S\} = \{-\sqrt{19}, \sqrt{19}\}$$
(b) The domain and range of $$S$$ is the closed interval [-10, 10].
(d) The relation $$S$$ is not a function from $$\mathbb{R}$$ to $$\mathbb{R}$$.

9. (a) $$R = \{(a, b) \in \mathbb{Z} \times \mathbb{Z}\ |\ |a - b| \le 2\}$$
(b) dom$$(R) = \mathbb{Z}$$ and range$$(R) = \mathbb{Z}$$

Section 7.2

1. The relation $$R$$ is not reflexive on $$A$$ and is not symmetric. However, it is transitive since the conditional statement "For all $$x, y, z \in A$$, if $$x\ R\ y$$ and $$y\ R\ z$$, then $$x\ R\ z$$" is a true conditional statement.

4. The relation $$R$$ is not reflexive on $$A$$, is symmetric, and is not transitive.

6. (a) The relation $$\sim$$ is an equivalence relation.
(b) $$C = \{-5, 5\}$$

10. The relation $$\sim$$ is an equivalence relation and the relation $$\thickapprox$$ is not an equivalence relation.

15. (c) The set $$C$$ is a circle of radius 5 with center at the origin.

Section 7.3

1. $$[a] = [b] = \{a, b\}$$; $$[c] = \{c\}$$; $$[d] = [e] = \{d, e\}$$

2. $$[a] = [b] = [d] = \{a, b, d\}$$; $$[c] = \{c\}$$; $$[e] = [f] = \{e, f\}$$

3. The equivalence classes are {0, 1, 2, ..., 9}, {10, 11, 12, ..., 99}, {100, 101, 102, ..., 999}, {1000}.

4. The congruence classes for the relation of congruence modulo 5 on the set of integers are

$$[0] = \{5n\ |\ n \in \mathbb{Z}$$ $$[3] = \{5n + 3\ |\ n \in \mathbb{Z}$$
$$[1] = \{5n + 1\ |\ n \in \mathbb{Z}$$
$$[2] = \{5n + 2\ |\ n \in \mathbb{Z}$$ $$[4] = \{5n + 4\ |\ n \in \mathbb{Z}$$

5. (a) The distinct equivalence classes are {0, 3, 6}, {1, 8}, {2, 7}, and {4, 5}.

6. (a) Let $$x \in [\dfrac{5}{7}]$$. Then $$x - \dfrac{5}{7} \in \mathbb{Z}$$, which means that there is an integer $$m$$ such that $$x - \dfrac{5}{7} = m$$, or $$x = \dfrac{5}{7} + m$$. This proves that $$x \in \{m + \dfrac{5}{7}\ |\ m \in \mathbb{Z}\}$$ and, hence, that $$[\dfrac{5}{7}] \subseteq \{m + \dfrac{5}{7}\ |\ m \in \mathbb{Z}\}$$. We still need to prove that $$\{m + \dfrac{5}{7}\ |\ m \in \mathbb{Z}\} \subseteq [\dfrac{5}{7}]$$

9. (a) To prove the relation is symmetric, note that if $$(a, b) \thickapprox (c, d)$$, then $$ad = bc$$. This implies that $$cb = da$$ and, hence, $$(c, d) \thickapprox (a, b)$$
(c) $$3a = 2b$$

Section 7.4

1. (a)
(b)

2. (a) $$[x] = [1]$$ or $$[x] = [3]$$
(e) $$[x] = [2]$$ or $$[x] = [3]$$
(g) The equation has no solution.

3. The statement in (a) is false. The statement in (b) is true.

5. (a) The proof consists of the following computations:

$$\begin{array} {lcl} {[1]^1 = [1]} & & {[3]^1 = [9] = [4]} \\ {[2]^1 = [4]} & & {[4]^1 = [16] = [1].} \end{array}$$

17. (a) Prove the contrapostive by calculating $$[a]^2 + [b]^2$$ for all nonzero $$[a]$$ and $$[b]$$ in $$\mathbb{Z}_3$$.

Section 8.1

1. (a) gcd(21, 28) = 7
(b) gcd(-21, 28) = 7
(c) gcd(58, 63) = 1
(d) gcd(0, 12) = 12

2. (a) Hint: Prove that $$k\ |\ [(a + 1) - a]$$.

4. (a) $$|b|$$ is the largest natural number that divides 0 and $$b$$.
(b) The integers $$b$$ and $$-b$$ have the same divisors. Therefore, $$\text{gcd}(a, -b) = \text{gcd}(a, b)$$.

5. (a) gcd(36, 60) = 12 $$12 = 36 \cdot 2 + 60 \cdot (-1)$$
(a) gcd(901, 935) = 17 $$17 = 901 \cdot 27 + 935 \cdot (-26)$$
(a) gcd(901, -935) = 17 $$17 = 901 \cdot 27 + (-935) \cdot (26)$$

7. (a) $$11 \cdot (-3) + 17 \cdot 2 = 1$$
(b) $$\dfrac{m}{11} + \dfrac{n}{17} = \dfrac{17m + 11n}{187}$$

Section 8.2

1. The only natural number divisors of a prime number $$p$$ are 1 and $$p$$.

2. Use cases: (1) $$p$$ divides $$a$$; (2) p does not divide $$a$$. In this case, use the fact that gcd($$a$$, $$p$$) = 1 to write the number 1 as a linear combination of $$a$$ and $$p$$.

3. A hint for the inductive step: Write $$p\ |\ (a_{1} a_{2} \cdot\cdot\cdot a_{m})a_{m + 1}$$. Then look at two cases: (1) $$p\ |\ a_{m + 1}$$; (2) $$p$$ does not divide $$a_{m + 1}$$.

4. (a) gcd($$a$$, $$b$$) = 1. Why?
(b) gcd($$a$$, $$b$$) = 1 or gcd($$a$$, $$b$$) = 1=2. Why?

7. (a) gcd(16, 28) = 4. Also, $$\dfrac{16}{4} = 4$$, $$\dfrac{28}{4} = 7$$, and gcd(4, 7) = 1.

9. Part (b) of Exercise (8) can be helpful.

11. The statement is true. Start of a proof: If gcd($$a$$, $$b$$) = 1 and $$c\ |\ (a + b)$$, then there exist integers $$x$$ and $$y$$ such that $$ax + by = 1$$ and there exists an integer m such that $$a + b = cm$$.

Section 8.3

3. (a) $$x = -3 + 14k, y = 2 - 9k$$
(b) $$x = -1 + 11k, y = 1 + 9k$$
(c) No solution
(d) $$x = 2 + 3k, y = -2 - 4k$$

4. There are several possible solutions to this problem, each of which can be generated from the solutions of the Diophantine equation $$27x + 50y = 25$$.

5. This problem can be solved by finding all solutions of a linear Diophantine equation in $$x$$ and $$y$$, where both $$x$$ and $$y$$ are positive. The minimum number of people attending the banquet is 66.

6. (a) $$y = 12 + 16k$$, $$x_3 = -1 - 3k$$
(c) $$x_1 = y + 3n$$, $$x_2 = -y + 4n$$

Section 9.1

2. Use $$f: A \times \{x\} \to A$$ by $$f(a, x) = a$$, for all $$(a, x) \in A \times \{x\}$$.

4. Notice that $$A = (A - \{x\}) \cup \{x\}$$. Use Theorem 9.6 to conclude that $$A - \{x\}$$ is finte. Then use Lemma 9.4.

5. (a) Since $$A \cap B \subseteq A$$, if $$A$$ is finite, then Theorem 9.6 implies that $$A \cap B$$ is finte.

7. (a) Remember that two ordered pairs are equal if and only if their corresponding coordinates are equal. So if $$h(a_1, c_1) = h(a_2, c_2)$$, then $$(f(a_1), g(c_1)) = (f(a_2), g(c_2))$$. We can then conclude that $$f(a_1) = f(a_2)$$ and $$g(c_1) = g(c_2)$$.

8. (a) If we define the function $$f$$ by $$f(1) = a$$, $$f(2) = b$$, $$f(3) = c$$, $$f(4) = a$$, and $$f(5) = b$$, then we can use $$g(a) = 1$$, $$g(b) = 1$$, and $$g(3) = c$$. The function $$g$$ is an injection.

Section 9.2

1. All except Part (d) are true.

2. (e) Either define an appropriate bijection or use Corollary 9.20 to conclude that $$\mathbb{N} - \{4, 5, 6\}$$ is countable. Prove that $$\mathbb{N} - \{4, 5, 6\}$$ cannot be finite.
(f) $$\{m \in \mathbb{Z}\ |\ m \equiv 2 \text{ (mod 3)}\} = \{3k + 2\ |\ k \in \mathbb{Z}\}$$

5. For each $$n \in \mathbb{N}$$, let $$P(n)$$ be "If card($$B$$) = $$n$$, then $$A \cup B$$ is a countably infinte set."

Note that if card$$(B) = k + 1$$ and $$x \in B$$, then card$$(B - \{x\}) = k$$. Apply the inductive assumption to $$B - \{x\}$$.

6. Notice that if $$h(n) = h(m)$$, then since $$A$$ and $$B$$ are disjoint, either $$h(n)$$ and $$h(m)$$ are both in $$A$$ or are both in $$B$$.

Also, if $$y \in A \cup B$$, then there are only two cases to consider: $$y \in A$$ or $$y \in B$$.

8. Since $$A - B \subseteq A$$, the set $$A - B$$ is countable. Now assume $$A - B$$ is finte and show that this leads to a contradiction.

Section 9.3

1. (a) $$f: (0, \infty) \to \mathbb{R}$$ by $$f(x) = \text{In} x$$ for all $$x \in (0, \infty)$$
(b) $$g: (0, \infty) \to (a, \infty)$$ by $$g(x) = x + a$$ for all $$x \in (0, \infty)$$. The function $$g$$ is a bijection and so $$(0, \infty) \thickapprox (a, \infty)$$. Then use Part (a).

2. Show that the assumption that the set of irrational numbers is countable leads to a contradiction.

3. Use Corollary 9.20.