Review Sheet for the Final

Math 310

These problems are provided to help you study. The presence of a problem on this handout does not imply that there will be a similar problem on the test. And the absence of a topic does not imply that it won't appear on the test.

1. (a) Negate the following statement, simplifying so that only simple statements are negated:

$$\lnot P \ifthen (P \land Q).$$

(b) Negate the following statement, simplifying so that only simple statements are negated:

$$\forall x \exists y (x > y \lor x \le 0).$$

(c) Negate the following statement, simplifying so that only simple statements are negated, and write your answer in words:

"Every soccer fan either likes pizza or dislikes writing proofs."

2. (a) Prove or disprove by specific counterexample: If x is rational and y is irrational, then $x y$ is irrational.

(b) Prove or disprove by specific counterexample: If x is rational and y is rational, then $x y$ is irrational.

3. Show that $\lnot(P \ifthen Q) \lor (\lnot Q \ifthen\,\lnot P)$ is a tautology.

4. Prove that $\displaystyle \lim_{x \to 3} (x^2 - 4) = 5$ .

5. Prove that $\displaystyle \lim_{x \to 3} \dfrac{x + 3}{x - 2} = 6$ .

6. Prove: $\lnot C$ .

Premises: $\left\{\matrix{A \ifthen (B \land D) \cr D \ifthen\,\lnot C \cr (\lnot B \lor C) \ifthen A \cr}\right.$

7. Prove that if $x \in \real$ , then

$$-7 \le |x + 4| - |x - 3| \le 7.$$

8. Show that there do not exist real numbers x and y such that

$$x^2 - x + y^2 - 3 y + 3 = 0.$$

9. The Fibonacci numbers are defined recursively by

$$f_0 = 1, \quad f_1 = 1, \quad f_n = f_{n-1} + f_{n-2} \quad\hbox{for}\quad n > 1.$$

Prove that for $n \ge 0$ ,

$$f_0^2 + f_1^2 + \cdots + f_n^2 = f_n f_{n+1}.$$

10. Prove that if $n \ge 1$ , then

$$1 \cdot 5 + 2 \cdot 6 + 3 \cdot 7 + \cdots + n(n + 4) = \dfrac{n(n + 1)(2 n + 13)}{6}.$$

11. Prove that the sum of the cubes of three consecutive positive integers is divisible by 9.

12. A sequence of integers is defined by

$$x_0 = 6, \quad x_1 = 17,$$

$$x_n = x_{n - 1} + 12 x_{n - 2} \quad\hbox{for}\quad n \ge 2.$$

Prove that

$$x_n = 5 \cdot 4^n + (-3)^n \quad\hbox{for}\quad n \ge 0.$$

13. Prove that if $n \ge 4$ , then

$$(2 n)! \ge 10^n.$$

14. Suppose that A is a set and $|A| = 3$ . Which set has more elements --- $\powerset(A)$ or $A \times A$ ?

15. Let A and B be sets. Prove that $(A - B) \cap (B - A) = \emptyset$ .

16. Let A, B, and C be sets.

(a) Draw a general Venn diagram for $A - (B - C)$ .

(b) Prove that $A - (B - C) = (A \cap C) \cup (A - B)$ .

17. Prove that $[-1, 2] \cup [0, 4] = [-1, 4]$ .

18. Prove that $(-4, 6) \cap (1, 8) = (1, 6)$ .

19. In each case, give a counterexample to the statement.

(a) "If $n \in \integer$ , then $n^2 + 120 \ge 22 n$ ."

(b) "If $\der {} x f(x) = 3 x^2 + 4 x$ , then $f(x) = x^3 + 2 x^2$ ."

(c) "If a, b, and c are positive integers, then $(a^b)^c = a^(b^c)$ ."

20. Bonzo McTavish observes that if n is an integer, then

$$2\cdot (2 n + 3) + (-4)\cdot (n + 1) = 2.$$

He concludes that $(2 n + 3, n + 1)$ is either 1 or 2. Can $(2 n + 3, n + 1) = 2$ ? Why or why not?

21. Define $f: \real^2 \to \real^2$ by

$$f(x, y) = (x + y^3, x^2).$$

Prove by example that f is neither injective nor surjective.

22. Define $g: \real^2 \to \real^2$ by

$$g(x, y) = (x + y^3, x^3).$$

Prove that g is bijective by:

(a) Proving that g is injective and surjective.

(b) Constructing an inverse for g.

23. Define $h: \real^2 \to \real^2$ by

$$h(x, y) = (x + 3 y + 2, x^3 + 5).$$

Prove that h is surjective.

24. Define $f: \real \to \real$ by

$$f(x) = 2 e^x + x^3 + 4 x + \sin x.$$

Prove that f is injective.

25. Define $f: \real \to \real$ by

$$f(x) = 2 x^3 + \tan^{-1} x.$$

Prove that f is surjective.

26. Prove that $\{0, 1\} \times \real$ has the same cardinality as $\real$ .

27. Prove by constructing a bijection that $|[-1, 3]| = |[3, 5]|$ .

28. Prove that $[1, 4] \cup (5, 6)$ has the same cardinality as $(2, 3) \cup \{7\}$ .

29. Define a relation on $\real$ by

$$x \sim y \quad\hbox{means}\quad (\sin x)(\sin y) \ge 0.$$

Take each axiom for an equivalence relation. If the axiom holds, prove it; if the axiom does not hold, give a counterexample.

30. Consider the equivalence relation defined by writing $x \sim y$ to mean $x = y \mod{3}$ on the set

$$S = \{-3, -2, 0, 2, 4, 5, 6, 10, 17, 18, 22\}.$$

List the elements of the equivalence classes.

31. A relation is defined on $\real^2$ by

$$(a, b) \sim (c, d) \quad \iff \quad a |d| = c |b|.$$

Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom doesn't hold, give a specific counterexample.

32. Define a relation $\sim$ on $\real$ by

$$x \sim y \quad\hbox{means}\quad x^3 - x \le y^3 - y.$$

Check each axiom for a partial order. If the axiom holds, prove it; if the axiom does not hold, give a counterexample.

33. Define a relation $\sim$ on $\real^2$ by

$$(a, b) \sim (c, d) \quad\hbox{means}\quad ab \ge cd.$$

Check each axiom for a partial order. If the axiom holds, prove it; if the axiom does not hold, give a counterexample.

34. Prove that the square of an odd number leaves a remainder of 1 when it's divided by 4.

35. Prove that if n is an integer, then $n^2 + n + 3$ does not leave a remainder of 1 or 2 when it's divided by 5.

36. Prove that if $m, n \in \integer$ and neither m nor n is divisible by 3, then $m^2 + n^2$ is not divisible by 3.

37. Compute $(1021, 129)$ .

38. Using the fact that $(x, y) = m x + n y$ for some $m, n \in \integer$ , prove:

(a) If d is a common divisor of a and b, then $d \mid (a, b)$ .

(b) If $a, b, c \in \integer$ and $a > 0$ , then $(a b, a c) = a (b,c)$ .

39. If $a, b, m, n \in \integer$ and $a m + b n = 6$ , does it follow that $(m, n) = 6$ ?

40. Prove that if $n \in \integer$ , then $(2 n^2 + 8 n + 1, n + 4) = 1$ .

41. Prove that if $x, y > 0$ , then $x^2 + \dfrac{y^2}{x^2} \ge 2 y$ .

42. Prove that if $x > 0$ , then $x^3 + e^{2 x} > 1$ .

43. Prove that if $x > 0$ , then

$$x \ln x \ge x - 1.$$

[Hint: Find the absolute min of $f(x) = x \ln x - x + 1$ .]

44. Use the limit definition to prove that

$$\lim_{x \to \infty} \dfrac{8 x^3 + 1}{2 x^3} = 4.$$

45. Phoebe Small has proved that

$$\bigcup_{n=1}^\infty \left[0, \dfrac{n}{n + 6}\right] = [0, 1).$$

But Bonzo McTavish is confused. "The point 0.9 is in $[0, 1]$ . But for $n = 1$ , the interval $\left[0, \dfrac{n}{n + 6}\right]$ is $\left[0, \dfrac{1}{7}\right]$ , and that doesn't contain 0.9." Does Bonzo have a valid objection?

46. Prove that $\displaystyle \bigcap_{n=1}^\infty [1, 2 + e^{-n}] = [1, 2]$ .

Solutions to the Review Sheet for the Final

1. (a) Negate the following statement, simplifying so that only simple statements are negated:

$$\lnot P \ifthen (P \land Q).$$

(b) Negate the following statement, simplifying so that only simple statements are negated:

$$\forall x \exists y (x > y \lor x \le 0).$$

(c) Negate the following statement, simplifying so that only simple statements are negated, and write your answer in words:

"Every soccer fan either likes pizza or dislikes writing proofs."

(a)

$$\matrix{\lnot[\lnot P \ifthen (P \land Q)] & \iff & \lnot[P \lor (P \land Q)] & \hbox{(Conditional disjunction)} \cr & \iff & \lnot P \land \lnot(P \land Q) & \hbox{(DeMorgan)} \cr & \iff & \lnot P \land (\lnot P \lor \lnot Q) & \hbox{(DeMorgan)} \quad\halmos \cr}$$

(b)

$$\matrix{\lnot[\forall x \exists y (x > y \lor x \le 0)] & \iff & \exists x \forall y \lnot (x > y \lor x \le 0) & \hbox{(Negating quantifiers)} \cr & \iff & \exists x \forall y (x \le y \land x > 0) & \hbox{(DeMorgan)} \quad\halmos \cr}$$

(c) Let

$S(x)$ mean "x is a soccer fan."

$P(x)$ mean "x likes pizza."

$W(x)$ means "x likes writing proofs."

The original statement is $\forall x [S(x) \ifthen (P(x) \lor \lnot W(x))]$ . Negate it:

$$\matrix{\lnot(\forall x [S(x) \ifthen (P(x) \lor \lnot W(x))]) & \iff & \exists x \lnot [S(x) \ifthen (P(x) \lor \lnot W(x))] & \hbox{(Negating a quantifier)} \cr & \iff & \exists x \lnot [\lnot S(x) \lor (P(x) \lor \lnot W(x))] & \hbox{(Conditonal disjunction)} \cr & \iff & \exists x [S(x) \land \lnot (P(x) \lor \lnot W(x))] & \hbox{(DeMorgan)} \cr & \iff & \exists x [S(x) \land (\lnot P(x) \land W(x))] & \hbox{(DeMorgan)} \cr}$$

The last statement says: "There is a soccer fan who dislikes pizza and likes writing proofs."

2. (a) Prove or disprove by specific counterexample: If x is rational and y is irrational, then $x y$ is irrational.

(b) Prove or disprove by specific counterexample: If x is rational and y is rational, then $x y$ is irrational.

(a) The claim is false. $x = 0$ is rational and $y = \sqrt{2}$ is irrational, but $x y = 0 \cdot \sqrt{2} = 0$ is rational.

(b) Suppose x is rational and y is rational. Then

$$x = \dfrac{a}{b} \quad\hbox{and}\quad y = \dfrac{c}{d}, \quad\hbox{where}\quad a, b, c, d \in \integer.$$

So

$$x y = \dfrac{a c}{b d}.$$

Since $a c, b d \in \integer$ , it follows that $x y$ is rational.

3. Show that $\lnot(P \ifthen Q) \lor (\lnot Q \ifthen\,\lnot P)$ is a tautology.

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & P & & Q & & $P \ifthen Q$ & & $\lnot(P \ifthen Q)$ & & $\lnot P$ & & $\lnot Q$ & & $\lnot Q \ifthen\,\lnot P$ & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & T & & T & & T & & F & & F & & F & & T & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & T & & F & & F & & T & & F & & T & & F & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & F & & T & & T & & F & & T & & F & & T & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & F & & F & & T & & F & & T & & T & & T & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & \cr & $\lnot(P \ifthen Q) \lor (\lnot Q \ifthen\,\lnot P)$ & \cr height2pt & \omit & \cr \noalign{\hrule} height2pt & \omit & \cr & T & \cr height2pt & \omit & \cr \noalign{\hrule} height2pt & \omit & \cr & T & \cr height2pt & \omit & \cr \noalign{\hrule} height2pt & \omit & \cr & T & \cr height2pt & \omit & \cr \noalign{\hrule} height2pt & \omit & \cr & T & \cr height2pt & \omit & \cr \noalign{\hrule} }} $$

Since the column for $\lnot(P \ifthen Q) \lor (\lnot Q \ifthen\,\lnot P)$ contains only T's, the statement is a tautology.

4. Prove that $\displaystyle \lim_{x \to 3} (x^2 - 4) = 5$ .

Let $\epsilon > 0$ . I want to find $\delta$ such that if $\delta > |x - 3| > 0$ , then $\epsilon > |(x^2 - 4) - 5|$ .

Here's the scratch work. I want $\epsilon > |x^2 - 9| = |x - 3||x + 3|$ . I can use $\delta$ to control $|x - 3|$ . To control $|x + 3|$ , assume $1 \ge \delta$ . Then $1 > |x - 3|$ , so $2 < x < 4$ . Then $5 < x + 3 < 7$ , so $|x + 3| < 7$ .

Now if I can make $\epsilon > 7|x - 3|$ , then $7|x - 3| > |x + 3||x - 3|$ gives $\epsilon > |x + 3||x - 3|$ . But $\epsilon > 7|x - 3|$ is equivalent to $\dfrac{\epsilon}{7} > |x - 3|$ , and I could get this if $\dfrac{\epsilon}{7} \ge \delta$ .

Putting my two requirements on $\delta$ together, I'll take $\delta = \min\left(1,\dfrac{\epsilon}{7}\right)$ .

Here's the real proof. Suppose $\epsilon > 0$ . Take $\delta = \min\left(1,\dfrac{\epsilon}{7}\right)$ . If $\delta > |x - 3| > 0$ , then

$$ \eqalign{ 1 \ge \delta & > |x - 3| \cr 2 < &\ x < 4 \cr 5 < &\ x + 3 < 7 \cr}$$

Therefore, $7 > |x + 3|$ .

Also, $\dfrac{\epsilon}{7} \ge \delta > |x - 3|$ . Since all the numbers involved are positive, I can multiply inequalities to get

$$\epsilon = 7 \cdot \dfrac{\epsilon}{7} > |x + 3||x - 3| = |x^2 - 9| = |(x^2 - 4) - 5|.$$

This proves that $\displaystyle \lim_{x \to 3} (x^2 - 4) = 5$ .

5. Prove that $\displaystyle \lim_{x \to 3} \dfrac{x + 3}{x - 2} = 6$ .

Let $\epsilon > 0$ . I must find $\delta$ such that if $\delta > |x - 3| > 0$ , then $\epsilon > \left|\dfrac{x + 3}{x - 2} - 6\right|$ .

Here's the scratch work. I want

$$\epsilon > \left|\dfrac{x + 3}{x - 2} - 6\right| = \left|\dfrac{x + 3 - 6(x - 2)}{x - 2}\right| = \left|\dfrac{15 - 5 x}{x - 2}\right| = 5|x - 3|\cdot \dfrac{1}{|x - 2|}.$$

As usual, I suppose $1 \ge \delta$ . Then $\delta > |x - 3|$ gives $1 > |x - 3|$ , so $2 < x < 4$ , and $0 < x - 2 < 4$ . But now I have a problem: I want to estimate how big $\dfrac{1}{|x - 2|}$ could be, but I can't take reciprocals in $0 < x - 2 < 4$ ! In fact, $\dfrac{1}{|x - 2|}$ gets infinitely large on this interval.

So I rewind and try again with a smaller $\delta$ . Suppose $0.5 \ge \delta$ . Then $\delta > |x - 3|$ gives $0.5 > |x - 3|$ , so $2.5 < x < 3.5$ , and $0.5 < x - 2 < 1.5$ . Taking reciprocals gives $2 > \dfrac{1}{x - 2} > \dfrac{2}{3}$ , so $\dfrac{1}{|x - 2|} < 2$ .

If I had $\epsilon > 5|x - 3|\cdot 2$ , then $2 > \dfrac{1}{|x - 2|}$ gives $\epsilon > 5|x - 3|\cdot \dfrac{1}{|x - 2|}$ , which is what I want. I could get $\epsilon > 5|x - 3|\cdot 2 = 10|x - 3|$ if $\dfrac{\epsilon}{10} > |x - 3|$ , and this in turn I could get if I had $\dfrac{\epsilon}{10} \ge \delta$ .

Thus, I ought to take $\delta = \min\left(\dfrac{\epsilon}{10},0.5\right)$ .

Now here's the proof. Take $\delta = \min\left(\dfrac{\epsilon}{10},0.5\right)$ . Since $0.5 \ge \delta > |x - 3|$ , I get

$$\eqalign{ 0.5 & > |x - 3| \cr 2.5 < &\ x < 3.5 \cr 0.5 < &\ x - 2 < 1.5 \cr \noalign{\vskip2pt} 2 > &\ \dfrac{1}{x - 2} > \dfrac{2}{3} \cr}$$

Therefore, $\dfrac{1}{|x - 2|} < 2$ .

In addition, $\dfrac{\epsilon}{10} \ge \delta > |x - 3|$ , so

$$\epsilon > 10|x - 3| = 5|x - 3|\cdot 2 > 5|x - 3|\cdot \dfrac{1}{|x - 2|} = \left|\dfrac{x + 3}{x - 2} - 6\right|.$$

This proves that $\displaystyle \lim_{x \to 3} \dfrac{x + 3}{x - 2} = 6$ .

6. Prove: $\lnot C$ .

Premises: $\left\{\matrix{A \ifthen (B \land D) \cr D \ifthen\,\lnot C \cr (\lnot B \lor C) \ifthen A \cr}\right.$

$$\matrix{ 1. & A \hfill & \hbox{Premise for proof by cases} \hfill \cr 2. & A \ifthen (B \land D) \hfill & \hbox{Premise} \hfill \cr 3. & B \land D \hfill & \hbox{Modus ponens (1,2)} \hfill \cr 4. & D \hfill & \hbox{Decomposing a conjunction (3)} \hfill \cr 5. & D \ifthen\,\lnot C \hfill & \hbox{Premise} \hfill \cr 6. & \lnot C \hfill & \hbox{Modus ponens (4,5)} \hfill \cr 7. & \lnot A \hfill & \hbox{Premise for proof by cases} \hfill \cr 8. & (\lnot B \lor C) \ifthen A \hfill & \hbox{Premise} \hfill \cr 9. & \lnot(\lnot B \lor C) \hfill & \hbox{Modus tollens (7,8)} \hfill \cr 10. & B \land \lnot C \hfill & \hbox{DeMorgan's law (9)} \hfill \cr 11. & \lnot C \hfill & \hbox{Decomposing a conjunction (10)} \hfill \cr 12. & \lnot C \hfill & \hbox{Proof by cases (1, 6, 7, 11)} \quad\halmos \hfill \cr}$$

7. Prove that if $x \in \real$ , then

$$-7 \le |x + 4| - |x - 3| \le 7.$$

Note that

$$|x + 4| = \cases{ x + 4 & if $x \ge -4$ \cr -(x + 4) & if $x < -4$ \cr} \quad\hbox{and}\quad |x - 3| = \cases{ x - 3 & if $x \ge 3$ \cr -(x - 3) & if $x < 3$ \cr}.$$

Case 1: $x < -4$ .

$$|x + 4| - |x - 3| = -(x + 4) - [-(x - 3)] = -x - 4 + x - 3 = -7.$$

Hence, $-7 \le |x + 4| - |x - 3| \le 7$ .

Case 2: $-4 \le x < 3$ .

$$|x + 4| - |x - 3| = (x + 4) - [-(x - 3)] = x + 4 + x - 3 = 2 x + 1.$$

Now

$$\eqalign{ -4 \le & x < 3 \cr -8 \le & 2 x < 6 \cr -7 \le & 2 x + 1 < 7 \cr}$$

Hence, $-7 \le |x + 4| - |x - 3| \le 7$ .

Case 3: $x \ge 3$ .

$$|x + 4| - |x - 3| = (x + 4) - (x - 3) = x + 4 - x + 3 = 7.$$

Hence, $-7 \le |x + 4| - |x - 3| \le 7$ .

This proves $-7 \le |x + 4| - |x - 3| \le 7$ for all $x \in \real$ .

8. Show that there do not exist real numbers x and y such that

$$x^2 - x + y^2 - 3 y + 3 = 0.$$

Suppose that for $x, y \in \real$ ,

$$x^2 - x + y^2 - 3 y + 3 = 0.$$

Complete the square in x and in y:

$$\eqalign{ x^2 - x + \dfrac{1}{4} + y^2 - 3 y + \dfrac{9}{4} + \dfrac{1}{2} & = 0 \cr \left(x - \dfrac{1}{2}\right)^2 + \left(y - \dfrac{3}{2}\right)^2 + \dfrac{1}{2} & = 0 \cr}$$

Each of the squared terms on the left are nonnegative, so the left side must be greater than or equal to $\dfrac{1}{2}$ . Therefore, it can't be equal to 0. This contradiction show that there do not exist $x, y \in \real$ such that $x^2 - x + y^2 - 3 y + 3 = 0$ .

9. The Fibonacci numbers are defined recursively by

$$f_0 = 1, \quad f_1 = 1, \quad f_n = f_{n-1} + f_{n-2} \quad\hbox{for}\quad n > 1.$$

Prove that for $n \ge 0$ ,

$$f_0^2 + f_1^2 + \cdots + f_n^2 = f_n f_{n+1}.$$

For $n = 0$ ,

$$f_0^2 = 1^2 = 1 \quad\hbox{and}\quad f_0 f_1 = 1\cdot 1 = 1.$$

Thus, the result is true for $n = 0$ .

Assume $n > 1$ , and suppose the result is true for n. I'll prove the result for $n + 1$ .

The result for n says that

$$f_0^2 + f_1^2 + \cdots + f_n^2 = f_nf_{n+1}.$$

Adding $f_{n+1}^2$ to both sides, I get

$$f_0^2 + f_1^2 + \cdots + f_n^2 + f_{n+1}^2 = f_nf_{n+1} + f_{n+1}^2 = f_{n+1}(f_n + f_{n+1}) = f_{n+1}f_{n+2}.$$

This proves the result for $n + 1$ . Hence, the result is true for all $n \ge 0$ , by induction.

10. Prove that if $n \ge 1$ , then

$$1 \cdot 5 + 2 \cdot 6 + 3 \cdot 7 + \cdots + n(n + 4) = \dfrac{n(n + 1)(2 n + 13)}{6}.$$

For $n = 1$ , the left side is $1 \cdot 5 = 5$ , while the right side is $\dfrac{1(2)(15)}{6} = 5$ . Thus, the result holds for $n = 1$ .

Assume that the result is true for n:

$$1 \cdot 5 + 2 \cdot 6 + 3 \cdot 7 + \cdots + n(n + 4) = \dfrac{n(n + 1)(2 n + 13)}{6}.$$

I will prove it for $n + 1$ :

$$1 \cdot 5 + 2 \cdot 6 + 3 \cdot 7 + \cdots + n(n + 4) + (n + 1)(n + 5) = \dfrac{n(n + 1)(2 n + 13)}{6} + (n + 1)(n + 5) =$$

$$(n + 1)\left(\dfrac{n(2 n + 13)}{6} + (n + 5)\right) = (n + 1)\left(\dfrac{n(2 n + 13) + 6(n + 5)}{6}\right) = (n + 1)\left(\dfrac{2 n^2 + 19 n + 30}{6}\right) =$$

$$(n + 1)\left(\dfrac{(n + 2)(2 n + 15)}{6}\right) = \dfrac{(n + 1)(n + 2)(2 n + 15)}{6}.$$

This proves the result for $n + 1$ , so the result is true for all $n \ge 1$ , by induction.

11. Prove that the sum of the cubes of three consecutive positive integers is divisible by 9.

I'll use induction.

The first three consecutive positive integers are 1, 2, and 3, and

$$1^3 + 2^3 + 3^3 = 36.$$

This is divisible by 9.

Take $n > 1$ , and assume the result is true for n. In other words, assume that

$$n^3 + (n + 1)^3 + (n + 2)^3 \quad\hbox{is divisible by}\quad 9.$$

I want to prove the result for $n + 1$ : I want to show that $(n + 1)^3 + (n + 2)^3 + (n + 3)^3$ is divisible by 9.

Note that

$$n^3 + (n + 1)^3 + (n + 2)^3 = 3 n^3 + 9 n^2 + 15 n + 9 \quad\hbox{and}\quad (n + 1)^3 + (n + 2)^3 + (n + 3)^3 = 3 n^3 + 18 n^2 + 42 n + 36.$$

Thus,

$$[(n + 1)^3 + (n + 2)^3 + (n + 3)^3] - [n^3 + (n + 1)^3 + (n + 2)^3] = (3 n^3 + 18 n^2 + 42 n + 36) - (3 n^3 + 9 n^2 + 15 n + 9) =$$

$$9 n^2 + 27 n + 27.$$

Hence,

$$(n + 1)^3 + (n + 2)^3 + (n + 3)^3 = [n^3 + (n + 1)^3 + (n + 2)^3] + 9 n^2 + 27 n + 27 = [n^3 + (n + 1)^3 + (n + 2)^3] + 9(n^2 + 3 n + 3).$$

$n^3 + (n + 1)^3 + (n + 2)^3$ is divisible by 9 by the induction hypothesis, and $9(n^2 + 3 n + 3)$ is divisible by 9. Hence, the sum $(n + 1)^3 + (n + 2)^3 + (n + 3)^3$ is divisible by 9. This proves the result for $n + 1$ , so the result is true for all $n \ge 1$ , by induction.

12. A sequence of integers is defined by

$$x_0 = 6, \quad x_1 = 17,$$

$$x_n = x_{n - 1} + 12 x_{n - 2} \quad\hbox{for}\quad n \ge 2.$$

Prove that

$$x_n = 5 \cdot 4^n + (-3)^n \quad\hbox{for}\quad n \ge 0.$$

Use induction. For $n = 0$ , the formula gives

$$5 \cdot 4^0 + (-3)^0 = 5 + 1 = 6 = x_0.$$

For $n = 1$ , the formula gives

$$5 \cdot 4^1 + (-3)^1 = 17 = x_1.$$

Now assume the formula holds for all $k < n$ . In particular, it is true for $n -1$ and for $n - 2$ . Then

$$\eqalign{ x+n & = x_{n - 1} + 12 x_{n - 2} \cr & = [5 \cdot 4^{n - 1} + (-3)^{n - 1}] + 12 [5 \cdot 4^{n - 2} + (-3)^{n - 2}] \cr & = [5 \cdot 4^{n - 1} + 60 \cdot 4^{n - 2}] + [(-3)^{n - 1} + 12 \cdot (-3)^{n - 2}] \cr & = 5 \cdot 4^{n - 2} (4 + 12) + (-3)^{n - 2} [(-3) + 12] \cr & = 5 \cdot 4^{n - 2} \cdot 4^2 + (-3)^{n - 2} \cdot (-3)^2 \cr & = 5 \cdot 4^n + (-3)^n \cr}$$

This proves the result for n, so the formula holds for all $n \ge 0$ by induction.

13. Prove that if $n \ge 4$ , then

$$(2 n)! \ge 10^n.$$

For $n = 4$ ,

$$(2 n)! = 8! = 40320, \quad\hbox{while}\quad 10^4 = 10000.$$

The result holds for $n = 4$ .

Assume that $n \ge 4$ and the result is true for n:

$$(2 n)! \ge 10^n.$$

I will prove the result for $n + 1$ :

$$\eqalign{ [2(n + 1)]! & = (2 n + 2)! \cr & = (2 n + 2)(2 n + 1)(2 n)! \cr & \ge (2 n + 2)(2 n + 1) \cdot 10^n \cr & \ge 10 \cdot 9 \cdot 10^n \cr & \ge 10^{n + 1} \cr}$$

Note that $2 n + 2 \ge 10$ and $2 n + 1 \ge 9$ follow from $n \ge 4$ .

This proves the result for $n + 1$ , so the result is true for all $n \ge 4$ by induction.

14. Suppose that A is a set and $|A| = 3$ . Which set has more elements --- $\powerset(A)$ or $A \times A$ ?

$|\powerset(A)| = 2^3 = 8$ , while $|A \times A| = 3 \cdot 3 = 9$ . So $A \times A$ has more elements.

15. Let A and B be sets. Prove that $(A - B) \cap (B - A) = \emptyset$ .

I want to prove that $(A - B) \cap (B - A)$ is empty. Suppose on the contrary that $x \in (A - B) \cap (B - A)$ .

Since $x \in A - B$ , I have $x \in A$ and $x \notin B$ . Since $x \in B - A$ , I have $x \in B$ and $x \notin A$ . But in particular, I have the contrary assertions "$x \in A$ " and "$x \notin A$ ". This contradiction shows that $(A - B) \cap (B - A) = \emptyset$ .

16. Let A, B, and C be sets.

(a) Draw a general Venn diagram for $A - (B - C)$ .

(b) Prove that $A - (B - C) = (A \cap C) \cup (A - B)$ .

(a)

$$\hbox{\epsfysize=1.75in \epsffile{final-review11.eps}}\quad\halmos$$

(b) Before starting the proof, I'll prove an easy lemma.

Lemma. $x \notin B - C$ if and only if $x \notin B$ or $x \in C$ .

Proof. Now $x \notin B - C$ means $\lnot x \in B - C$ . By definition of complement, this is equivalent to $\lnot (x \in B \land \lnot x \in C)$ . By DeMorgan, this is equivalent to $x \notin B$ or $x \in C$ .

Let $x \in A - (B - C)$ . By definition of complement, $x \in A$ and $x \notin B - C$ . By the lemma, $x \notin B - C$ gives $x \notin B$ or $x \in C$ .

Suppose first that $x \notin B$ . Since $x \in A$ , the definition of complement gives $x \in A - B$ .

Next, suppose $x \in C$ . Since $x \in A$ , the definition of intersection gives $x \in A \cap C$ .

By the definition of union, $x \in (A \cap C) \cup (A - B)$ . This proves that $A - (B - C) \subset (A \cap C) \cup (A - B)$ .

Conversely, suppose $x \in (A \cap C) \cup (A - B)$ . By definition of union, I have $x \in A \cap C$ or $x \in A - B$ .

Suppose first that $x \in A \cap C$ . By definition of intersection, $x \in A$ and $x \in C$ . Now "$x \notin B$ or $x \in C$ " is true, so by the lemma $x \notin (B - C)$ . By definition of complement, $x \in A - (B - C)$ .

Next, suppose $x \in A - B$ . By definition of complement, $x \in A$ and $x \notin B$ . Now "$x \notin B$ or $x \in C$ " is true, so by the lemma $x \notin (B - C)$ . By definition of complement, $x \in A - (B - C)$ .

In both cases, $x \in A - (B - C)$ . This proves that $x \in (A \cap C) \cup (A - B) \subset A - (B - C)$ .

Hence, $A - (B - C) = (A \cap C) \cup (A - B)$ .

Here is an alternate proof written in a different style:

$$\matrix{x \in A - (B - C) & \iff & x \in A \land x \notin (B - C) \hfill & \hbox{Definition of complement} \cr & \iff & x \in A \land \lnot(x \in (B - C)) \hfill & \hbox{Definition of $\notin$} \cr & \iff & x \in A \land \lnot(x \in B \land x \notin C) \hfill & \hbox{Definition of complement} \cr & \iff & x \in A \land (\lnot x \in B \lor \lnot x \notin C) \hfill & \hbox{DeMorgan's law} \cr & \iff & x \in A \land (\lnot x \in B \lor \lnot\lnot x \in C) \hfill & \hbox{Definition of $\notin$} \cr & \iff & x \in A \land (\lnot x \in B \lor x \in C) \hfill & \hbox{Double negation} \cr & \iff & (x \in A \land \lnot x \in B) \lor (x \in A \land x \in C) \hfill & \hbox{Distributivity} \cr & \iff & (x \in A \land x \notin B) \lor (x \in A \land x \in C) \hfill & \hbox{Definition of $\notin$} \cr & \iff & x \in (A - B) \lor (x \in A \land x \in C) \hfill & \hbox{Definition of complement} \cr & \iff & x \in (A - B) \lor x \in A \cap C \hfill & \hbox{Definition of $\cap$} \cr & \iff & x \in A \cap C \lor x \in (A - B) \hfill & \hbox{Commutativity} \cr & \iff & x \in (A \cap C) \cup (A - B) \hfill & \hbox{Definition of $\cup$} \cr}$$

Therefore, $A - (B - C) = (A \cap C) \cup (A - B)$ .

17. Prove that $[-1, 2] \cup [0, 4] = [-1, 4]$ .

Let $x \in [-1, 2] \cup [0, 4]$ . Then $x \in [-1, 2]$ or $x \in [0, 4]$ .

Suppose $x \in [-1, 2]$ . Then

$$-1 \le x \le 2 \le 4.$$

Hence, $x \in [-1, 4]$ .

Suppose $x \in [0, 4]$ . Then

$$-1 \le 0 \le x \le 4.$$

Hence, $x \in [-1, 4]$ .

In both cases, $x \in [-1, 4]$ .

Thus, $[-1, 2] \cup [0, 4] \subset [-1, 4]$ .

Conversely, let $x \in [-1, 4]$ , so $-1 \le x \le 4$ . Thus, $-1 \le x$ and $x \le 4$ . I'll consider two cases.

Suppose $x \le 1$ . Then

$$-1 \le x \le 1 \le 2.$$

Hence, $x \in [-1, 2] \subset [-1, 2] \cup [0, 4]$ .

Suppose $x > 1$ . Then

$$0 \le 1 < x \le 4.$$

Hence, $x \in [0, 4] \subset [-1, 2] \cup [0, 4]$ .

This proves that $[-1, 4] \subset [-1, 2] \cup [0, 4]$ . Hence, $[-1, 2] \cup [0, 4] = [-1, 4]$ .

18. Prove that $(-4, 6) \cap (1, 8) = (1, 6)$ .

Let $x \in (-4, 6) \cap (1, 8)$ . I'll show that $x \in (1, 6)$ .

Since $x \in (-4, 6) \cap (1, 8)$ , the definition of intersection gives $x \in (-4, 6)$ and $x \in (1, 8)$ . The definition of intervals gives $-4 < x < 6$ and $1 < x < 8$ , so $-4 < x$ and $x < 6$ and $1 < x$ and $x < 8$ .

In particular, $1 < x$ and $x < 6$ give $1 < x < 6$ , so $x \in (1, 6)$ .

Next, let $x \in (1, 6)$ . I'll show that $x \in (-4, 6) \cap (1, 8)$ .

Since $x \in (1, 6)$ , I have $1 < x < 6$ . First,

$$-4 < 1 < x < 6.$$

So $x \in (-4, 6)$ .

Next,

$$1 < x < 6 < 8.$$

So $x \in (1, 8)$ .

By definition of intersection, $x \in (-4, 6) \cap (1, 8)$ .

Since $(-4, 6) \cap (1, 8)$ and $(1, 6)$ are contained in each other, I have $(-4, 6) \cap (1, 8) = (1, 6)$ .

19. In each case, give a counterexample to the statement.

(a) "If $n \in \integer$ , then $n^2 + 120 \ge 22 n$ ."

(b) "If $\der {} x f(x) = 3 x^2 + 4 x$ , then $f(x) = x^3 + 2 x^2$ ."

(c) "If a, b, and c are positive integers, then $(a^b)^c = a^(b^c)$ ."

(a) If $n = 11$ , then $n^2 + 120 = 241$ , but $22 n = 242$ , so $n^2 + 120 \not\geq 22 n$ .

(b) $\der {} x (x^3 + 2 x^2 + 1) = 3 x^2 + 4 x$ , but $x^3 + 2 x^2 + 1 \ne x^3 + 2 x^2$ .

(c)

$$(2^2)^3 = 4^3 = 64, \quad\hbox{but}\quad 2^(2^3) = 2^8 = 256.\quad\halmos$$

20. Bonzo McTavish observes that if n is an integer, then

$$2\cdot (2 n + 3) + (-4)\cdot (n + 1) = 2.$$

He concludes that $(2 n + 3, n + 1)$ is either 1 or 2. Can $(2 n + 3, n + 1) = 2$ ? Why or why not?

The equation $2 \cdot (2 n + 3) + (-4) \cdot (n + 1) = 2$ only shows that $(2 n + 3, n + 1)$ could be either 1 or 2. It does not mean that both of these numbers are possible.

In fact,

$$(2 n + 3) + (-2) \cdot (n + 1) = 1.$$

Since $(2 n + 3, n + 1)$ divides both $2 n + 3$ and $n + 1$ , it must divide $(2 n + 3) + (-2) \cdot (n + 1) = 1$ ; since $(2 n + 3, n + 1)$ is positive, $(2 n + 3, n + 1) = 1$ .

Thus, $(2 n + 3, n + 1)$ is never equal to 2.

21. Define $f: \real^2 \to \real^2$ by

$$f(x, y) = (x + y^3, x^2).$$

Prove by example that f is neither injective nor surjective.

$$f(1,0 ) = (1 + 0^3, 1^2) = (1, 1) \quad\hbox{and}\quad f(-1, \root 3 \of 2) = (-1 + (\root 3 \of 2)^3, (-1)^2) = (1, 1).$$

Since f takes the different inputs $(1, 0)$ and $(-1, \root 3 \of 2)$ to the same output $(1, 1)$ , f is not injective.

$f(x, y) = (x + y^3, x^2)$ , so the second component of $f(x, y)$ cannot be negative. Therefore, for no $(x, y)$ does $f(x, y) = (0, -1)$ . Hence, f is not surjective.

22. Define $g: \real^2 \to \real^2$ by

$$g(x, y) = (x + y^3, x^3).$$

Prove that g is bijective by:

(a) Proving that g is injective and surjective.

(b) Constructing an inverse for g.

(a) Suppose that $g(a, b) = g(c, d)$ . This means that

$$(a + b^3, a^3) = (c + d^3, c^3).$$

Equating the second components, I get $a^3 = c^3$ , so $a = c$ . Equating the first components gives $a + b^3 = c + d^3$ . But $a = c$ , so $b^3 = d^3$ , and therefore $b = d$ .

Hence, $(a, b) = (c, d)$ , which proves that g is injective.

Next, take $(a, b) \in \real^2$ . I want to find $(x, y)$ such that $g(x, y) = (a, b)$ .

I'll work backwards, then check by plugging back in. I want

$$(x + y^3, x^3) = (a, b), \quad\hbox{or}\quad x + y^3 = a \quad\hbox{and}\quad x^3 = b.$$

The second component equation gives $x = b^{1/3}$ . Plugging this into the first component equation gives

$$b^{1/3} + y^3 = a, \quad\hbox{or}\quad y^3 = a - b^{1/3}.$$

Thus, $y = [a - b^{1/3}]^{1/3}$ .

Now I'll check that this works:

$$g\left(b^{1/3}, [a - b^{1/3}]^{1/3}\right) = \left(b^{1/3} + \left([a - {b^{1/3}}]^{1/3}\right)^3, (b^{1/3})^3\right) = (b^{1/3} + a - b^{1/3}, b) = (a, b).$$

This proves that g is surjective.

(b) To guess an inverse, I use the same approach I used above to show that g is surjective. I'll repeat it so you can see how the whole proof would look like in this case.

I have $g(x, y) = (x + y^3, x^3)$ , and I want a formula for $g^{-1}(a, b) = (p, q)$ . This means I want p and q in terms of a and b. Working backwards,

$$\eqalign{ g^{-1}(a, b) & = (p, q) \cr g[g^{-1}(a, b)] & = g(p, q) \cr (a, b) & = (p + q^3, p^3) \cr}$$

So

$$p + q^3 = a \quad\hbox{and}\quad p^3 = b.$$

The second equation gives $p = b^{1/3}$ . Plugging this into the first equation and solving gives $q = [a - b^{1/3}]^{1/3}$ . So define

$$g^{-1}(a, b) = (b^{1/3}, [a - b^{1/3}]^{1/3}).$$

Now check that g and $g^{-1}$ really are inverses:

$$g\left(g^{-1}(a, b)\right) = g(b^{1/3}, [a - b^{1/3}]^{1/3}) = (b^{1/3} + ([a - b^{1/3}]^{1/3})^3), [b^{1/3}]^3) = (b^{1/3} + a - b^{1/3}, b) = (a, b).$$

$$g^{-1}\left(g(x, y)\right) = g^{-1}(x + y^3, x^3) = ([x^3]^{1/3}, [(x + y^3) - [x^3]^{1/3}]^{1/3}) = (x, (x + y^3 - x)^{1/3}) = (x, [y^3]^{1/3}) = (x, y).$$ g and $g^{-1}$ are inverses, so g is bijective.\quad\halmos

23. Define $h: \real^2 \to \real^2$ by

$$h(x, y) = (x + 3 y + 2, x^3 + 5).$$

Prove that h is surjective.

Let $(a, b) \in \real^2$ . I need to find $(x, y) \in \real^2$ such that $h(x, y) = (a, b)$ .

I'll work backwards to guess formulas for x and y in terms of a and b, then confirm that my guesses work.

I want $h(x, y) = (a, b)$ , so

$$(x + 3 y + 2, x^3 + 5) = (a, b), \quad\hbox{or}\quad x + 3 y + 2 = a \quad\hbox{and}\quad x^3 + 5 = b.$$

The second equation gives $x = (b - 5)^{1/3}$ ; plugging this into the first equation, I get

$$(b - 5)^{1/3} + 3 y + 2 = a, \quad\hbox{or}\quad y = \dfrac{1}{3}\left(a - 2 - (b - 5)^{1/3}\right).$$

Now I'll check that these formulas for x and y work:

$$h\left((b - 5)^{1/3}, \dfrac{1}{3}\left(a - 2 - (b - 5)^{1/3}\right)\right) = \left((b - 5)^{1/3} + 3\cdot \dfrac{1}{3} \left(a - 2 - (b - 5)^{1/3}\right) + 2, \left((b - 5)^{1/3}\right)^3 + 5\right) =$$

$$\left((b - 5)^{1/3} + a - 2 - (b - 5)^{1/3} + 2, b - 5 + 5\right) = (a, b).$$

This proves that h is surjective.

24. Define $f: \real \to \real$ by

$$f(x) = 2 e^x + x^3 + 4 x + \sin x.$$

Prove that f is injective.

It is too hard to do this directly, so I'll use calculus. Suppose $f(a) = f(b)$ and $a \ne b$ . There is no harm in assuming $a < b$ --- if instead $b < a$ , then just rewrite the rest of the proof with a and b switched.

Since f is differentiable, I can apply Rolle's Theorem to f on the interval $[a, b]$ to conclude that $f'(c) = 0$ for some c in $(a, b)$ .

But

$$f'(x) = 2 e^x + 3 x^2 + 4 + \cos x.$$

Now for all x, I have $2e^x > 0$ , $3 x^2 \ge 0$ , and $\cos x \ge -1$ . So

$$f'(x) = 2 e^x + 3 x^2 + 4 + \cos x > 0 + 0 + 4 + (-1) = 3.$$

This contradicts $f'(c) = 0$ . It follows that $a = b$ , so f is injective.

25. Define $f: \real \to \real$ by

$$f(x) = 2 x^3 + \tan^{-1} x.$$

Prove that f is surjective.

Let $y \in \real$ . I must show that $f(x) = y$ for some $x \in \real$ .

Note that

$$\lim_{x \to \infty} (2 x^3 + \tan^{-1} x) = +\infty \quad\hbox{and}\quad \lim_{x \to -\infty} (2 x^3 + \tan^{-1} x) = -\infty.$$

Therefore, there are numbers a and b such that

$$f(a) < y < f(b).$$

Since f is continuous, by the Intermediate Value Theorem there is a number x between a and b such that $f(x) = y$ . Hence, f is surjective.

26. Prove that $\{0, 1\} \times \real$ has the same cardinality as $\real$ .

$\{0, 1\} \times \real$ consists of all ordered pairs $(0, x)$ or $(1, x)$ , where $x \in \real$ . Thus, $\{0, 1\} \times \real$ looks like two copies of the real line:

$$\hbox{\epsfysize=0.5in \epsffile{final-review10a.eps}}$$

I'll use the Schr\"oder-Bernstein theorem.

Define $f: \real \to \{0, 1\} \times \real$ by

$$f(x) = (0, x).$$

If $f(a) = f(b)$ , then $(0, a) = (0, b)$ , so $a = b$ . Therefore, f is injective.

Define $g: \{0, 1\} \times \real \to \real$ by

$$g(0, x) = \arctan x - \dfrac{\pi}{2} \quad\hbox{and}\quad g(1, x) = \arctan x + \dfrac{\pi}{2}.$$

g maps the first copy of $\real$ to $(-\pi,0)$ and the second copy to $(0,\pi)$ . Here's the picture:

$$\hbox{\epsfysize=2.5in \epsffile{final-review10b.eps}}$$

To show that g is injective, suppose $g(a, b) = g(c, d)$ . I must show that $(a, b) = (c, d)$ .

First, I'll show that $a = c$ . a and c are each either 0 or 1. If $a \ne c$ , then one is 0 and the other is 1.

Suppose $a = 0$ and $c = 1$ . Then

$$g(a, b) = g(0, b) = \arctan b - \dfrac{\pi}{2} \quad\hbox{and}\quad g(c, d) = g(1, d) = \arctan d + \dfrac{\pi}{2}.$$

Now

$$-\dfrac{\pi}{2} < \arctan b < \dfrac{\pi}{2}, \quad\hbox{so}\quad -\pi < \arctan b - \dfrac{\pi}{2} < 0 \quad\hbox{and}\quad -\pi < g(a, b) < 0.$$

Likewise,

$$-\dfrac{\pi}{2} < \arctan d < \dfrac{\pi}{2}, \quad\hbox{so}\quad 0 < \arctan d + \dfrac{\pi}{2} < \pi \quad\hbox{and}\quad 0 < g(c, d) < \pi.$$

But $-\pi < g(a, b) < 0$ and $0 < g(c, d) < \pi$ contradict the assumption that $g(a, b) = g(c, d)$ . Hence, $a = 0$ and $c = 1$ is impossible.

A symmetrical argument shows that $a = 1$ and $c = 0$ is impossible.

Therefore, either $a = c = 0$ or $a = c = 1$ .

Suppose $a = c = 0$ . Then

$$g(a, b) = g(0, b) = \arctan b - \dfrac{\pi}{2} \quad\hbox{and}\quad g(c, d) = g(0, d) = \arctan d - \dfrac{\pi}{2}.$$

Now $g(a, b) = g(c, d)$ , so

$$\arctan b - \dfrac{\pi}{2} = \arctan d - \dfrac{\pi}{2}, \quad \arctan b = \arctan d, \quad b = d.$$

Since $a = c = 0$ , it follows that $(a, b) = (c, d)$ .

A similar argument shows that if $a = c = 1$ , then $(a, b) = (c, d)$ .

Hence, g is injective.

Therefore, by the Schr\"oder-Bernstein theorem, $\{0, 1\} \times \real$ has the same cardinality as $\real$ .

27. Prove by constructing a bijection that $|[-1, 3]| = |[3, 5]|$ .

Define $f: [-1, 3] \to [3, 5]$ by

$$f(x) = \dfrac{1}{2} x + \dfrac{7}{2}.$$

Note that if $x \in [-1, 3]$ , then

$$\eqalign{ -1 \le x & \le 3 \cr \noalign{\vskip2pt} -\dfrac{1}{2} \le \dfrac{1}{2} x & \le \dfrac{3}{2} \cr \noalign{\vskip2pt} 3 \le \dfrac{1}{2} x + \dfrac{7}{2} & \le 5 \cr \noalign{\vskip2pt} 3 \le f(x) & \le 5 \cr}$$

Hence, $f(x) \in [3, 5]$ , so f does map $[-1, 3]$ into $[3, 5]$ .

Define $g: [3, 5] \to [-1, 3]$ by

$$g(x) = 2 x - 7.$$

Note that if $x \in [3, 5]$ , then

$$\eqalign{ 3 \le x & \le 5 \cr 6 \le 2 x & \le 10 \cr -1 \le 2 x - 7 & \le 3 \cr -1 \le f(x) & \le 3 \cr}$$

Hence, $g(x) \in [-1, 3]$ , so f does map $[3, 5]$ into $[-1, 3]$ .

I have

$$f(g(x)) = f(2 x - 7) = \dfrac{1}{2}(2 x - 7) + \dfrac{7}{2} = x - \dfrac{7}{2} + \dfrac{7}{2} = x.$$

$$g(f(x)) = g\left(\dfrac{1}{2}x + \dfrac{7}{2}\right) = 2\left(\dfrac{1}{2}x + \dfrac{7}{2}\right) - 7 = x + 7 - 7 = x.$$

Hence, f and g are inverses, so they are bijections. Therefore, $|[-1, 3]| = |[3, 5]|$ .

28. Prove that $[1, 4] \cup (5, 6)$ has the same cardinality as $(2, 3) \cup \{7\}$ .

Define $f: [1, 4] \cup (5, 6) \to (2, 3) \cup \{7\}$ by

$$f(x) = 0.1 x + 2.$$

Note that if $x \in [1, 4] \cup (5, 6)$ , then

$$\eqalign{ 1 \le x & < 6 \cr 0.1 \le 0.1 x & < 0.6 \cr 2.1 \le 0.1 x + 2 & < 2.6 \cr 2 < 2.1 \le f(x) & < 2.6 < 3 \cr}$$

Therefore, $f(x) \in (2, 3) \cup \{7\}$ , so f does map $[1, 4] \cup (5, 6)$ into $(2, 3) \cup \{7\}$ .

If $f(x_1) = f(x_2)$ , then

$$\eqalign{ 0.1 x_1 + 2 & = 0.1 x_2 + 2 \cr 0.1 x_1 & = 0.1 x_2 \cr x_1 & = x_2 \cr}$$

Therefore, f is injective.

Define $g: (2, 3) \cup \{7\} \to [1, 4] \cup (5, 6)$ by

$$g(x) = 0.2 x + 1.$$

If $x \in (2, 3) \cup \{7\}$ , then

$$\eqalign{ 2 < x & \le 7 \cr 0.4 < 0.2 x & \le 1.4 \cr 1.4 < 0.2 x + 1 & \le 2.4 \cr 1 < 1.4 < g(x) & \le 2.4 < 4 \cr}$$

Therefore, $g(x) \in [1, 4] \cup (5, 6)$ , so g does map $(2, 3) \cup \{7\}$ into $[1, 4] \cup (5, 6)$ .

If $g(x_1) = g(x_2)$ , then

$$\eqalign{ 0.2 x_1 + 1 & = 0.2 x_2 + 1 \cr 0.2 x_1 & = 0.2 x_2 \cr x_1 & = x_2 \cr}$$

Therefore, g is injective.

By the Schr\"oder-Bernstein theorem, $[1, 4] \cup (5, 6)$ has the same cardinality as $(2, 3) \cup \{7\}$ .

29. Define a relation on $\real$ by

$$x \sim y \quad\hbox{means}\quad (\sin x)(\sin y) \ge 0.$$

Take each axiom for an equivalence relation. If the axiom holds, prove it; if the axiom does not hold, give a counterexample.

The graph of this relation is pretty complicated; I'll give it even though it's not necessary for the problem, since it's kind of interesting.

$$\hbox{\epsfysize=2in \epsffile{final-review7.eps}}$$

In this contour plot, the light areas represent points $(x, y)$ where $f(x, y) = (\sin x)(\sin y)$ is positive; dark areas represents points where the function is negative. Thus, if a point $(x, y)$ is in a light area, then $x \sim y$ .

For reflexivity, note that $(\sin x)(\sin x) = (\sin x)^2 \ge 0$ for all $x \in \real$ . Therefore, $x \sim x$ for all $x \in \real$ , and the relation is reflexive.

Suppose $x \sim y$ . Then $(\sin x)(\sin y) \ge 0$ , so $(\sin y)(\sin x) \ge 0$ , and hence $y \sim x$ . Therefore, $\sim$ is symmetric.

On the other hand,

$$\left(\sin \dfrac{\pi}{2}\right)(\sin 0) = (1)(0) = 0 \ge 0, \quad\hbox{so}\quad \dfrac{\pi}{2} \sim 0,$$

$$(\sin 0)\left(\sin -\dfrac{\pi}{2}\right) = (0)(-1) = 0 \ge 0, \quad\hbox{so}\quad 0 \sim -\dfrac{\pi}{2}.$$

But

$$\left(\sin \dfrac{\pi}{2}\right)\left(\sin -\dfrac{\pi}{2}\right) = (1)(-1) = -1 \not\ge 0, \quad\hbox{so}\quad \dfrac{\pi}{2} \not\sim -\dfrac{\pi}{2}.$$

Hence, $\sim$ is not transitive. Thus, $\sim$ is not an equivalence relation.

30. Consider the equivalence relation defined by writing $x \sim y$ to mean $x = y \mod{3}$ on the set

$$S = \{-3, -2, 0, 2, 4, 5, 6, 10, 17, 18, 22\}.$$

List the elements of the equivalence classes.

$$\{-3, 0, 6, 18\}, \quad \{-2, 4, 10, 22\}, \quad \{2, 5, 17\}.\quad\halmos$$

31. A relation is defined on $\real^2$ by

$$(a, b) \sim (c, d) \quad \iff \quad a |d| = c |b|.$$

Check each axiom for an equivalence relation. If the axiom holds, prove it. If the axiom doesn't hold, give a specific counterexample.

If $(a, b) \in \real^2$ , then

$$a |b| = a |b|.$$

Hence, $(a, b) \sim (a, b)$ , and $\sim$ is reflexive.

Suppose $(a, b) \sim (c, d)$ . Then

$$a |d| = c |b| \quad\hbox{so}\quad c |b| = a |d|.$$

Hence, $(c, d) \sim (a, b)$ , and $\sim$ is symmetric.

$(1, 3) \sim (0, 0)$ because $1 \cdot |0| = 0 = 3 \cdot |0|$ .

$(0, 0) \sim (1, 2)$ because $0 \cdot |2| = 0 = 1 \cdot |0|$ .

But $(1, 3) \not\sim (1, 2)$ , because $1 \cdot |2| = 2$ while $1 \cdot |3| = 3$ . Hence, $\sim$ is not transitive.

32. Define a relation $\sim$ on $\real$ by

$$x \sim y \quad\hbox{means}\quad x^3 - x \le y^3 - y.$$

Check each axiom for a partial order. If the axiom holds, prove it; if the axiom does not hold, give a counterexample.

If $x \in \real$ , then $x^3 - x \le x^3 - x$ , so $x \sim x$ . Therefore, reflexivity holds.

Take $x = 0$ and $y = 1$ . $x^3 - x = 0$ and $y^3 - y = 0$ , so $x^3 - x \le y^3 - y$ and $y^3 - y \le x^3 - x$ . Thus, $x \sim y$ and $y \sim x$ . However, $x \ne y$ . Therefore, antisymmetry fails.

Suppose that $x \sim y$ and $y \sim z$ . This means that

$$x^3 - x \le y ^3 - y \quad\hbox{and}\quad y^3 - y \le z^3 - z.$$

Therefore, $x^3 - x \le z^3 - z$ , so $x \sim z$ . Hence, the relation is transitive.

33. Define a relation $\sim$ on $\real^2$ by

$$(a, b) \sim (c, d) \quad\hbox{means}\quad ab \ge cd.$$

Check each axiom for a partial order. If the axiom holds, prove it; if the axiom does not hold, give a counterexample.

For all $(a, b) \in \real^2$ , I have $ab \ge ab$ , so $(a, b) \sim (a, b)$ . The relation is reflexive.

I have $(1, 0) \sim (0, 1)$ , since $1 \cdot 0 \ge 0 \cdot 1$ . I have $(0, 1) \sim (1, 0)$ , since $0 \cdot 1 \ge 1 \cdot 0$ . But $(1, 0) \ne (0, 1)$ . Hence, the relation is not antisymmetric.

Suppose $(a, b), (c, d), (e, f) \in \real^2$ , and $(a, b) \sim (c, d)$ and $(c, d) \sim (e, f)$ . Then

$$ab \ge cd \quad\hbox{and}\quad cd \ge ef, \quad\hbox{so}\quad ab \ge ef.$$

Hence, $(a, b) \sim (e, f)$ , so the relation is transitive.

34. Prove that the square of an odd number leaves a remainder of 1 when it's divided by 4.

Let $2 n + 1$ be an odd number, where $n \in \integer$ . Then

$$(2 n + 1)^2 = 4 n^2 + 4 n + 1 = 4(n^2 + n) + 1.$$

Therefore, when $(2 n + 1)^2$ is divided by 4, the remainder is 1.

35. Prove that if n is an integer, then $n^2 + n + 3$ does not leave a remainder of 1 or 2 when it's divided by 5.

I consider the cases $n = 0, 1, 2, 3, 4$ mod 5. Since I'm interested in the remainder when $n^3 + n + 3$ is divided by 5, I look at $n^2 + n + 3$ mod 5. Here's the table:

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & n & & 0 & & 1 & & 2 & & 3 & & 4 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & $n^2 + n + 3 \pmod 5$ & & 3 & & 0 & & 4 & & 0 & & 3 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

The table shows that $n^2 + n + 3$ never equals 1 or 2 mod 5. This completes the proof.

36. Prove that if $m, n \in \integer$ and neither m nor n is divisible by 3, then $m^2 + n^2$ is not divisible by 3.

Since $3 \notdiv m$ , I have $m = 1$ or 2 mod 3. Likewise, since $3 \notdiv n$ , I have $n = 1$ or 2 mod 3.

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & $m \mod{3}$ & & 1 & & 2 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & $m^2 \mod{3}$ & & 1 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} \hskip0.25in \vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & $n \mod{3}$ & & 1 & & 2 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & \cr & $n^2 \mod{3}$ & & 1 & & 1 & \cr height2pt & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

It follows that $m^2 + n^2 = 2 \mod{3}$ , so $3 \notdiv m^2 + n^2$ .

37. Compute $(1021, 129)$ .

Use the Euclidean algorithm:

$$\matrix{ 1021 & - \cr 129 & 7 \cr 118 & 1 \cr 11 & 10 \cr 8 & 1 \cr 3 & 2 \cr 2 & 1 \cr 1 & 2 \cr}$$

Thus, $(1021, 129) = 1$ .

38. Using the fact that $(x, y) = m x + n y$ for some $m, n \in \integer$ , prove:

(a) If d is a common divisor of a and b, then $d \mid (a, b)$ .

(b) If $a, b, c \in \integer$ and $a > 0$ , then $(a b, a c) = a (b,c)$ .

(a) Write $(a, b) = m a + n b$ , where $m, n \in \integer$ . Then $d \mid a$ and $d \mid b$ , so $d \mid m a + n b = (a, b)$ .

(b) I'll show that $(a b, a c)$ and $a (b, c)$ divide each other. Since they are both positive numbers, it will follow that they're equal.

$(b, c) \mid b$ and $(b, c) \mid c$ , so $a (b, c) \mid a b$ and $a (b, c) \mid a c$ . Therefore, $a (b, c)$ is a common divisor of $a b$ and $a c$ , so $a (b, c) \mid (a b, a c)$ .

On the other hand, I have $(b, c) = m b + n c$ for some $m, n \in \integer$ . So $a (b, c) = m (a b) + n (a c)$ . Now $(a b, a c) \mid a b$ and $(a b, a c) \mid a c$ , so

$$(a b, a c) \mid m (a b) + n (a c) = a (b, c).$$

Therefore, $a (b, c) = (a b, a c)$ .

39. If $a, b, m, n \in \integer$ and $a m + b n = 6$ , does it follow that $(m, n) = 6$ ?

No. For example, take $a = 1$ , $b = 1$ , $m = 2$ , and $n = 4$ . Then

$$a m + b n = 1 \cdot 2 + 1 \cdot 4 = 6.$$

But $(m, n) = (2, 4) = 2$ .

40. Prove that if $n \in \integer$ , then $(2 n^2 + 8 n + 1, n + 4) = 1$ .

Note that

$$(2 n^2 + 8 n + 1) - (2 n)(n + 4) = 1.$$

Now $(2 n^2 + 8 n + 1, n + 4) \mid 2 n^2 + 8 n + 1$ and $(2 n^2 + 8 n + 1, n + 4) \mid n + 4$ . From the equation above, it follows that $(2 n^2 + 8 n + 1, n + 4) \mid 1$ . Hence, $(2 n^2 + 8 n + 1, n + 4) = 1$ .

41. Prove that if $x, y > 0$ , then $x^2 + \dfrac{y^2}{x^2} \ge 2 y$ .

$$\eqalign{ (x^2 - y)^2 & \ge 0 \cr x^4 - 2 x^2 y + y^2 & \ge 0 \cr x^4 + y^2 & \ge 2 x^2 y \cr x^2 + \dfrac{y^2}{x^2} & \ge 2 y \quad\halmos \cr}$$

42. Prove that if $x > 0$ , then $x^3 + e^{2 x} > 1$ .

Let $f(x) = x^3 + e^{2 x} - 1$ . Then $f'(x) = 3 x^2 + 2 e^{2 x}$ , and $f'(x) > 0$ for all x. Thus, f is always increasing. But $f(0) = 0$ , so if $x > 0$ , then $f(x) > 0$ . Hence, if $x > 0$ , then $x^3 + e^{2 x} - 1 > 0$ , i.e. $x^3 + e^{2 x} > 1$ .

43. Prove that if $x > 0$ , then

$$x \ln x \ge x - 1.$$

[Hint: Find the absolute min of $f(x) = x \ln x - x + 1$ .]

Following the hint, I take $f(x) = x \ln x - x + 1$ . Note that the domain of f is $x > 0$ . The derivative is

$$f'(x) = 1 + \ln x - 1 = \ln x.$$

The only critical point is $x = 1$ .

$$\hbox{\epsfxsize=3in \epsffile{final-review1.eps}}$$

The function decreases for $x \le 1$ and increases for $x \ge 1$ . $x = 1$ is a local min; since it's the only critical point, it's an absolute min.

Now $f(1) = 1 \ln 1 - 1 + 1 = 0$ . Since this is the absolute min, $f(x) \ge 0$ for all $x > 0$ . In other words, $x \ln x - x + 1 \ge 0$ for $x > 0$ , or $x \ln x \ge x - 1$ for $x > 0$ .

Remark. Many inequalities involving real functions can be proved using calculus in this way by finding absolute maxima or minima.

44. Use the limit definition to prove that

$$\lim_{x \to \infty} \dfrac{8 x^3 + 1}{2 x^3} = 4.$$

Let $\epsilon > 0$ . Set $M = \dfrac{1}{{\root 3 \of {2\epsilon}}}$ . Suppose that $n > M$ . Note that since $\epsilon > 0$ , it follows that $M > 0$ , so $n > 0$ . Then

$$\eqalign{ n & > \dfrac{1}{{\root 3 \of {2\epsilon}}} \cr n^3 & > \dfrac{1}{2\epsilon} \cr \epsilon & > \dfrac{1}{2 n^3} \cr \epsilon & > \left|\dfrac{1}{2 n^3}\right| \cr \epsilon & > \left|\dfrac{8 n^3 + 1 - 8 n^3}{2 n^3}\right| \cr \epsilon & > \left|\dfrac{8 n^3 + 1}{2 n^3} - 4\right| \cr}$$

This proves that $\displaystyle \lim_{x \to \infty} \dfrac{8 x^3 + 1}{2 x^3} = 4$ .

45. Phoebe Small has proved that

$$\bigcup_{n=1}^\infty \left[0, \dfrac{n}{n + 6}\right] = [0, 1).$$

But Bonzo McTavish is confused. "The point 0.9 is in $[0, 1]$ . But for $n = 1$ , the interval $\left[0, \dfrac{n}{n + 6}\right]$ is $\left[0, \dfrac{1}{7}\right]$ , and that doesn't contain 0.9." Does Bonzo have a valid objection?

Bonzo is confused. For 0.9 to be in $\displaystyle \bigcup_{n=1}^\infty \left[0, \dfrac{n}{n + 6}\right]$ , it does not need to be in all the intervals in the union --- it only has to be in at least one of the intervals.

In fact, $0.9 \in \left[0, \dfrac{55}{55 + 6}\right]$ . (Can you prove that if $n > 54$ , then $0.9 \in \left[0, \dfrac{n}{n + 6}\right]$ ?)

And Phoebe's claim is correct --- see if you can prove it.

46. Prove that $\displaystyle \bigcap_{n=1}^\infty [1, 2 + e^{-n}] = [1, 2]$ .

Let $x \in [1, 2]$ , so $1 \le x \le 2$ . Since $e^{-n} > 0$ for all n, I have

$$1 \le x \le 2 < 2 + e^{-n} \quad\hbox{for all } n.$$

Therefore, $x \in [1, 2 + e^{-n}]$ for all n, so $\displaystyle x \in \bigcap_{n=1}^\infty [1, 2 + e^{-n}]$ .

This proves that $\displaystyle [1, 2] \subset \bigcap_{n=1}^\infty [1, 2 + e^{-n}]$ .

Conversely, suppose $\displaystyle x \in \bigcap_{n=1}^\infty [1, 2 + e^{-n}]$ . Then $x \in [1, 2 + e^{-n}]$ for all n, so

$$1 \le x \le 2 + e^{-n} \quad\hbox{for all } n.$$

Suppose that $x > 2$ . Note that

$$\lim_{n \to \infty} (2 + e^{-n}) = 2.$$

In the limit definition, let $\epsilon = x - 2$ . Then there is a number M such that if $n > M$ ,

$$\epsilon = x - 2 > |(2 + e^{-n}) - 2| = |e^{-n}| = e^{-n}.$$

Then

$$\eqalign{ x - 2 & > e^{-n} \cr x & > 2 + e^{-n} \cr}$$

But this contradicts the fact that $x \le 2 + e^{-n}$ for all n.

Therefore, $x \le 2$ . Since $1 \le x$ , I have $1 \le x \le 2$ , and so $x \in [1, 2]$ . This proves that $\displaystyle \bigcap_{n=1}^\infty [1, 2 + e^{-n}] \subset [1, 2]$ .

Hence, $\displaystyle \bigcap_{n=1}^\infty [1, 2 + e^{-n}] = [1, 2]$ .

The best thing for being sad is to learn something. - Merlyn, in T. H. White's The Once and Future King

Contact information

Bruce Ikenaga's Home Page

Copyright 2020 by Bruce Ikenaga