\documentclass[12pt]{article}
\title{Math 187 Test III}
\author{Dr. Holmes}
\begin{document}
\maketitle
This test will last from 7:50 am to 9:30 pm. You are allowed to use a
plain scientific calculator with no graphing or symbolic computation
capabilities. Your grade will be posted on the web by the ID number
on the first page of your paper. Cell phones must be turned off and
out of sight.
\newpage
\begin{enumerate}
\item
Do two of the three mathematical induction problems. These count as
two separate problems on the test, not as two parts of one question.
If you do all three, your best two problems will count, and success on
all three may yield some extra credit (don't try for a third until you
have completed the rest of the test!)
\begin{enumerate}
\item Prove by mathematical induction that the sum of the first $n$ numbers is
$\frac{n(n+1)}2$.
\newpage
\item Prove by mathematical induction that for each natural number
$n$, $4^n-1$ is divisible by 3. You may use the fact that the sum or
difference of two numbers both divisible by 3 is also divisible by 3.
\newpage
\item Prove by mathematical induction that the sequence defined by
$a_0=3;a_1=7;a_{n+2} = 5a_{n+1}-6a_n$ satisfies $a_n=2^{n+1}+3^n$ for
each natural number $n$.
\newpage
\end{enumerate}
\item Compute the first six terms of the sequence defined by the recurrence relation
$$a_0=1; a_1=1;a_{n+2} = 3a_{n+1}-2a_n.$$ Find a formula for this
sequence.
\newpage
\item
Write the function defined by $f(x)=2x+1$ with domain $\{1,2,3,4\}$ in
set notation (listing all of its elements). What is the image (or
range) of this function? Write the image in set notation, listing all
of its elements.
\newpage
\item How many functions are there from $A=\{2,3,4\}$ to $B=\{5,6,7,8,9\}$?
How many of these functions are one-to-one? How many of them are onto
$B$?
\vspace{2 in}
Write one of these functions which is not one-to-one and explain why
it is not one-to-one (mentioning specific elements of $A$).
\vspace{2 in}
Write one of these functions which is not onto $B$ and explain why it
is not onto $B$ (mentioning specific elements of $B$).
\vspace{2 in}
\newpage
\item Use the Pigeonhole Principle to explain why any collection of
12 positive integers must contain two numbers whose difference is
divisible by 10. Your answer should make it clear that you understand
what the Pigeonhole Principle says (you may express it informally).
\newpage
\item Two functions $f$ and $g$ are given in set notation. Compute each of
$f^{-1}$ and $g^{-1}$ or explain why it does not exist (be specific in your
explanation, mentioning specific numbers). Compute each of $f \circ g$
and $g \circ f$ or explain why it does not exist (again, mention specific
numbers in your explanation). Functions in this problem should be written
in set notation, listing all their elements.
It might help to draw arrow diagrams of the functions.
$f = \{(1,3),(2,2),(3,5),(4,4)\}$
$g = \{(2,1),(3,1),(4,5),(5,5)\}$
\newpage
\item
One permutation $\sigma$ is given in array notation and one
permutation $\tau$ is given in cycle notation. Convert $\sigma$ to
cycle notation and $\tau$ to array notation.
$$\sigma = \left[\begin{array}{ccccccc}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 3 & 1 & 5 & 7 & 6 & 4\\ \end{array}\right]$$
$$\tau = (1 2 4 5)(3 6 7)$$
\vspace{2.5 in}
Each of the following computations can be done in array notation or
cycle notation as you prefer: compute $\sigma^{-1}$ and $\sigma\circ \tau$.
Be careful about the order of composition!
\vspace{2.5 in}
(problem continues next page)
\newpage
Write each of $\sigma$ and $\tau$ as a composition of transpositions,
and classify each as an even or odd permutation.
\vspace{2.5 in}
What is the smallest positive integer $k$ such that $\rho^k$ is the
identity function, where $\rho$ is the permutation $(2 3 4 5)(1 6 7 8
9 10)$ in $S_{10}$? Explain briefly.
\vspace{2.5 in}
\end{enumerate}
\end{document}