\documentstyle[12pt]{report}
\newcommand{\sk}{\vskip 0.2in}
\begin{document}
\begin{center}
{\Huge 189-235A: Basic Algebra I} \\ \sk
{\Huge Assignment 1} \\ \sk
{\Large Due: Wednesday, September 21 }
\end{center}
\sk
\sk
\noindent
Let $S$ and $T$ be the sets $\{ a,b, c\}$and
$\{x,y\}$ respectively.
\noindent
1. How many functions are there from $S$ to $T$?
\noindent
2. How many injective
functions?
\noindent 3.
How many surjective functions?
\sk \noindent
Let $X$ be a set, and let ${\cal F}(X)$ be the set of all functions from
$X$ to itself. This set is equipped with a natural binary operation
$(f,g) \mapsto fg$ , given
by the composition of functions.
\noindent 4. Show that $f(gh) = (fg)h $ for all $f$, $g$, $h$ in ${\cal F}(X)$.
(In other words, the operation of composition of funcions is {\em associative}.)
\noindent 5. Show, by providing an example,
that $fg$ need not be equal to $gf$.
\noindent
6. Prove that $\sum_{k=0}^n \left(\frac{n}{k}\right) = 2^n$,
and that $\sum_{k=0}^n (-1)^k\left(\frac{n}{k}\right) = 0$,
using the binomial theorem.
\sk\noindent
7. Using the Euclidean algorithm compute the gcd of
$910091$ and $3619$. Show the steps in your calculation.
\sk\noindent
8. Using induction (or otherwise) show that $7$ divides $8^n-1$ for
all $n\ge 0$.
Use induction to show that $49$ divides
$8^n-7n-1$ for all $n\ge 0$.
\sk\noindent
9. Using induction, show that the addition law in $\mathbf N$ is associative
directly from the axioms defining addition in $\mathbf N$.
\sk\noindent
10. Show that the expression
$$ 1^k + 2^k + 3^k + \cdots + n^k $$
can be written as a polynomial in $n$ of degree at most $k+1$.
\end{document}