###### 1.

If $A = \{ a, b, c \}\text{,}$ $B = \{ 1, 2, 3 \}\text{,}$ $C = \{ x \}\text{,}$ and $D = \emptyset\text{,}$ list all of the elements in each of the following sets.

1. $\displaystyle A \times B$

2. $\displaystyle B \times A$

3. $\displaystyle A \times B \times C$

4. $\displaystyle A \times D$

Hint

(a) $A \times B = \{ (a,1), (a,2), (a,3), (b,1), (b,2), (b,3), (c,1), (c,2), (c,3) \}\text{;}$ (d) $A \times D = \emptyset\text{.}$

###### 2.

Find an example of two nonempty sets $A$ and $B$ for which $A \times B = B \times A$ is true.

###### 3.

Prove $A \cup \emptyset = A$ and $A \cap \emptyset = \emptyset\text{.}$

###### 4.

Prove $A \cup B = B \cup A$ and $A \cap B = B \cap A\text{.}$

###### 5.

Prove $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\text{.}$

Hint

If $x \in A \cup (B \cap C)\text{,}$ then either $x \in A$ or $x \in B \cap C\text{.}$ Thus, $x \in A \cup B$ and $A \cup C\text{.}$ Hence, $x \in (A \cup B) \cap (A \cup C)\text{.}$ Therefore, $A \cup (B \cap C) \subset (A \cup B) \cap (A \cup C)\text{.}$ Conversely, if $x \in (A \cup B) \cap (A \cup C)\text{,}$ then $x \in A \cup B$ and $A \cup C\text{.}$ Thus, $x \in A$ or $x$ is in both $B$ and $C\text{.}$ So $x \in A \cup (B \cap C)$ and therefore $(A \cup B) \cap (A \cup C) \subset A \cup (B \cap C)\text{.}$ Hence, $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\text{.}$

###### 6.

Prove $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\text{.}$

###### 7.

Prove $A \subset B$ if and only if $A \cap B = A\text{.}$

###### 8.

Prove $(A \cap B)' = A' \cup B'\text{.}$

###### 9.

Prove $A \cup B = (A \cap B) \cup (A \setminus B) \cup (B \setminus A)\text{.}$

Hint

$(A \cap B) \cup (A \setminus B) \cup (B \setminus A) = (A \cap B) \cup (A \cap B') \cup (B \cap A') = [A \cap (B \cup B')] \cup (B \cap A') = A \cup (B \cap A') = (A \cup B) \cap (A \cup A') = A \cup B\text{.}$

###### 10.

Prove $(A \cup B) \times C = (A \times C ) \cup (B \times C)\text{.}$

###### 11.

Prove $(A \cap B) \setminus B = \emptyset\text{.}$

###### 12.

Prove $(A \cup B) \setminus B = A \setminus B\text{.}$

###### 13.

Prove $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)\text{.}$

Hint

$A \setminus (B \cup C) = A \cap (B \cup C)' = (A \cap A) \cap (B' \cap C') = (A \cap B') \cap (A \cap C') = (A \setminus B) \cap (A \setminus C)\text{.}$

###### 14.

Prove $A \cap (B \setminus C) = (A \cap B) \setminus (A \cap C)\text{.}$

###### 15.

Prove $(A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)\text{.}$

###### 16.

Which of the following relations $f: {\mathbb Q} \rightarrow {\mathbb Q}$ define a mapping? In each case, supply a reason why $f$ is or is not a mapping.

1. $\displaystyle \displaystyle f(p/q) = \frac{p+ 1}{p - 2}$

2. $\displaystyle \displaystyle f(p/q) = \frac{3p}{3q}$

3. $\displaystyle \displaystyle f(p/q) = \frac{p+q}{q^2}$

4. $\displaystyle \displaystyle f(p/q) = \frac{3 p^2}{7 q^2} - \frac{p}{q}$

Hint

(a) Not a map since $f(2/3)$ is undefined; (b) this is a map; (c) not a map, since $f(1/2) = 3/4$ but $f(2/4)=3/8\text{;}$ (d) this is a map.

###### 17.

Determine which of the following functions are one-to-one and which are onto. If the function is not onto, determine its range.

1. $f: {\mathbb R} \rightarrow {\mathbb R}$ defined by $f(x) = e^x$

2. $f: {\mathbb Z} \rightarrow {\mathbb Z}$ defined by $f(n) = n^2 + 3$

3. $f: {\mathbb R} \rightarrow {\mathbb R}$ defined by $f(x) = \sin x$

4. $f: {\mathbb Z} \rightarrow {\mathbb Z}$ defined by $f(x) = x^2$

Hint

(a) $f$ is one-to-one but not onto. $f({\mathbb R} ) = \{ x \in {\mathbb R} : x \gt 0 \}\text{.}$ (c) $f$ is neither one-to-one nor onto. $f(\mathbb R) = \{ x : -1 \leq x \leq 1 \}\text{.}$

###### 18.

Let $f :A \rightarrow B$ and $g : B \rightarrow C$ be invertible mappings; that is, mappings such that $f^{-1}$ and $g^{-1}$ exist. Show that $(g \circ f)^{-1} =f^{-1} \circ g^{-1}\text{.}$

###### 19.
1. Define a function $f: {\mathbb N} \rightarrow {\mathbb N}$ that is one-to-one but not onto.

2. Define a function $f: {\mathbb N} \rightarrow {\mathbb N}$ that is onto but not one-to-one.

Hint

(a) $f(n) = n + 1\text{.}$

###### 20.

Prove the relation defined on ${\mathbb R}^2$ by $(x_1, y_1 ) \sim (x_2, y_2)$ if $x_1^2 + y_1^2 = x_2^2 + y_2^2$ is an equivalence relation.

###### 21.

Define a function on the real numbers by

\begin{equation*} f(x) = \frac{x + 1}{x - 1}\text{.} \end{equation*}

What are the domain and range of $f\text{?}$ What is the inverse of $f\text{?}$ Compute $f \circ f^{-1}$ and $f^{-1} \circ f\text{.}$

Hint

$f^{-1}(x) = (x+1)/(x-1)\text{.}$

###### 22.

Let $f: X \rightarrow Y$ be a map with $A_1, A_2 \subset X$ and $B_1, B_2 \subset Y\text{.}$

1. Prove $f( A_1 \cup A_2 ) = f( A_1) \cup f( A_2 )\text{.}$

2. Prove $f( A_1 \cap A_2 ) \subset f( A_1) \cap f( A_2 )\text{.}$ Give an example in which equality fails.

3. Prove $f^{-1}( B_1 \cup B_2 ) = f^{-1}( B_1) \cup f^{-1}(B_2 )\text{,}$ where

\begin{equation*} f^{-1}(B) = \{ x \in X : f(x) \in B \}\text{.} \end{equation*}
4. Prove $f^{-1}( B_1 \cap B_2 ) = f^{-1}( B_1) \cap f^{-1}( B_2 )\text{.}$

5. Prove $f^{-1}( Y \setminus B_1 ) = X \setminus f^{-1}( B_1)\text{.}$

Hint

(a) Let $y \in f(A_1 \cup A_2)\text{.}$ Then there exists an $x \in A_1 \cup A_2$ such that $f(x) = y\text{.}$ Hence, $y \in f(A_1)$ or $f(A_2) \text{.}$ Therefore, $y \in f(A_1) \cup f(A_2)\text{.}$ Consequently, $f(A_1 \cup A_2) \subset f(A_1) \cup f(A_2)\text{.}$ Conversely, if $y \in f(A_1) \cup f(A_2)\text{,}$ then $y \in f(A_1)$ or $f(A_2)\text{.}$ Hence, there exists an $x$ in $A_1$ or $A_2$ such that $f(x) = y\text{.}$ Thus, there exists an $x \in A_1 \cup A_2$ such that $f(x) = y\text{.}$ Therefore, $f(A_1) \cup f(A_2) \subset f(A_1 \cup A_2)\text{,}$ and $f(A_1 \cup A_2) = f(A_1) \cup f(A_2)\text{.}$

###### 23.

Show that an $m \times n$ matrix gives rise to a well-defined map from ${\mathbb R}^n$ to ${\mathbb R}^m\text{.}$

###### 24.

Find the error in the following argument by providing a counterexample. “The reflexive property is redundant in the axioms for an equivalence relation. If $x \sim y\text{,}$ then $y \sim x$ by the symmetric property. Using the transitive property, we can deduce that $x \sim x\text{.}$”

Hint

Let $X = {\mathbb N} \cup \{ \sqrt{2}\, \}$ and define $x \sim y$ if $x + y \in {\mathbb N}\text{.}$

###### 25.Projective Real Line.

Define a relation on ${\mathbb R}^2 \setminus \{ (0,0) \}$ by letting $(x_1, y_1) \sim (x_2, y_2)$ if there exists a nonzero real number $\lambda$ such that $(x_1, y_1) = ( \lambda x_2, \lambda y_2)\text{.}$ Prove that $\sim$ defines an equivalence relation on ${\mathbb R}^2 \setminus (0,0)\text{.}$ What are the corresponding equivalence classes? This equivalence relation defines the projective line, denoted by ${\mathbb P}({\mathbb R}) \text{,}$ which is very important in geometry.

###### 26.

Prove that

\begin{equation*} 1^2 + 2^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6} \end{equation*}

for $n \in {\mathbb N}\text{.}$

Hint

The base case, $S(1): [1(1 + 1)(2(1) + 1)]/6 = 1 = 1^2$ is true. Assume that $S(k): 1^2 + 2^2 + \cdots + k^2 = [k(k + 1)(2k + 1)]/6$ is true. Then

\begin{align*} 1^2 + 2^2 + \cdots + k^2 + (k + 1)^2 & = [k(k + 1)(2k + 1)]/6 + (k + 1)^2\\ & = [(k + 1)((k + 1) + 1)(2(k + 1) + 1)]/6\text{,} \end{align*}

and so $S(k + 1)$ is true. Thus, $S(n)$ is true for all positive integers $n\text{.}$

###### 27.

Prove that

\begin{equation*} 1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n + 1)^2}{4} \end{equation*}

for $n \in {\mathbb N}\text{.}$

###### 28.

Prove that $n! \gt 2^n$ for $n \geq 4\text{.}$

Hint

The base case, $S(4): 4! = 24 \gt 16 =2^4$ is true. Assume $S(k): k! \gt 2^k$ is true. Then $(k + 1)! = k! (k + 1) \gt 2^k \cdot 2 = 2^{k + 1}\text{,}$ so $S(k + 1)$ is true. Thus, $S(n)$ is true for all positive integers $n\text{.}$

###### 29.

Prove that

\begin{equation*} x + 4x + 7x + \cdots + (3n - 2)x = \frac{n(3n - 1)x}{2} \end{equation*}

for $n \in {\mathbb N}\text{.}$

###### 30.

Prove that $10^{n + 1} + 10^n + 1$ is divisible by $3$ for $n \in {\mathbb N}\text{.}$

###### 31.

Prove that $4 \cdot 10^{2n} + 9 \cdot 10^{2n - 1} + 5$ is divisible by $99$ for $n \in {\mathbb N}\text{.}$

###### 32.

Show that

\begin{equation*} \sqrt[n]{a_1 a_2 \cdots a_n} \leq \frac{1}{n} \sum_{k = 1}^{n} a_k\text{.} \end{equation*}
###### 33.

Prove the Leibniz rule for $f^{(n)} (x)\text{,}$ where $f^{(n)}$ is the $n$th derivative of $f\text{;}$ that is, show that

\begin{equation*} (fg)^{(n)}(x) = \sum_{k = 0}^{n} \binom{n}{k} f^{(k)}(x) g^{(n - k)}(x)\text{.} \end{equation*}
Hint

Follow the proof in Example 1.34 .

###### 34.

Use induction to prove that $1 + 2 + 2^2 + \cdots + 2^n = 2^{n + 1} - 1$ for $n \in {\mathbb N}\text{.}$

###### 35.

Prove that

\begin{equation*} \frac{1}{2}+ \frac{1}{6} + \cdots + \frac{1}{n(n + 1)} = \frac{n}{n + 1} \end{equation*}

for $n \in {\mathbb N}\text{.}$

###### 36.

If $x$ is a nonnegative real number, then show that $(1 + x)^n - 1 \geq nx$ for $n = 0, 1, 2, \ldots\text{.}$

Hint

The base case, $S(0): (1 + x)^0 - 1 = 0 \geq 0 = 0 \cdot x$ is true. Assume $S(k): (1 + x)^k -1 \geq kx$ is true. Then

\begin{align*} (1 + x)^{k + 1} - 1 & = (1 + x)(1 + x)^k -1\\ & = (1 + x)^k + x(1 + x)^k - 1\\ & \geq kx + x(1 + x)^k\\ & \geq kx + x\\ & = (k + 1)x\text{,} \end{align*}

so $S(k + 1)$ is true. Therefore, $S(n)$ is true for all positive integers $n\text{.}$

###### 37.Power Sets.

Let $X$ be a set. Define the power set of $X\text{,}$ denoted ${\mathcal P}(X)\text{,}$ to be the set of all subsets of $X\text{.}$ For example,

\begin{equation*} {\mathcal P}( \{a, b\} ) = \{ \emptyset, \{a\}, \{b\}, \{a, b\} \}\text{.} \end{equation*}

For every positive integer $n\text{,}$ show that a set with exactly $n$ elements has a power set with exactly $2^n$ elements.

###### 38.

Prove that the two principles of mathematical induction stated in Section 1.4 are equivalent.

###### 39.

Show that the Principle of Well-Ordering for the natural numbers implies that 1 is the smallest natural number. Use this result to show that the Principle of Well-Ordering implies the Principle of Mathematical Induction; that is, show that if $S \subset {\mathbb N}$ such that $1 \in S$ and $n + 1 \in S$ whenever $n \in S\text{,}$ then $S = {\mathbb N}\text{.}$

###### 40.Fibonacci Numbers.

The Fibonacci numbers are

\begin{equation*} 1, 1, 2, 3, 5, 8, 13, 21, \ldots\text{.} \end{equation*}

We can define them inductively by $f_1 = 1\text{,}$ $f_2 = 1\text{,}$ and $f_{n + 2} = f_{n + 1} + f_n$ for $n \in {\mathbb N}\text{.}$

1. Prove that $f_n \lt 2^n\text{.}$

2. Prove that $f_{n + 1} f_{n - 1} = f^2_n + (-1)^n\text{,}$ $n \geq 2\text{.}$

3. Prove that $f_n = [(1 + \sqrt{5}\, )^n - (1 - \sqrt{5}\, )^n]/ 2^n \sqrt{5}\text{.}$

4. Show that $\lim_{n \rightarrow \infty} f_n / f_{n + 1} = (\sqrt{5} - 1)/2\text{.}$

5. Prove that $f_n$ and $f_{n + 1}$ are relatively prime.

Hint

For (a) and (b) use mathematical induction. (c) Show that $f_1 = 1\text{,}$ $f_2 = 1\text{,}$ and $f_{n + 2} = f_{n + 1} + f_n\text{.}$ (d) Use part (c). (e) Use part (b) and Exercise 6.1.5.2 .