final_quiz_review_1.tex

\activitytitle{Review questions for the final quiz}{Taken from a variety of sources without attribution.}

\overview{The final quiz will consist of approximately 6 questions and will be worth approximately 30 points.
I will try to make sure that it can be done by a prepared student in 2 hours.
The best way to prepare is to work out problems on the review sheet and on the handouts that we have had in class.}

\vspace{0.2in}

\noindent
{\bf Induction problems}
\blist{0.2in}
\item Show that $1 + 2 + 2^2 + 2^3 + \cdots + 2^n = 2^{n+1} - 1$ for all $n \geq 0$.
\item Show that $\sum_{j=0}^n r^j = \frac{r^{n+1} - 1}{r-1}$ for all $n$ and all real numbers $r \ne 1$.  (There is an easier formula when $r = 1!$)
\item Show that $2^n < n!$ for all $n \geq 4$.
\item Show that $3^n < n!$ for all $n \geq 7$.
\item Show that $n! < n^n$ for all $n > 1$.
\item Show that $1\cdot 2 + 2\cdot 3 +3 \cdot 4 + \cdots + n(n+1) = \frac{n(n+1)(n+2)}{3}$ for all $n \geq 1$.
\item Show that $1 + \frac{1}{4} + \frac{1}{9} + \cdots + \frac{1}{n^2} < 2-\frac{1}{n}$ for all $n \geq 2$.
\item Show that $n^5 - n$ is a multiple of 5 for all $n$.
\item Show that $n^2 - 1$ is a multiple of 8 for all odd $n$.
{\bf Hint:} You could try showing $P(1)$ and then show that $P(n)$ implies $P(n+2)$.
\item Draw $n$ lines in the plane such that no two lines are parallel and no three lines go through a common point.
Show that this divides the plane into $\frac{n^2+n+2}{2}$ regions.
{\bf Hint:} How many regions does the $n+1$st line add?
\item Show that $1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^n} \geq 1 + \frac{n}{2}$.  This is too hard for the final quiz, but you may enjoy working on it.  Notice that increasing $n$ by 1 will double the number of terms, unlike most of the other problems you have worked on.
This result shows that the harmonic series diverges.
\item Show that $5^n$ is odd for all $n \geq 0$.
\item Use the product rule to show that, for every integer $n \geq 1$, the derivative of $x^n$ is $n x^{n-1}$.
\elist

\pagebreak

\noindent
{\bf Sample problems}
\blist{0.2in}
\item Show that if $n$ is odd, then $n^2 + 2n - 7$ is a multiple of 4.
\item Let $a, b,$ and $c$ be integers.
Suppose that $b$ is a multiple of $a$ or $c$ is a multiple of $a$.
Show that $bc$ is a multiple of $a$.
\item Let $a$ and $b$ be integers.
Suppose that $a$ is a multiple of $b$ and that $b$ is a multiple of $a$.
Show that $a = \pm b$.

\item Suppose that $n$ is an integer and $n^2$ is a multiple of 5.
Show that $n$ is a multiple of 5.
Try to do this without looking back at your notes!

\item Suppose that $n$ is an odd integer.
Show that $n^3 - 25n$ is a multiple of 24.
This is similar to something we did in class.
See if you can do it that way.
Can you do it by induction instead?
Work with $P(n)$ and $P(n+2)$.
Which way is easier?

\item Show that an integer $n$ cannot be both even and odd.
What kind of proof did you use?

\item We used the Division Algorithm, number 73, a lot once we proved it.
It has both an existence part and a uniqueness part.
Please review the statements and arguments for both:

Suppose that $n$ and $k$ are positive integers.
Argue that there {\bf exist} integers $q$ and $r$ with $0 \leq r < k$ such that $n = kq + r$.

Suppose that $n = kq + r$ where $q$ and $r$ and integers and $0 \leq r < k$ and also that $n = ka + b$ where $a$ and $b$ are integers and $0 \leq b < k$.
Show that $q=a$ and $r=b$.

\item Suppose that $m$ and $n$ are integers and that $3m = 7n$.
Show that $n$ is a multiple of 3.
Do this by writing $n$ as $3q+r$ for different possible values of $r$.

\item Give a complete proof that $\sqrt{3}$ is irrational.

\item Show that $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ by showing containment in both directions and using cases.
Then show it again using logical statements such as $P = ``x \in A"$ and a truth table.
Try to do this without looking back at Problems 124 and 125.

\item Now that we have practiced inequalities, re--do Problem 130.

\item (Problem 133).  Let $I$ be a set, and for each $i$ in $I$, let $A_i$ be a set, all subsets of the same universe $X$.
Show de Morgan's law:  $\left( \bigcup_{i \in I} A_i \right)^c = \bigcap_{i \in I} A_i^c$ by showing set containment in both directions.

\item Show that $[2,5) \cap (3,7) = (3,5)$ by showing inclusion both ways.
Start by letting $x \in [2,5) \cap (3,7)$, so that $x \in [2,5)$ and $x \in (3,7)$, then write it as $2 \leq x < 5$ and $3 < x < 7$.
There are four inequalities here.  Soon enough you can conclude that $x \in (3,5)$.
Then show containment the other way as well.

\item Let $x > 0$.
Show that there exists an integer $n$ such that $0 < \frac{1}{n} < x$.

\item Show that $\bigcup_{n=1}^{\infty} [\frac{1}{n}, 1] = (0,1]$ by showing inclusion in both directions.
This should be easier now that we have practiced inequalities.

\item Do Problem 137, about unions.

\item Do Problem 138, about intersections.

\item This is a challenge involving two--dimensional sets and the Cartesian product.
Let $T = \{ (x,y) \in \R^2 : x \geq 0, y \geq 0, x+y\leq 1\}.$
Let $U = \bigcup_{0 \leq a \leq 1} [0,a]\times[0,1-a]$.
Show that $T = U$ by showing containment both directions.

\item Do problem 169, about relations.

\item Do problem 170, about relations.

\item Finish problems 225, 226, 227, 229, 230, 231 about absolute value.

\elist

\vfill          % pad the rest of the page with white space