Skip to main content
$$\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# Section 1:

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

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

# Solutions to Hands-On Exercises

### Section [sec:provingID]

1. Two proofs are given below, one uses direct expansion, the other uses factorization.

-6pt Expanding the two sides separately, we find \begin{aligned} \frac{k(k+1)(k+2)}{3} + (k+1)(k+2) &=& \frac{k^3+3k^2+2k}{3} + k^2+3k+2 \\ &=& \frac{k^3+3k^2+2k+3(k^2+3k+2)}{3} \\ &=& \frac{k^3+6k^2+11k+6}{3}, \end{aligned} and $\frac{(k+1)(k+2)(k+3)}{3} = \frac{(k^2+3k+2)(k+2)}{3} = \frac{k^3+6k^2+11k+6}{3},$ which establish the identity.

-6pt Since \begin{aligned} \frac{k(k+1)(k+2)}{3} + (k+1)(k+2) &=& (k+1)(k+2)\left(\frac{k}{3}+1\right) \\ [3pt] &=& \frac{(k+1)(k+2)(k+3)}{3}, \end{aligned} the identity always holds.

### Section [sec:prop]

1. Any example of the form

If then  . Therefore. if then .

will work.

2. (a) We do not know which “he” the sentence is referring to.

(b) We do not know the values of $$x$$ and $$y$$.

(c) While the equation is true if $$A$$ and $$B$$ are numbers, it is not always true if $$A$$ and $$B$$ are matrices.

3. (a) $$x$$ is an integer less than or equal to 7.

(b) We cannot factor 144 into a product of prime numbers.

(c) The number 64 is not a perfect square.

### Section [sec:conjdisj]

1. $$x$$ is rational and $$y$$ is rational; $$(x\in\Q) \wedge (y\in\Q)$$.

2. (a) Since “$$\sqrt{30}<5$$” is false, and “$$\sqrt{30}>7$$” is true, the statement “$$(\sqrt{30}<5) \wedge (\sqrt{30}>7)$$” is false.

(b) Since “$$\sqrt{30}>5$$” is true and “$$\sqrt{30}<7$$” is false, the statement “$$(\sqrt{30}>5) \vee (\sqrt{30}<7)$$” is true.

3. $$(5<x) \wedge (x<8)$$.

4. The statement “$$0\geq x\geq 1$$” means “$$(0\geq x) \wedge (x\geq1)$$.” Since no number can be less than or equal to 0 and greater than or equal to 1 simultaneously, the statement “$$(0\geq x) \wedge (x\geq1)$$” is always false.

### Section [sec:imply]

1. (a) one (b) two (c) none

2. $$x>y>0 \Rightarrow x^2>y^2$$.

3. (a) False, because we could have $$x=3$$, then “$$(x-2)(x-3)=0$$” is true but “$$x=2$$” is false. This makes the implication false.

(b) True, because if “$$x=2$$” is true, “$$(x-2)(x-3)=0$$” would be true as well. Thus, the implication is true.

4. (a)

 $$p$$: The figure $$PQRS$$ is a square, $$q$$: The figure $$PQRS$$ is a parallelogram.

(b)

 $$p$$: The number $$x$$ is a prime number, $$q$$: The number $$x$$ is an integer.

(c)

 $$p$$: The function $$f(x)$$ is a polynomial, $$q$$: The function $$f(x)$$ is differentiable.
5.  converse: if $$\sqrt{p}$$ is irrational, then $$p$$ is prime inverse: if $$p$$ is composite, then $$\sqrt{p}$$ is rational contrapositive: if $$\sqrt{p}$$ is rational, then $$p$$ is composite
6. (a) $$p:\; x>1$$; $$q:\; x^2>1$$.

(b) $$p:\; x^2>1$$; $$q:\; x>1$$.

### Section [sec:bicond]

1. The completed statement is “$$n$$ is odd $$\Leftrightarrow$$ $$n=2k+1$$ for some integer $$k$$.”

Proof: Assume $$n$$ is odd, then we can write $$n=2k+1$$ for some integer $$k$$. We find $n^2 = (2k+1)^2 = 4k^2+4k+1 = 2(2k^2+2k)+1,$ where $$2k^2+2k$$ is an integer. Hence, $$n^2$$ is also odd.

2. The statement “$$p\Rightarrow q\wedge r$$” means “$$p\Rightarrow (q\wedge r)$$.” Below is its truth table. $% \arraygap{1.125} \begin{array}{|*{5}{c|}} \hline p & q & r & q\wedge r & p\Rightarrow (p\wedge r) \\ \hline \T & \T & \T & \T & \T\qquad\; \\ \T & \T & \F & \F & \F\qquad\; \\ \T & \F & \T & \F & \F\qquad\; \\ \T & \F & \F & \F & \F\qquad\; \\ \F & \T & \T & \T & \T\qquad\; \\ \F & \T & \F & \F & \T\qquad\; \\ \F & \F & \T & \F & \T\qquad\; \\ \F & \F & \F & \F & \T\qquad\; \\ \hline \end{array}$

3. We can write “$$(p\wedge q) \Leftrightarrow (\overline{p}\vee \overline{q})$$.” To construct its truth table, we need to evaluate each component one at a time: $% \arraygap{1.125} \begin{array}{|*{7}{c|}} \hline p & q & p\wedge q & \overline{p} & \overline{q} & \overline{p}\vee\overline{q} & (p\wedge q) \Leftrightarrow (\overline{p}\vee\overline{q}) \\ \hline \T & \T & \T & \F & \F & \F & \F \\ \T & \F & \F & \F & \T & \T & \F \\ \F & \T & \F & \T & \F & \T & \F \\ \F & \F & \F & \T & \T & \T & \F \\ \hline \end{array}$

### Section [sec:logiceq]

1. In general, if we have $$n$$ statements, we need $$2^n$$ rows in the truth table. $% \arraygap{1.125} \begin{array}{|*{11}{c|}} \hline p & q & r & p\wedge q & (p\wedge q)\Rightarrow r & \overline{r} & \overline{p} & \overline{q} & \overline{p}\vee\overline{q} & \overline{r} \Rightarrow (\overline{p}\vee\overline{q}) & [(p \wedge q) \Rightarrow r] \Rightarrow [\overline{r}\Rightarrow(\overline{p} \vee \overline{q})] \\ \hline \T &\T &\T &\T &\qquad\;\T &\F &\F &\F &\F &\T\qquad\; &\T \\ \T &\T &\F &\T &\qquad\;\F &\T &\F &\F &\F &\F\qquad\; &\T \\ \T &\F &\T &\F &\qquad\;\T &\F &\F &\T &\T &\T\qquad\; &\T \\ \T &\F &\F &\F &\qquad\;\T &\T &\F &\T &\T &\T\qquad\; &\T \\ \F &\T &\T &\F &\qquad\;\T &\F &\T &\F &\T &\T\qquad\; &\T \\ \F &\T &\F &\F &\qquad\;\T &\T &\T &\F &\T &\T\qquad\; &\T \\ \F &\F &\T &\F &\qquad\;\T &\F &\T &\T &\T &\T\qquad\; &\T \\ \F &\F &\F &\F &\qquad\;\T &\T &\T &\T &\T &\T\qquad\; &\T \\ \hline \end{array}$

2. (a) % \arraygap{1.125} \begin{array}[t]{|c|c|c|c|c|c|} \noalign{\vskip-9pt}\hline p & q & p\Rightarrow q & \overline{q} & \overline{p} & \overline{q}\Rightarrow\overline{p} \\ \hline \T & \T &\T &\F &\F &\T \\ \T & \F &\F &\T &\F &\F \\ \F & \T &\T &\F &\T &\T \\ \F & \F &\T &\T &\T &\T \\ \hline \end{array} (c) % \arraygap{1.125} \begin{array}[t]{|c|c|c|c|c|c|c|} \noalign{\vskip-9pt}\hline p & q & p\wedge q & \overline{p} & \overline{q} & \overline{p}\vee\overline{q} & \overline{\overline{p}\vee\overline{q}} \\ \hline \T & \T &\T &\F &\F &\F &\T \\ \T & \F &\F &\F &\T &\T &\F \\ \F & \T &\F &\T &\F &\T &\F \\ \F & \F &\F &\T &\T &\T &\F \\ \hline \end{array}

(b) % \arraygap{1.125} \begin{array}[t]{|c|c|c|} \noalign{\vskip-9pt}\hline p & p & p\vee p \\ \hline \T & \T &\T \\ \F & \F &\F \\ \hline \end{array} (d) % \arraygap{1.125} \begin{array}[t]{|c|c|c|c|c|c|} \noalign{\vskip-9pt}\hline p & q & p\Leftrightarrow q & p\Rightarrow q & q\Rightarrow p & (p\Rightarrow q) \wedge (q\Rightarrow p) \\ \hline \T & \T &\T &\T &\T &\T \\ \T & \F &\F &\F &\T &\F \\ \F & \T &\F &\T &\F &\F \\ \F & \F &\T &\T &\T &\T \\ \hline \end{array}

3. We need to compare the truth values of the three formulas: $p\veebar q, \qquad (p\vee q) \wedge \overline{p\wedge q}, \qquad\mbox{and}\qquad (p\wedge\overline{q}) \vee (\overline{p}\wedge q).$ The truth table for comparing them is depicted below. $% \arraygap{1.125} \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline p & q & p\veebar q & p\vee q & p\wedge q & \overline{p\wedge q} & (p\vee q) \wedge \overline{p\wedge q} & \overline{p} & \overline{q} & p\wedge \overline{q} & \overline{p}\wedge q & (p\wedge \overline{q}) \vee (\overline{p}\wedge q) \\ \hline \T &\T &\F &\T &\T &\F &\F &\F &\F &\F &\F &\F \\ \T &\F &\T &\T &\F &\T &\T &\F &\T &\T &\F &\T \\ \F &\T &\T &\T &\F &\T &\T &\T &\F &\F &\T &\T \\ \F &\F &\F &\F &\F &\T &\F &\T &\T &\F &\F &\F \\ \hline \end{array}$

4. The statement “$$0>x>1$$” means “$$(0>x) \wedge (x>1)$$,” which is always false because no such $$x$$ exists.

5. We find \begin{aligned} (p\vee q)\wedge (r\vee s) &\equiv& [p\wedge (r\vee s)] \vee [q\wedge(r\vee s)] \\ &\equiv& (p\wedge r)\vee(p\wedge s)\vee(q\wedge r)\vee(q\wedge s). \end{aligned}

### Section [sec:quant]

1. (a) false (b) true (c) true

2. The first three twin primes are 3 and 5, 5 and 7, and 11 and 13.

3. (a) False, a counterexample is $$x=2$$.

(b) True.

(c) False, because an even number is defined as an integral multiple of 2.

(d) True, see (c).

(e) False, $$x=\sqrt{2}$$ provides a counterexample.

4. False, because $$0^2=0$$.

5. True, because we can pick $$y=0$$, then regardless of what $$x$$ is, we always have $$xy=0<1$$.

6. (a) There exists a prime number $$x$$ such that the number $$x+1$$ is prime.

(b) There exists a prime number $$x>2$$ such that the number $$x+1$$ is prime.

(c) For any integer $$k$$, the number $$2k+1$$ is odd.

(d) There exists an integer $$k$$ such that $$2k$$ is odd.

(e) There exists a number $$x$$ such that $$x^2$$ is an integer and $$x$$ is not an integer.

7. One solution is: “There is a Discrete Mathematics student who has not taken Calculus I and Calculus II.” Because of De Morgan’s laws, we can also state the negation as “There is a Discrete Mathematics student who has not taken Calculus I or has not taken Calculus II.”

### Section [sec:pfintro]

1. The distance between $$a$$ and $$\frac{1}{3}\,a+\frac{2}{3}\,b$$ is $\left(\frac{1}{3}\,a+\frac{2}{3}\,b\right) - a = \frac{2}{3}\,b-\frac{2}{3}\,a = \frac{2}{3}\,(b-a).$ The distance between $$\frac{1}{3}\,a+\frac{2}{3}\,b$$ and $$b$$ is $b - \left(\frac{1}{3}\,a+\frac{2}{3}\,b\right) = \frac{1}{3}\,b - \frac{1}{3}\,a = \frac{1}{3}\,(b-a).$ Since $$\frac{2}{3}\,(b-a) > \frac{1}{3}\,(b-a)$$, the point $$\frac{1}{3}\,a+\frac{2}{3}\,b$$ is closer to $$b$$ than to $$a$$.

2. $$6 = 2\cdot3$$, $$40 = 2^3\cdot5$$, $$32 = 2^5\cdot1$$, and $$15 = 2^0\cdot15$$.

3. The five consecutive integers 722, 723, 724, 725, and 726 are composite.

4. Since $$a$$ and $$b$$ are rational numbers, we can write $$a=\frac{m}{n}$$ and $$b=\frac{r}{s}$$ for some integers $$m$$, $$n$$, $$r$$, and $$s$$, where $$n,s\neq0$$. Then the midpoint of the interval $$[a,b]$$ is $\frac{a+b}{2} = \frac{1}{2}\left(\frac{m}{n}+\frac{r}{s}\right) = \frac{ms+nr}{2ns},$ where $$ms+nr$$ and $$2ns$$ are integers, and $$2ns\neq0$$. Hence, $$\frac{a+b}{2}$$ is a rational number between $$a$$ and $$b$$.

5. Using the same argument in Hands-On Exercise [he:pfintro-04], we see that $$\frac{1}{3}\,a+\frac{2}{3}\,b$$ is rational, and we have learned from Hands-On Exercise [he:pfintro-01] that it is closer to $$b$$ than to $$a$$.

6. Let $$g(x) = 1+x\cos x$$. Noting that $$g(-\pi)=1-\pi<0$$ and $$g(0)=1>0$$, we conclude that the equation $$g(x)=0$$ has a real solution between $$-\pi$$ and 0.

### Section [sec:directpf]

1. Assume $$n$$ is odd, we can write $$n=2k+1$$ for some integer $$k$$. Then $n^3 = (2k+1)^3 = 8k^3+12k^2+6k+1 = 2(4k^3+6k^2+2k)+1,$ where $$4k^3+6k^2+2k$$ is an integer. Thus, $$n^3$$ is odd.

2. Assume $$x^3+6x^2+12x+8=0$$. Since $x^3+6x^2+12x+8 = (x+2)^3,$ we must have $$(x+2)^3=0$$. It follows that $$x=-2$$.

3. There are two cases.

• Case 1: If $$n$$ is even, then $$n=2q$$ for some integer $$q$$, so that $n^3+n = (2q)^3+2q = 8q^3+2q = 2(4q^3+q),$ where $$4q^3+q$$ is an integer.

• Case 2: If $$n$$ is odd, then $$n=2q+1$$ for some integer $$q$$, so that $n^3+n = (2q+1)^3+(2q+1) = 8q^3+12q^2+8q+2 = 2(4q^3+6q^2+4q+1),$ where $$4q^3+6q^2+4q+1$$ is an integer.

In both cases, we have proved that $$n^3+n$$ is even.

### Section [sec:indirectpf]

Assume $$x$$ is a real number such that $$x\neq-5$$ and $$x\neq7$$, then $$x+5\neq0$$ and $$x-7\neq0$$. Since $$2x^2+5$$ can never be zero, we find $(2x^2+3)(x+5)(x-7) \neq 0.$ Therefore, if $$(2x^2+3)(x+5)(x-7)=0$$, then either $$x=-5$$, or $$x=7$$.

We shall prove the contrapositive of the given statement. Let $$x$$ and $$y$$ be real numbers such that $$xy=0$$. Then either $$x=0$$ or $$y=0$$. Therefore, if $$x\neq0$$ and $$y\neq0$$, then $$xy\neq0$$.

Assume $$x^2\geq49$$, we want to prove that $$|x|\geq7$$. Suppose, on the contrary, $$|x|<7$$. This means $$-7<x<7$$. We need to study two cases.

If $$-7<x<0$$, we find $$0<x^2<49$$.

If $$0\leq x<7$$, we find $$0\leq x^2<49$$.

In both cases, we have $$x^2<49$$. This contradicts the given assumption that $$x^2\geq49$$. Therefore, we must have $$|x|\geq7$$.

Suppose there exist some positive numbers $$x$$ and $$y$$ such that $$\sqrt{x+y} = \sqrt{x}+\sqrt{y}$$, then $x+y = \left(\sqrt{x}+\sqrt{y}\,\right)^2 = x+2\sqrt{xy}+y,$ implying that $0 = 2\sqrt{xy},$ which is possible only when $$xy=0$$. But both $$x$$ and $$y$$ are positive, hence, $$xy\neq0$$. This contradiction shows that $$\sqrt{x+y} \neq \sqrt{x}+\sqrt{y}$$ for all positive numbers $$x$$ and $$y$$.

Suppose $$\sqrt{3}$$ is rational, then we can write $\sqrt{3} = \frac{m}{n}$ for some positive integers $$m$$ and $$n$$ such that $$m$$ and $$n$$ do not share any common divisor except 1 (hence, $$\frac{m}{n}$$ is in its simplest term). Squaring both sides and cross-multiplying gives $3n^2 = m^2.$ Thus 3 divides $$m^2$$, consequently 3 must also divide $$m$$. Then we can write $$m=3s$$ for some integer $$s$$. The equation above becomes $3n^2 = m^2 = (3s)^2 = 9s^2.$ Hence, $n^2 = 3s^2,$ which implies that 3 divides $$n^2$$, thus 3 also divides $$n$$. We have proved that both $$m$$ and $$n$$ are divisible by 3. This contradicts the assumption that $$m$$ and $$n$$ do not share any common divisor. Therefore, $$\sqrt{3}$$ must be irrational.

($$\Rightarrow$$) If $$n$$ is odd, we can write $$n=2k+1$$ for some integer $$k$$. Then $n^2 = (2k+1)^2 = 4k^2+4k+1 = 2(2k^2+2k)+1,$ where $$2k^2+2k$$ is an integer. Hence, $$n^2$$ is odd.

($$\Leftarrow$$) We shall prove its contrapositive: if $$n$$ is even, then $$n^2$$ is even. If $$n$$ is even, we can write $$n=2k$$ for some integer $$k$$. Then $n^2 = (2k)^2 = 4k^2 = 2\cdot 2k^2,$ where $$2k^2$$ is an integer, which means $$n^2$$ is even.

### Section [sec:induct1]

1. We proceed by induction on $$n$$. When $$n=1$$, the left-hand side reduces to $$1\cdot2=2$$, and the right-hand side becomes $$\frac{1\cdot2\cdot3}{3}=2$$. Hence, the identity holds when $$n=1$$. Assume the identity holds when $$n=k$$ for some integer $$k\geq1$$; that is, assume $1\cdot2 + 2\cdot3 + 3\cdot4 + \cdots + k(k+1) = \frac{k(k+1)(k+2)}{3}$ for some integer $$k\geq1$$. We want to show that it also holds when $$n=k+1$$; that is, we want to show that $1\cdot2 + 2\cdot3 + 3\cdot4 + \cdots + (k+1)(k+2) = \frac{(k+1)(k+2)(k+3)}{3}.$ It follows from the inductive hypothesis that \begin{aligned} 1\cdot2 + 2\cdot3 + \cdots + (k+1)(k+2) &=& 1\cdot2 + 2\cdot3 + \cdots + k(k+1) + (k+1)(k+2) \\ &=& \frac{k(k+1)(k+2)}{3} + (k+1)(k+2) \\ &=& (k+1)(k+2) \left(\frac{k}{3}+1\right) \\ &=& (k+1)(k+2) \left(\frac{k+3}{3}\right). \end{aligned} This completes the induction.

2. We proceed by induction on $$n$$. When $$n=1$$, the left-hand side reduces to $$1\cdot2\cdot3=6$$, and the right-hand side reduces to $$\frac{1\cdot2\cdot3\cdot4}{4}=6$$. Hence, the identity holds when $$n=1$$. Assume it holds when $$n=k$$ for some integer $$k\geq1$$; that is, assume $\sum_{i=1}^k i(i+1)(i+2) = \frac{k(k+1)(k+2)(k+3)}{4}$ for some integer $$k\geq1$$. We want to show that it also holds when $$n=k+1$$; that is, we want to show that $\sum_{i=1}^{k+1} i(i+1)(i+2) = \frac{(k+1)(k+2)(k+3)(k+4)}{4}.$ It follows from the inductive hypothesis that \begin{aligned} \sum_{i=1}^{k+1} i(i+1)(i+2) &=& \left(\sum_{i=1}^k i(i+1)(i+2)\right) + (k+1)(k+2)(k+3) \\ &=& \frac{k(k+1)(k+2)(k+3)}{4} + (k+1)(k+2)(k+3) \\ &=& (k+1)(k+2)(k+3) \left(\frac{k}{4} + 1\right) \\ &=& (k+1)(k+2)(k+3) \left(\frac{k+4}{4}\right). \end{aligned} This completes the induction.

3. We proceed by induction on $$n$$. When $$n=1$$, the left-hand side reduces to $$1+4=5$$, and the right-hand side becomes $$\frac{1}{3} (4^2-1)=5$$. Hence, the identity holds when $$n=1$$. Assume it holds when $$n=k$$ for some integer $$k\geq1$$; that is, assume that $1+4+4^2+\cdots+4^k = \frac{1}{3}\,(4^{k+1}-1)$ for some integer $$k\geq1$$. We want to show that it also holds when $$n=k+1$$; that is, we want to show that $1+4+4^2+\cdots+4^{k+1} = \frac{1}{3}\,(4^{k+2}-1).$ It follows from the inductive hypothesis that \begin{aligned} 1+4+4^2+\cdots+4^{k+1} &=& 1+4+4^2+\cdots+4^k+4^{k+1} \\ &=& \textstyle\frac{1}{3}\,(4^{k+1}-1) + 4^{k+1} \\ &=& \textstyle\frac{1}{3}\,(4^{k+1}-1+3\cdot4^{k+1}) \\ &=& \textstyle\frac{1}{3}\,(4\cdot4^{k+1}-1) \\ &=& \textstyle\frac{1}{3}\,(4^{k+2}-1). \end{aligned} This completes the induction.

### Section [sec:induct2]

1. We use induction to prove the claim. Note that $$n^2+3n+2=6$$ when $$n=1$$, so the claim is true. Assume it is true when $$n=k$$ for some integer $$k\geq1$$, so we can write $k^2+3k+2 = 2q$ for some integer $$q$$. We want to show that the claim is still true when $$n=k+1$$, that is, $(k+1)^2+3(k+1)+2 = 2Q$ for some integer $$Q$$. We find \begin{aligned} (k+1)^2+3(k+1)+2 &=& k^2+5k+6 \\ &=& (k^2+3k+2)+2k+4 \\ &=& 2q+2k+4 \\ &=& 2(q+k+2), \end{aligned} where $$q+k+2$$ is an integer. Thus, the claim is still true when $$n=k+1$$, thereby completing the induction.

2. Proceed by induction on $$n$$. Since $$1<2^1$$, the inequality is valid when $$n=1$$. Assume it is valid when $$n=k$$ for some integer $$k\geq1$$; that is, assume $k < 2^k$ for some integer $$k\geq1$$. We want to show that $k+1 < 2^{k+1}.$ Notice that for $$k\geq1$$, we have $$1<2^k$$. Hence, it follows from the inductive hypothesis that $k+1 < 2^k+1 < 2^k+2^k = 2\cdot 2^k = 2^{k+1}.$ This completes the induction and the proof of the given inequality.

3. Proceed by induction on $$n$$. When $$n=0$$, the LHS of the identity reduces to 1, and the RHS of the identity becomes $$3\big(1-\frac{2}{3}\big) = 3\cdot \frac{1}{3} = 1$$. Thus, the identity holds when $$n=0$$. Assume it holds when $$n=k$$ for some integer $$k\geq0$$. That is, assume $1+\frac{2}{3}+\frac{4}{9}+\cdots+\left(\frac{2}{3}\right)^k = 3\,\left[1-\left(\frac{2}{3}\right)^{k+1}\right]$ for some integer $$k\geq0$$. We want to show that it also holds when $$n=k+1$$. That is, we want to show that $1+\frac{2}{3}+\frac{4}{9}+\cdots+\left(\frac{2}{3}\right)^{k+1} = 3\,\left[1-\left(\frac{2}{3}\right)^{k+2}\right].$ According to the inductive hypothesis, \begin{aligned} 1+\frac{2}{3}+\frac{4}{9}+\cdots+\left(\frac{2}{3}\right)^{k+1} &=& 1+\frac{2}{3}+\frac{4}{9}+\cdots+\left(\frac{2}{3}\right)^k + \left(\frac{2}{3}\right)^{k+1} \\ &=& 3\,\left[1-\left(\frac{2}{3}\right)^{k+1}\right] + \left(\frac{2}{3}\right)^{k+1} \\ &=& 3\,\left[1-\left(\frac{2}{3}\right)^{k+1} + \frac{1}{3}\left(\frac{2}{3}\right)^{k+1} \right] \\ &=& 3\,\left[1-\frac{2}{3}\cdot\left(\frac{2}{3}\right)^{k+1}\right] \\ &=& 3\,\left[1-\left(\frac{2}{3}\right)^{k+2}\right]. \end{aligned} This completes the induction and the proof of the given identity.

### Section [sec:induct3]

1. Proceed by induction on $$n$$. When $$n=1,2$$, the proposed formula for $$c_n$$ says $$c_1=5\cdot3-4\cdot2=7$$, and $$c_2=5\cdot9-4\cdot4=29$$. They agree with the given initial values, so the formula holds for $$n=1,2$$. Assume the formula is valid for $$n=1,2,\ldots,k$$ for some integer $$k\geq2$$. In particular, assume $c_k = 5\cdot3^k-4\cdot2^k, \qquad\mbox{and}\qquad c_{k-1} = 5\cdot3^{k-1}-4\cdot2^{k-1}.$ We want to show that the formula still works when $$n=k+1$$. In other words, we want to show that $c_{k+1} = 5\cdot3^{k+1}-4\cdot2^{k+1}.$ Using the recurrence relation and the inductive hypothesis, we find \begin{aligned} c_{k+1} &=& 5c_k - 6c_{k-1} \\ &=& 5(5\cdot3^k-4\cdot2^k)-6(5\cdot3^{k-1}-4\cdot2^{k-1}) \\ &=& 25\cdot3^k-20\cdot2^k-30\cdot3^{k-1}+24\cdot2^{k-1} \\ &=& 25\cdot3^k-20\cdot2^k-10\cdot3\cdot3^{k-1}+12\cdot2\cdot2^{k-1} \\ &=& 25\cdot3^k-20\cdot2^k-10\cdot3^k+12\cdot2^k \\ &=& 15\cdot3^k-8\cdot2^k \\ &=& 5\cdot3\cdot3^k-4\cdot2\cdot2^k \\ &=& 5\cdot3^{k+1}-4\cdot2^{k+1}, \end{aligned} which is what we want to establish. This completes the induction, and hence, the claim that $$b_n = 2^n+3^n$$.

2. Proceed by induction on $$n$$. The claim is true for $$n=2,3$$, because \begin{aligned} 2 &=& 2\cdot1+3\cdot0, \\ 3 &=& 2\cdot0+3\cdot1. \end{aligned} Assume the claim holds when $$n=2,3,\ldots,k$$ for some integer $$k\geq3$$. In particular, since $$k-1\geq2$$, we may assume that $k-1 = 2x+3y$ for some nonnegative integers $$x$$ and $$y$$. We want to show that the claim is still true when $$n=k+1$$. We find \begin{aligned} k+1 &=& (k-1)+2 \\ &=& (2x+3y)+2 \\ &=& 2(x+1)+3y, \end{aligned} where $$x+1$$ and $$y$$ are nonnegative integers. Therefore, the claim is still true when $$n=k+1$$. This completes the induction.

### Section [sec:setintro]

1. $$\{-4,-3,-2,-1,0,1,2,3,4\}$$, and $$\{1,2,3,4\}$$.

2. $$\{1,4,9,16\}$$.

3. $$\{\ldots,-5,-3,-1,1,3,5,\ldots\}$$.

4. $$\{\ldots,-9,-6,-3,0,3,6,9,\ldots\}$$.

5. Only $$\{x\in\R \mid 1<x<7\}$$ can be represented by the interval notation $$(1,7)$$, because we have to include all the real numbers between 1 and 7.

6. Because $$[2,7]=\{x\in\R \mid 2\leq x\leq 7\}$$ includes decimal numbers and integers, but $$\{2,3,4,5,6,7\}$$ contains only integers.

7. False, because the interval $$(-2,3)$$ contains decimal numbers as well as integers, but the set $$\{-1,0,1,2\}$$ contains only integers.

8. $$\Z^-$$.

9. The notation $$[7,7]$$ means $$\{x\in\R \mid 7\leq x\leq7\}$$. Since equality is allowed, this set contains only one number, namely, the number 7. In other words, $$[7,7]=\{7\}$$. But the sets $$(7,7)$$, $$(7,7]$$ and $$[7,7)$$ are empty.

10. Both sets have two elements. The elements of $$\big\{0,\{1\}\big\}$$ are 0 and $$\{1\}$$, one of them is an integer, the other is a set. The elements of $$\big\{\{0\},\{1\}\big\}$$ are the two sets $$\{0\}$$ and $$\{1\}$$.

11. (a) 0 (b) the set is infinite (c) 1

12. It is incorrect to say $$|\emptyset|=\emptyset$$ because $$|\emptyset|$$ is a number (its value is 0), but $$\emptyset$$ is a set, they are incompatible.

### Section [sec:subsets]

1. (a) true (b) true

2. False, because $$3\in[3,4)$$ but $$3\notin(3,4)$$.

3. Since $$(3,4)$$ consists of numbers strictly between 3 and 4, every number we can find in $$(3,4)$$ also appears as a member of $$[3,4]$$. However, the interval $$[3,4]$$ also contains the two numbers 3 and 4, which are not members of the interval $$(3,4)$$. Therefore, it is true that $$(3,4)\subset[3,4]$$. Likewise, we also have $$(3,4)\subset(3,4]$$.

4. (a) According to Theorem [thm:twosubsets], the empty set is the subset of any set, including $$\{\emptyset\}$$. Thus, the statement is true.

(b) For $$S\subseteq T$$, every element of $$S$$ must be an element of $$T$$ as well. Here, the set $$\{1\}$$ has only one element: the number 1, which is also an element of $$\big\{1,\{1,2\}\big\}$$. Therefore, the statement is true.

(c) This time, 1 does not appear in $$\big\{\{1\},\{1,2\}\big\}$$ as an element. Notice that $$\big\{\{1\},\{1,2\}\big\}$$ has two elements, both of which are sets, namely, $$\{1\}$$ and $$\{1,2\}$$. Therefore, the statement is false. It would have been true if it were $$\{1\} \in \big\{\{1\},\{1,2\}\big\}$$.

5. The completed table is listed below. $\begin{array}{|c|l|} \hline \mbox{size} & \mbox{subset} \\ \hline 0 & \emptyset \\ 1 & \{1\}, \{2\}, \{3\}, \{4\} \\ 2 & \{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\} \\ 3 & \{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\} \\ 4 & \{1,2,3,4\} \\ \hline \end{array}$ The final answer is \begin{aligned} \wp(\{1,2,3,4\}) &=& \big\{ \emptyset, \{1\}, \{2\}, \{3\}, \{4\}, \{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}, \\ & & \qquad \{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}, \{1,2,3,4\} \big\}. \end{aligned}

6. The set $$\emptyset$$ has no element, but the set $$\{\emptyset\}$$ has one element (namely, the empty set). In terms of cardinality, $$|\emptyset|=0$$, and $$|\{\emptyset\}|=1$$. Yes, it is true that $$\wp(\emptyset) = \{\emptyset\}$$.

7. There are $$2^3=8$$ elements in $$\wp(\{\alpha,\beta, \gamma\})$$. They are $\emptyset, \quad \{\alpha\}, \quad \{\beta\}, \quad \{\gamma\}, \quad \{\alpha,\beta\}, \quad \{\alpha,\gamma\}, \quad \{\beta,\gamma\}, \quad\mbox{and}\quad \{\alpha,\beta,\gamma\}.$

8. Since $$|\emptyset|=0$$, the power set $$\wp(\emptyset)$$ has only $$2^0=1$$ element, which is $$\emptyset$$ itself. Therefore, $$\wp(\emptyset) = \{\emptyset\}$$.

9. Yes, because $$|A|$$ is a number, and $$2^{|A|}$$ does equal to $$|\wp(A)|$$. The notation $$2^A$$ is illegal because $$A$$ is a set, hence, it does not make much sense to raise 2 to a power that is not a number.

### Section [sec:unionint]

$$A\cap B = \{\mbox{John}\}$$, $$A\cup B = \{\mbox{John}, \mbox{Mary}, \mbox{Dave}, \mbox{Larry}, \mbox{Lucy}\}$$, $$A-B = \{\mbox{Mary}, \mbox{Dave}\}$$, $$B-A = \{\mbox{Larry}, \mbox{Lucy}\}$$, $$\overline{A} = \{\mbox{Lucy}, \mbox{Peter}, \mbox{Larry},\}$$, $$\overline{B} = \{\mbox{John}, \mbox{Mary}, \mbox{Dave}\}$$.

$$\emptyset$$.

(a) Because $$\{-1,-2,-3,\ldots\}$$ and $$\{1,2,3,\ldots\}$$ are sets, but 0 is not, we cannot form their set union. To fix it, we should write $$\Z = \{-1,-2,-3,\ldots\} \cup \{0\} \cup \{1,2,3,\ldots\}$$.

(b) This is worse than (a): all three components are not sets! Of course, it does not make much sense to take the union of things that are not even sets. To fix it, we need to insert curly braces (set brackets) as in (a).

(c) Same problem as in (b), plus a wrong notation for set union. To fix it, insert curly braces and change the symbol $$+$$ to $$\cup$$.

(d) Same as (a).

$$[-1,3)$$ and $$(0,3)$$.

Solution 1: Let $$x\in A\cap(B\cup C)$$. Then $$x\in A$$, and $$x\in B\cup C$$. We know that $$x\in B\cup C$$ implies that $$x\in B$$ or $$x\in C$$. So we have

$$x\in A$$ and $$x\in B$$, or

$$x\in A$$ and $$x\in C$$;

equivalently,

$$x\in A\cap B$$, or

$$x\in A\cap C$$.

Thus, $$x\in (A\cap B)\cup (A\cap C)$$. We have proved that $$A\cap(B\cup C) \subseteq (A\cap B)\cup(A\cap C)$$.

Now let $$x\in (A\cap B)\cup(A\cap C)$$. Then $$x\in A\cap B$$ or $$x\in A\cap C$$. From the definition of intersection, we find

$$x\in A$$ and $$x\in B$$, or

$$x\in A$$ and $$x\in C$$.

Both conditions require $$x\in A$$, so we can rewrite them as

$$x\in A$$, and

$$x\in B$$ or $$x\in C$$;

equivalently,

$$x\in A$$, or

$$x\in B\cup C$$.

Thus, $$x\in A\cap(B\cup C)$$. This proves that $$(A\cap B)\cup(A\cap C) \subseteq A\cap(B\cup C)$$. Together with $$A\cap(B\cup C) \subseteq (A\cap B)\cup(A\cap C)$$, we conclude that $$A\cap(B\cup C) = (A\cap B) \cup(A\cap C)$$.

Solution 2: We note that $\arraygap{1.125} \begin{array}{l@{\;\Leftrightarrow\;}l@{\qquad}l} x \in A \cap (B \cup C) & x\in A\wedge x\in(B \cup C) & \mbox{(defn.~of intersection)} \\ & x\in A\wedge (x\in B \vee x\in C) & \mbox{(defn.~of union)} \\ & (x\in A\wedge x\in B) \vee (x\in A \wedge x\in C) & \mbox{(distributive law)} \\ & (x\in A\cap B) \vee (x\in A\cap C) & \mbox{(defn.~of intersection)} \\ & x\in(A\cap B) \cup (A\cap C) & \mbox{(defn.~of union)} \end{array}$ it follows that $$A \cap (B \cup C) = (A\cap B) \cup (A\cap C)$$.

Assume $$A\subseteq B$$ and $$A\subseteq C$$. We want to show that $$A\subseteq B\cap C$$. To achieve this goal, let $$x\in A$$. Since $$A\subseteq B$$, we also have $$x\in B$$. Likewise $$A\subseteq C$$ implies that $$x\in C$$. Now $$x\in B$$ and $$x\in C$$ together imply that, according to the definition of set intersection, $$x\in B\cap C$$. We have proved that $$x\in A$$ implies that $$x\in B\cap C$$; it follows that $$A\subseteq B\cap C$$.

### Section [sec:cartprod]

1. $$A\times B = \{ (a,r), (a,s), (a,t), (b,r), (b,s), (b,t), (c,r), (c,s), (c,t), (d,r), (d,s), (d,t)\}$$,

$$B\times A = \{ (r,a), (r,b), (r,c), (r,d), (s,a), (s,b), (s,c), (s,d), (t,a), (t,b), (t,c), (t,d)\}$$,

$$B\times B = \{ (r,r), (r,s), (r,t), (s,r), (s,s), (s,t), (t,r), (t,s), (t,t)\}$$.

2. $$\big\{(a,\emptyset), (a,\{d\}), (b,\emptyset), (b,\{d\}), (c,\emptyset), (c,\{d\})\big\}$$.

3. $$\{(x,y) \mid 1\leq x\leq 3, 2\leq y\leq 4\}$$.

4. $$\{(1,a,r), (1,a,s), (1,a,t), (1,b,r), (1,b,s), (1,b,t)$$,

$$\phantom{\{} (2,a,r), (2,a,s), (2,a,t), (2,b,r), (2,b,s), (2,b,t)\}$$.

5. $$\big\{\big((1,a),r\big), \big((1,a),s\big), \big((1,a),t\big), \big((1,b),r\big), \big((1,b),s\big), \big((1,b),t\big)$$,

$$\phantom{\big\{} \big((2,a),r\big), \big((2,a),s\big), \big((2,a),t\big), \big((2,b),r\big), \big((2,b),s\big), \big((2,b),t\big)\big\}$$.

### Section [sec:indexset]

1. $$\bigcup_{i=1}^n B_i = [0,2n)$$, and $$\bigcap_{i=1}^n B_i = [0,2)$$.

2. $$\bigcup_{i=1}^\infty B_i = [0,\infty)$$, and $$\bigcap_{i=1}^\infty B_i = [0,2)$$.

3. $$\bigcup_{i=1}^\infty C_i = [0,1)$$, and $$\bigcap_{i=1}^\infty C_i = \{0\}$$.

4. $$\bigcup_{i=1}^\infty E_i = (-\infty,2)$$, and $$\bigcap_{i=1}^\infty E_i = [-1,1]$$.

5. $$\bigcup_{i=1}^\infty F_i = \N$$, and $$\bigcap_{i=1}^\infty F_i = \emptyset$$.

6. We find $\bigcup_{i\in J} A_i = A_1\cup A_4\cup A_5 = \{1,4,23\} \cup \{5,17,22\} \cup \{3,6,23\} = \{1,3,4,5,6,17,22,23\},$ and $\bigcap_{i\in J} A_i = A_1\cap A_4\cap A_5 = \{1,4,23\} \cap \{5,17,22\} \cap \{3,6,23\} = \emptyset.$

7. For $$I=\{\mbox{Mary},\mbox{Joe},\mbox{Lucy}\}$$, we have $\bigcup_{i\in I} = A_{\mbox{\footnotesize Mary}} \cup A_{\mbox{\footnotesize Joe}} \cup A_{\mbox{\footnotesize Lucy}} = \{7,11,23\} \cup \{3,6,9\} \cup \{3,6,23\} = \{3,6,7,9,11,23\}.$ These will be the numbers on their Lotto tickets if Mary, Joe, and Lucy pool their money together.

8. I leave them to you as exercises.

9. The union $$\bigcup_{i\in I} A_i$$ represents the set of people who is friend to at least one student in $$I$$. The intersection $$\bigcap_{i\in I} A_i$$ represents the set of people who knows everyone in $$I$$.

### Section [sec:PWO]

1. The subset $$(0,1)$$ does not have a smallest element. Thus $$[0,1]$$ is not well-ordered.

### Section [sec:divalgo]

1. (a) 18, 2 (b) $$-19$$, 5 (c) $$-25$$, 11

2. -24pt $$\begin{array}[t]{|r|r|r|r|} \hline b\hfil & a\hfil & b\bdiv a \hfil & b\bmod a \hfil \\ \hline 234 & 15 & 22 & 4 \\ 234 & -15 & -22 & 4 \\ -234 & 15 & -23 & 11 \\ -234 & -15 & 23 & 11 \\ \hline \end{array}$$

3. $$11q+4$$, 2.

4. Thursday.

### Section [sec:divides]

$$35=5\cdot7$$, $$35=8\cdot4+3$$, $$35=25\cdot1+10$$, $$14=7\cdot2$$, $$-14=2\cdot(-7)$$, $$14=14\cdot1$$.

When an odd integer is divided by 2, the remainder is 1. Hence, we have

If $$n$$ is even, then $$n=2q$$ for some integer $$q$$.

If $$n$$ is odd, then $$n=2q+1$$ for some integer $$q$$.

If $$n$$ is not divisible by 3, then $$n=3q+1$$ or $$n=3q+2$$ for some integer $$q$$.

1, 2, 3, 4, 6, 11, 12, 22, 33, 44, and 66.

27, 29, 31, 37, and 41.

Assume $$a\mid b$$ and $$a\mid c$$. There exist integers $$x$$ and $$y$$ such that $$b=ax$$ and $$c=ay$$. Then $bc = ax\cdot ay = a^2\cdot xy,$ where $$xy$$ is an integer. Thus, $$a^2\mid bc$$.

### Section [sec:gcd]

1. The only common divisors of 3 and 5 are $$\pm1$$. Hence, $$\gcd(3,5)=1$$.

2. The largest positive divisor of $$-8$$ is 8, which also divides 0. Thus, $$\gcd(0,-8)=8$$.

3. By applying the theorem repeatedly, we have $\begin{array}{rcl@{\qquad\qquad}lcl} 732 &=& 153\cdot4+120, & \gcd(732,153) &=& \gcd(153,120) \\ [3pt] 153 &=& 120\cdot1+ 33, & \gcd(153,120) &=& \gcd(120, 33) \\ [3pt] 120 &=& 33\cdot3+ 21, & \gcd(120, 33) &=& \gcd( 33, 21) \\ [3pt] 33 &=& 21\cdot1+ 12, & \gcd( 33, 21) &=& \gcd( 21, 12) \\ [3pt] 21 &=& 12\cdot1+ 9, & \gcd( 21, 12) &=& \gcd( 12, 9) \\ [3pt] 12 &=& 9\cdot1+ 3, & \gcd( 12, 9) &=& \gcd( 9, 3) \\ [3pt] 9 &=& 3\cdot3+ 0, & \gcd( 9, 3) &=& \gcd( 3, 0) = 3. \end{array}$ Therefore, $$\gcd(732,153)=3$$.

4. By applying division repeatedly, we find $\begin{array}{rcl@{\qquad\qquad}lcl} 6958 &=& 2478\cdot2+2002 & \gcd(6958,2478) &=& \gcd(2478,2002), \\ [3pt] 2478 &=& 2002\cdot1+ 476 & \gcd(2478,2002) &=& \gcd(2002, 476), \\ [3pt] 2002 &=& 476\cdot4+ 98 & \gcd(2002, 476) &=& \gcd( 476, 98), \\ [3pt] 476 &=& 98\cdot4+ 84 & \gcd( 476, 98) &=& \gcd( 98, 84), \\ [3pt] 98 &=& 84\cdot1+ 14 & \gcd( 98, 84) &=& \gcd( 84, 14), \\ [3pt] 84 &=& 14\cdot6+ 0 & \gcd( 84, 14) &=& \gcd( 14, 0)=14. \end{array}$ Therefore, $$\gcd(6958,2478)=14$$.

5. We find $$\gcd(732,153)=3$$, as follows: $\begin{array}[c]{r|r|r|r} 4 & 732 & 153 & 1 \\ 1 & 612 & 120 & \\ \cline{2-3} 3 & 120 & 33 & 1 \\ 1 & 99 & 21 & \\ \cline{2-3} 1 & 21 & 12 & 1 \\ 1 & 12 & 9 & \\ \cline{2-3} 3 & 9 & 3 & \\ & & 9 & \\ \cline{2-3} & & 0 & \end{array}$

6. We find $$\gcd(6958,2478)=14$$, as follows: $\begin{array}[c]{r|r|r|r} 2 & 6958 & 2478 & 1 \\ & 4956 & 2002 & \\ \cline{2-3} 4 & 2002 & 476 & 4 \\ & 1904 & 392 & \\ \cline{2-3} 1 & 98 & 84 & 6 \\ & 84 & 84 & \\ \cline{2-3} & 14 & 0 & \end{array}$

7. From the linear combinations $\begin{array}{rcrcr} 7(5m+7n) &-& 5(7m+5n) &=& 24n, \\ [3pt] -5(5m+7n) &+& 7(7m+5n) &=& 24m, \end{array}$ we know that $$\gcd(5m+7n,7m+5n)$$ divides both $$24n$$ and $$24m$$. Since $$\gcd(m,n)=1$$, we conclude that $$\gcd(5m+7n,7m+5n)$$ divides 24. Thus, $$\gcd(5m+7n,7m+5n)$$ equals to 1, 2, 3, 4, 6, 8, 12, or 24.

8. The following computation $\begin{array}[t]{rr@{\qquad}r|r|r|r} s_k & t_k & \multicolumn{1}{r}{q_k} \\ 0 & 1 \\ 1 & 0 & 4 & 732 & 153 & 1 \\ -4 & 1 & 1 & 612 & 120 & \\ \cline{4-5} 5 & -1 & 3 & 120 & 33 & 1 \\ -19 & 4 & 1 & 99 & 21 & \\ \cline{4-5} 24 & -5 & 1 & 21 & 12 & 1 \\ -43 & 9 & 1 & 12 & 9 & \\ \cline{4-5} 67 & -14 & 3 & 9 & 3 & \\ & & & 9 & & \\ \cline{4-4} & & & 0 & \end{array}$ shows that $$3=\gcd(153,732)=67\cdot153-14\cdot732$$.

9. The following computation $\begin{array}[t]{rr@{\qquad}r|r|r|r} s_k & t_k & \multicolumn{1}{r}{q_k} \\ 0 & 1 \\ 1 & 0 & 2 & 6958 & 2478 & 1 \\ -2 & 1 & 1 & 4956 & 2002 & \\ \cline{4-5} 3 & -1 & 4 & 2002 & 476 & 4 \\ -14 & 5 & 4 & 1904 & 392 & \\ \cline{4-5} 59 & -21 & 1 & 98 & 84 & 6 \\ -73 & 26 & 6 & 84 & 84 & \\ \cline{4-5} & & & 14 & 0 & \end{array}$ shows that $$14=\gcd(2478,6958)=-73\cdot2478+26\cdot6958$$.

### Section [sec:moregcd]

1. $$-43\cdot133+40\cdot143=1$$.

2. $$-512\cdot757+319\cdot1215=1$$.

3. Suppose $$\sqrt{7}$$ is rational, then we can write $\sqrt{7} = \frac{m}{n}$ for some positive integers $$m$$ and $$n$$ that do not share any common divisor except 1. Squaring both sides and cross-multiplying gives $7n^2 = m^2.$ Thus 7 divides $$m^2$$. Since 7 is prime, Euclid’s lemma asserts that 7 must also divide $$m$$. Then we can write $$m=7s$$ for some integer $$s$$. The equation above becomes $7n^2 = m^2 = (7q)^2 = 49q^2.$ Hence, $n^2 = 7q^2,$ which implies that 7 divides $$n^2$$. Again, since 7 is prime, Euclid’s lemma implies that 7 also divides $$n$$. We have proved that both $$m$$ and $$n$$ are divisible by 7. This contradicts the assumption that $$m$$ and $$n$$ do not share any common divisor. Therefore, $$\sqrt{7}$$ must be irrational.

### Section [sec:FTA]

1. Since $$153=3\cdot3\cdot17$$, and $$72=2\cdot2\cdot3\cdot61$$, we determine that $$\gcd(153,72)=3$$.

2. By writing the factorizations as \begin{aligned} 2^3\cdot5\cdot7\cdot11^2 &=& 2^3\cdot3^0\cdot5^1\cdot7^1\cdot11^2, \\ 2^2\cdot3^2\cdot5^2\cdot7^2 &=& 2^2\cdot3^2\cdot5^2\cdot7^2\cdot11^0, \\ \end{aligned} it becomes clear that $$\gcd(2^3\cdot5\cdot7\cdot11^2, 2^2\cdot3^2\cdot5^2\cdot7^2) = 2^2\cdot3^0\cdot5^1\cdot7^1\cdot11^0 = 4\cdot5\cdot = 140$$.

3. We find $$\lcm(2^3\cdot5\cdot7\cdot11^2, 2^2\cdot3^2\cdot5^2\cdot7^2) = 2^3\cdot3^2\cdot5^2\cdot7^2\cdot11^2 = 10672200$$.

4. We find $$\dd\lcm(246,426) = \frac{246\cdot426}{\gcd(246,426)} = \frac{246\cdot426}{6} = 17466$$.

5. Since $$\lcm(35,42)=210$$, the two comets will return to Earth together in 2222.

6. From the linear combinations $\begin{array}{rcrcr} 6(4m-6n) &-& 4(6m+4n) &=& -52n, \\ [3pt] 4(4m-6n) &+& 6(6m+4n) &=& 52m, \end{array}$ we know that $$\gcd(4m-6n,6m+4n)$$ divides both $$-52n$$ and $$52m$$. Since $$\gcd(m,n)=1$$, we conclude that $$\gcd(4m-6n,6m+4n)$$ divides 52. Consequently, $$\gcd(4m-6n,6m+4n)$$ equals to 1, 2, 4, 13, 26, or 52. It follows that $$\lcm(4m-6n,6m+4n)$$ equals to $$mn$$, $$mn/2$$, $$mn/4$$, $$mn/13$$, $$mn/26$$, or $$mn/52$$.

7. Assume $$x\in 4\Z\cap6\Z$$, then $$x\in4\Z$$ and $$x\in6\Z$$. This means $$x$$ is a multple of both 4 and 6. Consequently, $$x$$ is a multiple of $$\lcm(4,6)=12$$, which means $$x\in12\Z$$. Thus, $$4\Z\cap6\Z \subseteq 12\Z$$.

Next, assume $$x\in 12\Z$$, then $$x$$ is a multiple of 12. Consequently, $$x$$ is a multiple of 3, as well as a multiple of 4. This means $$x\in4\Z$$, and $$x\in6\Z$$. As a result, $$x\in 4\Z\cap6\Z$$. Thus, $$12\Z \subseteq 4\Z\cap6\Z$$. Together with $$4\Z\cap6\Z \subseteq 12\Z$$, we conclude that $$4\Z\cap6\Z = 12\Z$$.

### Section [sec:modarith]

1. Wednesday.

2. 13.

3. 3.

4. 8.

5. There are five cases to consider: $\begin{array}{|c|l|} \hline \mbox{n (mod~5)} & \hfil\mbox{n^5-n (mod~5)} \\ \hline 0 & 0^5-0 = 0 \\ 1 & 1^5-1 = 0 \\ 2 & 2^5-2 = 30 \equiv 0 \\ 3 & 3^5-3 = 340 \equiv 0 \\ 4 & 4^5-4 = 1020 \equiv 0 \\ \hline \end{array}$ Therefore, for any integer $$n$$, we always have $$n^5-n\equiv0$$ (mod 5), which means $$5\mid(n^5-n)$$.

6. $$7^{45} = 7^{32}\cdot7^8\cdot7^4\cdot7 \equiv 5\cdot9\cdot3\cdot7 \equiv 10$$ (mod 11).

7. $$9^{58} = 9^{32}\cdot9^{16}\cdot9^8\cdot9^2 \equiv 18\cdot8\cdot13\cdot12 \equiv 16$$ (mod 23).

8. 17.

9. 38.

### Section [sec:fcnintro]

1. The domain is $$\R$$, and the codomain is $$\Z$$.

2. The range is $$\R^+\cup\{0\}$$. Hence, the square root function is not onto.

3. No, because $$\R^+$$ is a set, and 0 is a number. We can only take union of two sets.

### Section [sec:defnfcn]

1. Only $$f$$ is a well-defined function. The rule for $$g$$ does not assign any value to $$a$$. In other words, $$g(a)$$ is undefined. For $$h$$, two values are associated to $$b$$. That is, there are two possible values for the image $$h(b)$$, which is not allowed.

2. No, $$r$$ is not a well-defined function because the value of $$r(x)$$ should be the same regardless of which day of the week it is.

3. No, $$s$$ is not a well-defined function because the images $$s(x)$$ are undefined for $$2\leq x\leq3$$.

4. We also have $n(\{a,b\}) = n(\{a,d\}) = n(\{b,c\}) = n(\{c,d\}) = 2.$ The value of $$n(S)$$ must be between 0 and 4, inclusive.

5.  -24pt $$\begin{array}[t]{|c||*{10}{c|}} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline g(n) & 0 & 3 & 1 & 4 & 2 & 0 & 3 & 1 & 4 & 2 \\ \hline \end{array}$$

6.  -18pt

(260,160)(-20,-20) (-10,0)(1,0)230 (220,-10)(20,20)$$x$$ (0,-10)(0,1)130 (-10,120)(20,20)$$y$$ (20,-3)(20,0)10(0,1)6 (-3,20)(0,20) 5(1,0)6 ( 10,-20)(20,15)0 ( 30,-20)(20,15)1 ( 50,-20)(20,15)2 ( 70,-20)(20,15)3 ( 90,-20)(20,15)4 (110,-20)(20,15)5 (130,-20)(20,15)6 (150,-20)(20,15)7 (170,-20)(20,15)8 (190,-20)(20,15)9 (-20, 10)(20,20)0 (-20, 30)(20,20)1 (-20, 50)(20,20)2 (-20, 70)(20,20)3 (-20, 90)(20,20)4 ( 20, 20) ( 40, 80) ( 60, 40) ( 80,100) (100, 60) (120, 20) (140, 80) (160, 40) (180,100) (200, 60)

0.7in

(80,160)(0,0) (0,0)(80,160) \begin{array}[c]{cc} & \begin{array}{ccccc} 0 & 1 & 2 & 3 & 4 \end{array} \\ \noalign{\medskip} \begin{array}{c} 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \end{array} & \left(\begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \end{array}\right) \end{array}

### Section [sec:oneonefcn]

Assume $$g(x_1)=g(x_2)$$, then $5-7x_1 = 5-7x_2,$ which clearly implies $$x_1=x_2$$. Hence, $$g$$ is one-to-one.

Assume $$h(x_1)=h(x_2)$$, then $\sqrt{x_1-2} = \sqrt{x_2-2}.$ Squaring both sides yields $$x_1-2=x_2-2$$, which clearly implies $$x_1=x_2$$. Hence, $$h$$ is one-to-one.

Assume $$k(x_1)=k(x_2)$$, then $\ln x_1 = \ln x_2.$ Raising both sides to the power of $$e$$, we find $e^{\ln x_1} = e^{\ln x_2},$ which simplifies to $$x_1=x_2$$. Thus, $$k$$ is a one-to-one function.

Alternatively, we can look at the derivative $$k'(x)=1/x$$. Since $$k'(x)>0$$ for all $$x>0$$, the function $$k$$ is increasing. Thus, $$k$$ is one-to-one.

First, we use the two-point form to find the equation of the line: $\frac{y-2}{x-3} = \frac{5-2}{1-3} = -\frac{3}{2}.$ This simplifies to $$y=-\frac{3}{2}\,x+\frac{13}{2}$$. However, this is not the correct answer. We want a function, so the answer should be $\fcn{f}{[1,3]}{[2,5]}, \qquad f(x)=-\frac{3}{2}\,x+\frac{13}{2}.$

There are many possible answers, we only give two here, their graphs are the straight lines that join the opposite corners of the rectangle framed by the domain and codomain. The straight line joining the two corners $$(3,2)$$ and $$(8,5)$$ yields the example $\fcn{f}{[3,8]}{[2,5]}, \qquad f(x) = \frac{3}{5}\,x+\frac{1}{5},$ and the line joining the two corners $$(3,5)$$ and $$(8,2)$$ gives the example $\fcn{g}{[3,8]}{[2,5]}, \qquad g(x) = -\frac{3}{5}\,x+\frac{34}{5}.$

Assume $$h(x_1)=h(x_2)$$, then $4x_1-11 \equiv 4x_2-11 \pmod{15}.$ Adding 11 to both sides yields $4x_1 \equiv 4x_2 \pmod{15}.$ Multiplying 4 to both sides leads to $16x_1 \equiv 16x_2 \pmod{15},$ which simplifies to $$x_1\equiv x_2$$ (mod 15). Therefore, $$h$$ is one-to-one.

We find, for example, $$k(3)\equiv k(6) \equiv 4$$ (mod 15). Hence, $$k$$ is not one-to-one.

Assume $$h(n_1)=h(n_2)$$. Since the image is either odd or even, we have to consider two cases.

If both $$h(n_1)$$ and $$h(n_2)$$ are odd, then $2n_1+1 = 2n_2+1,$ hence, $$n_1=n_2$$.

If both $$h(n_1)$$ and $$h(n_2)$$ are even, then $-2n_1 = -2n_2,$ hence, $$n_1=n_2$$.

In both cases, we find $$n_1=n_2$$. Therefore, $$h$$ is one-to-one.

### Section [sec:ontofcn]

1. We can use, for example, a straight line graph that connects the points $$(1,2)$$ and $$(3,5)$$. This leads to the function $$\fcn{f}{[1,3]}{[2,5]}$$ defined by $$f(x)=\frac{3}{2}\,x+\frac{1}{2}$$.

2. We can use, for example, a straight line graph that connects the points $$(1,2)$$ and $$(3,4)$$, see Figure [fig:otograph].

3. $$[0,\infty)$$.

4. The midpoint of the interval $$(2,9)$$ is $$\frac{11}{2}$$, and its width is 7. The transformation of $$x$$ to $$x-\frac{11}{2}$$ shifts the interval to $$\left(-\frac{7}{2},\frac{7}{2}\right)$$. Hence, we can set $$h(x) = \tan\big[\frac{\pi}{7}\big(x-\frac{11}{2}\big)\big]$$.

5. Let $$y=3x+11$$, then $x = \frac{y-11}{3},$ which is, of course, an element of the domain. Hence, $$g$$ is onto.

6. It is obvious that the graphs $$y=3x+1$$ and $$y=4x$$ are increasing. For $$x\leq 2$$, the $$y$$-values cover the range $$(-\infty,7)$$. For $$x>2$$, the $$y$$-values cover the range $$(8,\infty)$$. Hence, the $$y$$-values in the interval $$[7,8]$$ are never used as images. For example, there is no $$x$$-value which would give $$f(x)=\frac{15}{2}$$. Therefore, $$f$$ is not onto.

7. Let $$y\equiv 5x+8$$ (mod 23). Then $5x \equiv y-8 \pmod{23}.$ Since $$5^{-1}\equiv14$$ (mod 23), we find $x \equiv 5^{-1}(y-8) \equiv 14(y-8) \pmod{23}.$ Therefore, $$h$$ is onto.

8. No! Since $$v(n)\geq2$$, there does not exist $$n\in\N$$ such that $$v(n)=1$$.

9. No! Someone in the tree would have no daughter. She could be you, or your sisters, or one of their infant daughters, or someone higher up in the tree. For this individual $$y$$, we cannot find any $$x$$ such that $$h_1(x)=y$$, because this would make $$x$$ a daughter of $$x$$.

### Section [sec:propfcn]

$$(11,\infty)$$; $$\R$$.

Since $x^2-x-7 = \left(x-\frac{1}{2}\right)^2 - \frac{29}{4} \geq -\frac{29}{4},$ we determine that $$\image{g}=\big(-\frac{29}{4},\infty)$$.

Remember that $$h(\{0,3,4\})$$ is a set, so we need to use a set notation. The answer is $$\{4,9\}$$.

$$\{0,1,2,3,4,5\}$$.

Let $$y\in f(C_1\cap C_2)$$, we want to show that $$y\in f(C_1)\cap f(C_2)$$. Having $$y\in f(C_1\cap C_2)$$ means there exists $$x\in C_1\cap C_2$$ such that $$f(x)=y$$. Now that $$x\in C_1\cap C_2$$ requires $$x\in C_1$$ and $$x\in C_2$$.

For $$x\in C_1$$, we find $$y=f(x)\in f(C_1)$$.

For $$x\in C_2$$, we find $$y=f(x)\in f(C_2)$$.

We conclude that $$y=f(x)$$ belongs to both $$f(C_1)$$ and $$f(C_2)$$. Thus, $$f(x)\in f(C_1)\cap f(C_2)$$, proving that $$f(C_1\cap C_2) \subseteq f(C_1)\cap f(C_2)$$.

We want to find $$x$$ such that $x^2-x-7 = 3.$ This is equivalent to solving the equation $x^2-x-10 = 0.$ Its solutions are $$x=\frac{1\pm\sqrt{41}}{2}\notin\Q$$. Therefore, $$k^{-1}(\{3\}) = \emptyset$$.

$$h^{-1}(\{4\}) = \{0,3,6,9,12\}$$; $$h^{-1}(\{2\}) = \emptyset$$.

First, we want to prove that $$f^{-1}(D_1\cap D_2) \subseteq f^{-1}(D_1) \cap f^{-1}(D_2)$$. Let $$x\in f^{-1}(D_1\cap D_2)$$, then $$f(x)\in D_1\cap D_2$$. This means either $$f(x)\in D_1$$ and $$f(x)\in D_2$$.

For $$f(x)\in D_1$$, we find $$x\in f^{-1}(D_1)$$.

For $$f(x)\in D_2$$, we find $$x\in f^{-1}(D_2)$$.

Since $$x$$ belongs to both $$f^{-1}(D_1)$$ and $$f^{-1}(D_2)$$, we determine that $$x\in f^{-1}(D_1)\cap f^{-1}(D_2)$$. Therefore, $$f^{-1}(D_1\cap D_2) \subseteq f^{-1}(D_1)\cap f^{-1}(D_2)$$.

Next, we want to prove that $$f^{-1}(D_1)\cap f^{-1}(D_2) \subseteq f^{-1}(D_1\cap D_2)$$. Let $$x\in f^{-1}(D_1)\cap f^{-1}(D_2)$$. Then $$x$$ belongs to both $$f^{-1}(D_1)$$ and $$x\in f^{-1}(D_2)$$.

For $$x\in f^{-1}(D_1)$$, we find $$f(x)\in D_1$$.

For $$x\in f^{-1}(D_2)$$, we find $$f(x)\in D_2$$.

Hence, $$f(x)$$ belongs to both $$D_1$$ and $$D_2$$, which means $$f(x)\in D_1\cap D_2$$. Thus, $$x\in f^{-1}(D_1\cap D_2)$$. We have proved that $$f^{-1}(D_1)\cap f^{-1}(D_2) \subseteq f^{-1}(D_1\cap D_2)$$. Together with $$f^{-1}(D_1\cap D_2) \subseteq f^{-1}(D_1)\cap f^{-1}(D_2)$$, we conclude that $$f^{-1}(D_1\cap D_2) = f^{-1}(D_1)\cap f^{-1}(D_2)$$.

### Section [sec:invfcn]

1. $$\fcn{f^{-1}}{[\,0,\infty)}{[-3,\infty)}$$, $$f^{-1}(x) = x^2-3$$.

2. $$\fcn{g^{-1}}{(0,\infty)}{\R}$$, $$g^{-1}(x) = \ln x$$.

3. Following the same idea used in Example [eg:invfcn-03], we find \fcn{g^{-1}}{\R}{\R}, \qquad g^{-1}(x) = \cases{ \frac{1}{3}\,(x-5) & if x\leq23, \cr\noalign{\smallskip} \frac{1}{5}\,(x+7) & if x > 23. \cr}

4. Let $$y\equiv 49x-3$$ (mod 57). Interchanging $$x$$ and $$y$$ yields $x \equiv 49y-3 \pmod{57}.$ Hence, $y \equiv 49^{-1}(x+3) \equiv 7(x+3) \pmod{57}.$ Therefore, $$\fcn{h^{-1}}{\Z_{57}}{\Z_{57}}$$ is defined by $$h^{-1}(x)= 7(x+3)\bmod57$$.

5. Following the same idea used in Example [eg:invfcn-06], we find \fcn{f^{-1}}{\N}{\Z}, \qquad f^{-1}(n) = \cases{ -\frac{n}{2} & if n is even, \cr \noalign{\smallskip} \frac{n-1}{2} & if n is odd. \cr}

6. $$(0,0,0,0,0,0,0,0)$$; $$\{a_1,a_3,a_4,a_5\}$$.

### Section [sec:compfcn]

1. We find $$\fcn{p\circ q}{\R}{\R}$$ and $$\fcn{q\circ p}{\R}{\R}$$ defined by $$(p\circ q)(x)=2x^2+7$$, and $$(q\circ p)(x)=4x^2+20x+26$$.

2. Direct computation yields $f(g(x)) \equiv 7g(x)+2 \equiv 7(5x-3)+2 \equiv 11x+5 \pmod{12}.$ Hence, $$\fcn{f\circ g}{\Z_{12}}{\Z_{12}}$$ is defined by $$(f\circ g)(x) \equiv 11x+5$$ (mod 12).

3. Since $$(f\circ g)(x) = f(g(x)) = 3g(x)+2$$, the function $$\fcn{f\circ g} {\R}{\R}$$ is defined by \begin{aligned} (f\circ g)(x) &=& \cases{ 3x^2+2 & if x\leq5 \cr 3(2x-1)+2 & if x > 5 \cr} \\ [3pt] &=& \cases{ 3x^2+2 & if x\leq5 \cr 6x-1 & if x > 5 \cr} \end{aligned}

4. The composite function $$\fcn{f\circ g}{\Z}{\Z}$$ is defined by $(f\circ g)(n) = \cases{ n-6 & if n is even, \cr n+2 & if n is odd. \cr}$ This is how we obtained the answer. If $$n$$ is even, then $$f(n)=n+1$$ is odd, so we have to use the second branch in $$g$$ to evaluate $$g(f(n))$$. We find, for even $$n$$, $$g(f(n))=g(n+1)=(n+1)-7=n-6$$. In a similar manner, when $$n$$ is odd, $$f(n)=n-1$$ is even, therefore $$g(f(n))=g(n-1)=(n-1)+3=n+2$$.

5. The composite function $$h\circ g$$ is easy to obtain: $\fcn{h\circ g}{\Z}{\R}, \qquad (h\circ g)(x) = \big(\sqrt{|x|}-5\big)^2.$ To compute $$g\circ h$$, we start with $$h$$, whose codomain is $$\R$$. This means the result from $$h$$ could be a real number. But the domain of $$g$$ is $$\Z$$, therefore $$g\circ h$$ is not a well-defined composite function.

6. We find $\displaylines{ (f\circ g)(x) = f(g(x)) = e^{g(x)} = e^{\ln x} = x, \cr (g\circ f)(x) = g(f(x)) = \ln f(x) = \ln e^x = x. \cr}$ Therefore, $$f$$ and $$g$$ are inverse functions of each other.

### Section [sec:defnrelat]

1. False, false, true, true, true.

2. Yes, we can write either $$(2,0.5)\in G$$, or $$2\,G\,0.5$$.

No, $$(4,0.5)\notin G$$, which can also be written as $$4\not\!G\,0.5$$.

No, $$(10,3)\notin G$$, and we can also write $$10\not\!G\,3$$.

3. No, $$(0,3)\notin G$$, or $$0\not\!G\,3$$. No, $$(1,-1)\notin G$$, or $$1\not\!\!G\,-1$$. Yes, $$\big(\frac{1}{\sqrt{2}},\sqrt{2}\,\big)\in G$$, or $$\frac{1}{\sqrt{2}}\,G\,\sqrt{2}$$.

4. $$S=\{(2,2),(2,4),(2,6),(2,8),(2,10),(2,12),(3,3),(3,6),(3,9),(3,12)$$,

$$\qquad\quad (4,4),(4,8),(4,12)\}$$.

5. $$\mbox{dom}\,S = \{2,3,4\} = S-\{7\}$$, $$\image{S} = \{2,3,4,6,8,9,10,12\} = S-\{1,5,7,11\}$$.

6. \begin{array}[t]{cc} & \begin{array}{*{12}{c}} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \end{array} \\ \noalign{\medskip} \begin{array}{c} 2 \\ 3 \\ 4 \\ 7 \end{array} & \left(\begin{array}{*{12}{c}} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 &\;1\;&\;0\;&\;1\; \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 &\;0\;&\;0\;&\;1\; \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 &\;0\;&\;0\;&\;1\; \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\;0\;&\;0\;&\;0\; \end{array}\right) \end{array}

7. -3pt

(190,70)(-20,-10) (0, 0)(40,0)4 (0,40)(40,0)5 (-10,-20)(20,20)John ( 30,-20)(20,20)Mary ( 70,-20)(20,20)Paul (110,-20)(20,20)Sally (-10, 50)(20,20)MATH (-10, 40)(20,20)210 ( 30, 50)(20,20)CSIT ( 30, 40)(20,20)121 ( 70, 50)(20,20)MATH ( 70, 40)(20,20)223 (110, 50)(20,20)MATH (110, 40)(20,20)231 (150, 50)(20,20)CSIT (150, 40)(20,20)120 ( 0,0)( 0,1) 40 ( 0,0)( 1,1) 40 ( 0,0)( 2,1) 80 ( 40,0)( 0,1) 40 ( 40,0)(-1,1) 40 ( 40,0)( 2,1) 80 ( 80,0)( 0,1) 40 ( 80,0)( 1,1) 40 ( 80,0)( 2,1) 80 (120,0)(-3,1)120 (120,0)( 1,1) 40

0.3in

0pt \begin{array}[t]{cc} & \begin{array}{ccccc} \rotatebox{90}{\mbox{MATH 210}} & \rotatebox{90}{\mbox{CSIT 121}} & \rotatebox{90}{\mbox{MATH 223}} & \rotatebox{90}{\mbox{MATH 231}} & \rotatebox{90}{\mbox{CSIT 120}} \end{array} \\ \noalign{\medskip} \begin{array}{c} \mbox{John} \\ \mbox{Mary} \\ \mbox{Paul} \\ \mbox{Sally} \end{array} & \left(\begin{array}{ccccc} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \end{array}\right) \end{array}

### Section [sec:proprelat]

We find the following.

The relation $$R$$ is reflexive since $$a\leq a$$ for all $$a$$; hence, it cannot be irreflexive.

It is not symmetric, because $$2\leq 3$$ but $$3\nleq 2$$.

Since $$a\leq b$$ and $$b\leq a$$ does imply that $$a=b$$, the relation$$R$$ is antisymmetric.

Finally, it is transitive because $$a\leq b$$ and $$b\leq c$$ imply that $$a\leq c$$.

The relation $$R$$ is reflexive, antisymmetric, and transitive.

This is how the analysis may proceed:

Since $$a\cdot a = a^2$$ is always positive for any $$a\in\R^*$$ (question: is it still true if $$A=\R$$?), the relation $$S$$ is reflexive, hence, it is not irreflexive.

Since $$ab=ba$$, it follows that whenever $$ab>0$$, we also have $$ba>0$$. Therefore, $$S$$ is symmetric.

However, $$S$$ is not antisymmetric. For example, $$2\cdot3>0$$ and $$3\cdot2>0$$, but $$2\neq 3$$.

Since $$ab>0$$ only when $$a$$ and $$b$$ have the same sign, if we also have $$bc>0$$, then $$c$$ must have the same sign as $$b$$, hence, the same sign as $$a$$, which in turn implies that $$ac>0$$. Thus, $$S$$ is transitive.

The given relation is reflexive, symmetric, and transitive.

The is how the analysis goes:

The relation $$T$$ is reflexive because $$a\mid a$$ for any positive integer $$a$$. Consequently, $$T$$ is not irreflexive.

Since $$2\mid6$$ but $$6\nmid2$$, we find $$T$$ non-symmetric.

However, if $$a\mid b$$ and $$b\mid a$$, we must have $$a=b$$, thus $$T$$ is antisymmetric.

Finally, $$a\mid b$$ and $$b\mid c$$ do imply that $$a\mid c$$, hence, $$T$$ is transitive.

The relation is reflexive, antisymmetric, and transitive.

The argument is similar to Hands-On Exercise [he:proprelat-03], the relation is reflexive and transitive.

The argument is similar to Hands-On Exercise [he:proprelat-03], the relation $$R$$ is reflexive, antisymmetric, and transitive.

We obtain these conclusions:

Anyone and himself (or herself) must have the same last name, hence, $$W$$ is reflexive, which immediately implies that $$W$$ cannot be irreflexive.

If two people $$a$$ and $$b$$ have the same last name, then so are $$b$$ and $$a$$. Thus, $$W$$ is symmetric.

It is not antisymmetric. For example, John Doe and Jane Doe are two different persons having the same last name.

It is obvious that $$W$$ is transitive.

This relation is reflexive, symmetric, and transitive.

### Section [sec:equivrelat]

1. The proof is similar to Example [eg:relmod4].

2. The proof is similar to Example [eg:relmod4].

3. $$, , , , , $$.

4. $$, , , \ldots , [n-1]$$.

5. Example [eg:proprelat-04]: $$=\Q$$, and $$[x]=x\Q$$, where $$x$$ is any irrational number.

Example [eg:proprelat-06]: $$$$ and $$$$.

Hands-On Exercise [he:proprelat-02]: $$=\R^+$$, and $$[-1]=\R^-$$.

Hands-On Exercise [he:proprelat-06]: each equivalence class consists of individuals with the same last name.

6. Since $$x-x=0$$ is an integer, we find $$x\sim x$$, hence, $$\sim$$ is reflexive. If $$x\sim y$$, then $$x-y=m$$ for some integer $$m$$. It follows that $$y-x=-(x-y)=-m$$, where $$-m$$ is an integer. Hence, $$y\sim x$$ as well, which means $$\sim$$ is symmetric. If $$x\sim y$$ and $$y\sim z$$, then $$x-y=m$$ and $$y-z=n$$ for some integers $$m$$ and $$n$$. Then $x-z = (x-y)+(y-z) = m+n$ is an integer. Hence, $$x\sim z$$, which means $$\sim$$ is transitive. Therefore, $$\sim$$ is an equivalence relation.

7. The proof is identical to that of Hands-On Exercise [he:samedec]. However, $$-2.14\notin[5.14]$$, because $$5.14-(-2.14)=7.28\notin\Z$$.

8. Two points are related if they both lie on the same line $$y=5x+b$$ for some specific $$b$$. To obtain a more precise formulation, let $$(x_1,y_1)$$ and $$(x_2,y_2)$$ be the two points. Then $$y_1=5x_1+b$$ and $$y_2=5x_2+b$$. Since $$b$$ is fixed, we find $$b=y_1-5x_1=y_2-5x_2$$. Therefore $(x_1,y_1)\sim(x_2,y_2) \Leftrightarrow y_1-5x_1=y_2-5x_2$ is the relation induced by the partition.

9. From the incidence matrix \begin{array}{cc} & \begin{array}{*{6}{c}} 1 & 2 & 3 & 4 & 5 & 6 \end{array} \\ \noalign{\medskip} \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \end{array} & \left(\begin{array}{*{6}{c}} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 \end{array}\right) \end{array} % \qquad\leadsto\qquad % \begin{array}{cc} & \begin{array}{*{6}{c}} 1 & 4 & 2 & 5 & 6 & 3 \end{array} \\ \noalign{\medskip} \begin{array}{c} 1 \\ 4 \\ 2 \\ 5 \\ 6 \\ 2 \end{array} & \left(\begin{array}{cc|ccc|c} 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 \\ \hline 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right) \end{array} it is clear that the relation $$S$$ is an equivalence relation, and its equivalence classes are $$ = \{1,4\}$$, $$ = \{2,5,6\}$$, and $$ = \{3\}$$.

10. $$\big\{(a,a),(a,d),(b,b),(b,c),(b,g),(c,b),(c,c),(c,g),(d,a),(d,d),$$

$$(e,e),(e,f),(f,e),(f,f),(g,b),(g,c),(g,g)\big\}$$

### Section [sec:ordering]

1. The “divides” relation is reflexive and transitive over $$\Z^*$$, but it is not antisymmetric. For example, $$(-2)\mid 2$$, and $$2\mid(-2)$$; yet $$-2\neq 2$$.

2. The relation $$\sqsubseteq$$ is reflexive and transitive, but not antisymmetric. For example, $$\{a,b\}\sqsubseteq \{b\}$$, and $$\{b\} \sqsubseteq \{a,b\}$$; yet $$\{a,b\}\neq\{b\}$$.

3. The Hasse diagram is displayed below, on the left.

(230,225)(-30,0) (50,20)(50,50)3(0,0)(-50,50)2(-1,1)30 (70,20)(50,50)2(0,0)(-50,50)3( 1,1)30 ( 50, 0)(20,20)1 ( 0, 50)(20,20)2 (-50,100)(20,20)4 (100, 50)(20,20)3 ( 50,100)(20,20)6 ( 0,150)(20,20)12 (150,100)(20,20)9 (100,150)(20,20)18 ( 50,200)(20,20)36

1in

(20,225)(0,0) (10,20)(0,50)4(0,1)30 (0, 0)(20,20)1 (0, 50)(20,20)2 (0,100)(20,20)4 (0,150)(20,20)8 (0,200)(20,20)16

4. The Hasse diagram is displayed above, on the right.

5. The Hasse diagram for the poset $$(\wp(\{a,b,c\}),\subseteq)$$ is shown below.

(180,230) (80,20)(80, 70)2(0,0)( 0,70)2(-6,5)60 (20,90)(80,-70)2(0,0)( 0,70)2( 6,5)60 (10,90)(80,-70)2(0,0)(80,70)2( 0,1)50 ( 80, 0)(20,20)$$\emptyset$$ ( 0, 70)(20,20)$$\{a\}$$ ( 80, 70)(20,20)$$\{b\}$$ (160, 70)(20,20)$$\{c\}$$ (-10,140)(40,20)$$\{a,b\}$$ ( 70,140)(40,20)$$\{a,c\}$$ (150,140)(40,20)$$\{b,c\}$$ ( 70,210)(40,20)$$\{a,b,c\}$$

### Section [sec:addmult]

1. 7, 11.

2. Let $$A$$ and $$B$$ denote the sets of people who attended the two games, then we are looking for the value of $$|A\cup B|$$. Since $$|A|=72397$$, $$|B|=69211$$ and $$|A\cap B|=45713$$, we find $|A\cup B| = |A|+|B|-|A\cap B| = 72397+69211-45713 = 95895.$ Conclusion: 95895 different people attended the two games.

3. This time, we have $$|A|=72397$$, $$|B|=69211$$ and $$|A\cup B|=93478$$, hence, $|A\cap B| = |A|+|B|-|A\cup B| = 72397+69211-93478 = 48130.$ Conclusion: 48130 people attended both games.

4. The answer is $$(47+43+32)-(33+27+25)-22 = 59$$.

5. 100000.

6. 999.

7. $$9\cdot9\cdot8\cdot7\cdot6\cdot5 = 136080$$.

8. There are $$9\cdot10\cdot10=900$$ natural numbers with 3 digits. Among them there are 10 of the form $$44x$$, and 9 of the form $$x44$$, for some digit $$x$$. However, 444 is counted in both groups, so there are actually $$10+9-1=18$$ integers with repeated 4s. Hence, the number of 3-digit natural numbers that do not have repeated 4s is $$900-18=882$$.

9. (a) There are 26 choices each for the first two letters, and 10 choices for each of the remaining four digits. Hence, there are $$26^2\cdot10^4$$ choices for the PINs.

(b) There are seven cases: from 0 to 6 digits following the first two letters, thus the total count is $$26^2(1+10+10^2+\cdots+10^6) = 26^2(10^7-1)/9$$.

(c) Similar to (b), the total number of PINS equals to $$26^2(10^2+10^3+\cdots+10^6) = 26^2\cdot10^2(1+10+\cdots+10^4) = 260^2(10^5-1)/9$$.

### Section [sec:perm]

1. $$21\cdot20\cdot19\cdot18 = 143640$$.

2. $$6\cdot5\cdot4\cdot3 = P(6,4) = 360$$.

3. $$15^5$$; $$15\cdot14\cdot13\cdot12\cdot11 = P(15,5) = 360360$$.

4. $$7! = 5040$$.

5. $$7!/2 = 2520$$.

### Section [sec:combin]

1. $$\comb{12}{3} = \frac{12\cdot11\cdot10}{3\cdot2\cdot1} = 2\cdot11\cdot10 = 220$$.

2. The order in which the committee members are selected does not matter. This problem essentially counts the number of 3-element subsets. The answer is $$\comb{7}{3}$$.

3. There are $$\comb{23}{5}$$ subsets with 5 elements.

4. $$\comb{529}{525} = \comb{529}{4} = \frac{529\cdot528\cdot527\cdot526}{4\cdot3\cdot2\cdot1} = 3226076876$$.

5. $$\comb{8}{5}$$.

6. $$P(10,4)$$.

7. $$\comb{52}{13}$$.

8. A bridge hand is a 13-element subset, so it is a combination problem. The four spades can be chosen in $$\comb{13}{4}$$ ways. The remaining nine cards must be selected from the remaining 39 cards (the non-spades), hence, they can be chosen in $$\comb{39}{9}$$ ways. Together, we determine that the number of bridge hands with exactly four spades is $$\comb{13}{4}\comb{39}{9}$$. Note that the upper numbers add up to 52, the total number of cards available, and the lower numbers add up to 13, the total number of cards selected.

9. The spades can be selected in $$\comb{13}{4}$$ ways, and the hearts in $$\comb{13}{4}$$ ways. The remaining five cards must be selected from the remaining 26 cards other than spades and hearts, they can be selected in $$\comb{26}{5}$$ ways. Hence, there are $$\comb{13}{4} \comb{13}{4} \comb{26}{5}$$. Again, take note that the upper numbers add up to 52, and the lower numbers add up to 13.

10. Following the same approach in the last two hands-on exercises, we find the total number to be $$\comb{13}{4} \comb{13}{3} \comb{13}{3} \comb{13}{3}$$, which can be written as $$\comb{13}{4}\comb{13}{3}^3$$.

11. There are $$\comb{8}{2}$$ ways to choose the two blue balls. The other three balls must be either red or green, so we have to choose 3 balls from $$6+5=11$$ balls. There are $$\comb{11}{3}$$ choices. Together, there are $$\comb{8}{2} \comb{11}{3}$$ selections with exactly two blue balls.

12. This is a combination problem, because we are selecting soda cans without worrying about the order of selection.

(a) The 4 cans of Pepsi can be selected in $$\comb{8}{4}$$ ways. The other 6 cans can be selected from the remaining 16 cans, and there are $$\comb{16}{6}$$ ways to do so. The total number of selections is therefore $$\comb{8}{4}\comb{16}{6}$$. Note that the upper numbers add up to 24, the total number of soda cans, and the lower numbers add up to 10, the number of cans selected.

(b) “At least 4 cans of Pepsi” means we can choose from 4 to 8 cans. Following the argument used above, the number of selections is $\comb{8}{4}\comb{16}{6} + \comb{8}{5}\comb{16}{5} + \comb{8}{6}\comb{16}{4} + \comb{8}{7}\comb{16}{3} + \comb{8}{8}\comb{16}{2},$ which can be written as $$\sum_{k=4}^8 \comb{8}{k}\comb{16}{10-k}$$.

(c) This time, the number of Pepsi is between 0 to 4 cans. The number of selections is $\comb{8}{0}\comb{16}{10}+ \comb{8}{1}\comb{16}{9} + \comb{8}{2}\comb{16}{8} + \comb{8}{3}\comb{16}{7} + \comb{8}{4}\comb{16}{6},$ or simply $$\sum_{k=0}^4 \comb{8}{k} \comb{16}{10-k}$$.

(d) This is a more elaborate version of the previous problems. The 3 Pepsi cans can be selected in $$\comb{8}{3}$$. Now we have to pick the other 7 cans. The number of Sprite could vary from 0 to 3 cans. Once we have picked the Sprite cans, the other cans must be selected from the remaining 9 cans of Dr. Pepper and Mountain Dew. Thus, the total count is $\comb{8}{3}\,\left[ \comb{7}{0}\comb{9}{7} + \comb{7}{1}\comb{9}{6} + \comb{7}{2}\comb{9}{5} + \comb{7}{3}\comb{9}{4} \right].$ Using the sigma notation, we can write $$\comb{8}{3} \sum_{k=0}^3 \comb{7}{k} \comb{9}{7-k}$$.

### Section [sec:binom]

1. $$81x^4-540x^3y+1350x^2y^2-1500xy^3+625y^4$$.

2. Since $$(1+3t)^8 = \sum_{k=0}^8 \comb{8}{k} (3t)^k$$, we need $$k=5$$. The coefficient is $$\comb{8}{5}\,3^5$$.

3. Since $$(2-5t)^9 = \sum_{k=0}^9 \comb{9}{k} 2^{9-k} (-5t)^k$$, we need $$k=4$$, which implies that the coefficient of $$t^4$$ is $$\comb{9}{4}\, 2^5\cdot(-5)^4$$.

4. Since $$(3-2t^3)^8 = \sum_{k=0}^8 \comb{8}{k} 3^{8-k} (-2t^3)^k = \sum_{k=0}^8 \comb{8}{k} 3^{8-k}(-2)^k t^{3k}$$, we need $$3k=9$$, or $$k=3$$. The coefficient is $$\comb{8}{3} 3^5 (-2)^3$$.

5. Since $\left(x+\frac{3}{x}\right)^9 = \sum_{k=0}^9 \comb{9}{k} x^{9-k} \left(\frac{3}{x}\right)^k = \sum_{k=0}^9 \comb{9}{k} 3^k x^{9-2k},$ we need $$9-2k=0$$, which has no integral solutions. Hence, the constant term in $$(x+3/x)^9$$ is zero.

For the second problem, since $\left(2x-\frac{3}{x}\right)^{10} = \sum_{k=0}^{10} \comb{10}{k}(2x)^{10-k}\left(-\frac{3}{x}\right)^k = \sum_{k=0}^{10} \comb{10}{k} 2^{10-k}(-3)^k x^{10-2k},$ we need $$10-2k=0$$ or $$k=5$$. The constant term is $$\comb{10}{5} 2^5 (-3)^5$$.

6. $$\comb{12}{8}\cdot2^8-2\comb{12}{7}\cdot2^7+3\comb{12}{6}\cdot266$$.

7. The 7th, 8th, and 9th rows of Pascal’s triangle are displayed below. $\begin{array}{*{19}{c}} & & 1 & & 7 & &21 & &35 & &35 & &21 & & 7 & &1 \\ &1 & & 8 & &28& &56 & &70 & &56 & &28 & & 8 & &1 \\ 1& & 9 & &36 & &84 & &126& &126& &84 & &36 & &9 & &1 \end{array}$