final_quiz_review_2.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 60 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.}

Key things to review are all in-class activities about set theory and induction, plus the homework on set theory.

\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 \geq 0$ 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 Set theory and other problems}
\blist{0.2in}
\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.

\item Show that $A \cup B = A$ if and only if $B \subseteq A$.

\item Show that $A \subseteq C$ and $B \subseteq C$ if and only if $A \cup B \subseteq C$.

\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 we did in class.

\item For each $n = 1, 2, 3, \ldots,$ let $A_n$ be a set.
Show de Morgan's law:  $\left( \bigcup_{n = 1}^{\infty} A_n \right)^c = \bigcap_{n = 1}^{\infty} A_n^c$ by showing set containment in both directions.

\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 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.

\elist

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