\documentclass{article}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{enumerate}
\newcommand{\noi}{\noindent}
\newcommand{\Q}{\mathbb{Q}}
\renewcommand{\a}{\alpha}
\renewcommand{\b}{\beta}
\renewcommand{\c}{\gamma}
\renewcommand{\t}{\textrm}
\newcommand{\R}{\mathbb{R}}
\newcommand{\IFF}{\Leftrightarrow}
\newcommand{\thenif}{\Leftarrow}
\newcommand{\ifthen}{\Rightarrow}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\8}{\infty}
\newcommand{\bob}{
\begin{displaymath}
\begin{array}{l}
}
\newcommand{\killbob}{
\end{array}\right.
}
\newcommand{\spacer}{\vskip .1 in}
\newcommand{\N}{\mathbb N}
\newcommand{\F}{\mathbb F}
\newcommand{\C}{\mathbb C}
\newcommand{\rectangle}[1]{\begin{tabular}
{|c|}\hline \ensuremath{#1} \\ \hline\end{tabular}}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\sixth}{\frac{1}{6}}
\newcommand{\third}{\frac{1}{3}}
\newcommand{\ret}{vskip.1in}
\begin{document}
\begin{center}
{\Large Basic Algebra\\
Solutions to Assignment 1}
\end{center}
Let $S$ and $T$ be the sets $\{a,b,c\}$ and $\{x,y\}$ respectively.
\noi{\bf Question 1} Saying how many functions there are from $S$ to
$T$ amounts to counting how many ways we can ``send'' the elements
of $S$ into $T$. So we have that if $f:S\to T$ then:
\begin{displaymath}
\left.\begin{array}{ccc}
f(a) &=& \textrm{two choices i.e. $x$ or $y$}\\
f(b) &=& \textrm{two choices}\\
f(c) &=& \textrm{two choices}\\
\end{array}\right.
\end{displaymath}
which means that there are 8 possible functions from $S$ to $T$.
\spacer \noi{\bf Question 2} We try ``build'' injective functions.
Let $f:S\to T$, then $f(a)=$ either $x$ or $y$. So let's suppose
that $f(a)=x$ then because $f$ is injective $f(b) \neq f(a)$ so we
must have $f(b)=y$. Now $f(c)$ is either $x$ or $y$, both choices
yield a non injective function. Similarly if $f(a)=y$ we find that
it is also impossible to build an injective function. Having
exhausted all the possibilities we have that there are no injective
functions from $S$ to $T$. \spacer \noi{\bf Question 3} Here it's
easier to count how many functions are not surjective. Suppose
$f:S\to T$. Then if $f(a)=x$ then both $f(b)$ and $f(c)$ must be
also be $x$, otherwise we have that $f$ is surjective. Similarly if
$f(a) = y$, $f(b)=f(c)=y$. There being no other choices, we have
that there are only two non-surjective functions from $S$ to $T$,
which means all the other ones must be surjective. So there are
$8-2=6$ surjective functions from $S$ to $T$. \spacer \noi{\bf
Question 4} Let $f,g$ and $h$ be function from $X$ to $X$. {\bf
Claim:} $f(gh)= (fg)h$. (By the way, in calculus some may have seen
the composition of $f$ and $g$ denoted by $f\circ g$. In that
notation $f(gh) = f\circ(g\circ h)$).
\noi{\bf proof of claim:} We fix an arbitrary $x \in X$, we compute
$f(gh)(x)$. First, we find $gh(x)$. Let $h(x)=y$ and $g(y)=z$, then
$gh(x)=z$. Now let $f(z)=w$, since $gh(x)= z$ and $f(z)=w$ we get
that the composition $f(gh)(x)=w$.
Now we compute $(fg)h(x)$. We already have that $h(x)=y$. To find
$fg(y)$, we use $g(y)=z$, $f(z)=w$ from the previous part to get
$fg(y)=w$. It follows that the composition $(fg)h(x) = w =
f(gh)(x)$.
Since $x \in X$ is arbitrary, we infer that for each $x \in X$
$f(gh)(x)=(fg)h(x)$, which means that $f(gh)$ and $(fg)h$ are equal
as functions from $X$ to $X$.$\Box$ \spacer \noi{\bf Question 5} Let
$f$ and $g$ be functions from $\N$ to $\N$ given by the rules:
\begin{displaymath}
f(n)= \left\{ \begin{array}{cc}
43 & \textrm{if}~ n > 20\\
1 & \textrm{otherwise}\\
\end{array}\right.
~;~~~~g(n)= n + 10
\end{displaymath}
These are clearly well defined (but silly) functions. Now for
$n=11$, we compute $gf(11) = g(1) = 11$ and $fg(11) = f(21) = 43$.
For $n=11, gf(n) \neq fg(n)$, so $fg \neq gf$. \spacer \noi{\bf
Question 6} The binomial theorem states that for all $a,b$ in a
commutative ring (e.g $\Z, \Q, \R, \C$) and $n$, a positive integer
we have the identity:
\begin{displaymath}
(a+b)^{n}=\sum_{k=0}^{n}\big(_{k}^{n}\big)a^{k}b^{n-k}
\end{displaymath}
Letting $a=1, b=1$ we get $(1+1)^{n}=2^{n}=
\sum_{k=0}^{n}\big(_{k}^{n}\big)*1^{k}*1^{n-k} =
\sum_{k=0}^{n}\big(_{k}^{n}\big)$. Similarly setting $a=-1, b=1$
gives you the other equality. \spacer \noi{\bf Question 7} Compute
the gcd of 910091 and 3619 using the Euclidian algorithm.\[
\left.\begin{array}{llll}
910091 & = & 251*3619 & + 1722\\
3619 & = & 2*1722 & + 175 \\
1722 & = & 9*175& + 147\\
175 & = & 1*147 & + 28\\
147 & = & 5*28& +7\\
28 & = & 4*\rectangle{7}& + 0 \leftarrow \textrm{zero!}
\end{array}\right.
\]
So gcd(910091, 3619) = 7
\spacer
\noi{\bf Question 8} (i) Using induction (or otherwise) show that 7
divides $8^n-1$ for all $n\ge 0$.
\noi We give two different proofs.
\noi {\bf (Proof by induction)} We first verify the statement for
$n=0$:
\[ 8^0-1=1-1=0=0\times7. ~~~\surd\]
We now suppose that $7\mid 8^n-1$. It follows from this that
$7\mid8(8^n-1)$, and since obviously $7\mid7$, we conclude that
\[7\mid8(8^n-1)+7=8^{n+1}-1,\]
and we are done.
\spacer
\noi One can also apply the identity
\[a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+\cdots+ab^{n-2}+b^{n-1})\]
to get the result at one stroke by replacing $a$ with 8 and $b$ with
1: \[8^n-1=8^n-1^n=(8-1)(8^{n-1}+\cdots+1^{n-1}).\]
\spacer
\noi(ii) Use induction to show that 49 divides $8^n-7n-1$ for all
$n\ge0$.
\noi Once again we first verify the statement for $n=0$:
\[ 8^0-7\times0-1=1-1=0=0\times49. ~~~\surd\]
Now we assume that the statement to be proved is true for $n\ge0$
and then prove it for $n+1$. Quite akin to what we did in previous
case, it is enough to notice that
\[8^{n+1}-7(n+1)-1=8(8^n-7n-1)+49n.\]
\spacer
\noi{\bf Question 9} We must show that for all $a, b, n$ that
$a+(b+n)$ = $(a+b)+n$. The proof is by induction on $n$.
For $n=0$ we have that $a+(b+0) = a+b$ and $(a+b)+0 = a+b$ by the
fact that $x+0=x$ for all $x$.
Now suppose that this was true for all $m \leq n$, then for $S(n)$
we have:
\[\left.\begin{array}{llr}
(a+b)+S(n)& = S((a+b)+n) & \textrm{(by definition of $+$)} \\
& = S(a+(b+n)) &\textrm{(by induction hypothesis)} \\
& = a + S(b+n) &\textrm{(by definition of $+$)}\\
& = a + (b+S(n)) & \textrm{(by definition of $+$)}\\
\killbob\]
So associativity also holds for S(n). Thus, by induction,
associativity holds for all $n$.
\noi{\bf Question 10} Show that the expression
$1^{k}+\ldots+n^{k}$ can be written as a polynomial in $n$ of degree
at most $k+1$.
We start by proving this {\bf proposition}: If $F:\N \to \N$ is a
function such that $F(n+1)-F(n)$ is a polynomial of degree $k$ then
$F$ itself is a polynomial of degree $k+1$.
\noi{\bf Proof of proposition:} This is done by induction on $k$. If
$k=0$ then we have that $F(n+1)-F(n)=b$ a constant. Suppose $F(0)=a$
then we have that $F(n)=bn+a$ (check this, it's a straightforward
inductive proof.) So the claim is true for $k=0$
Now suppose that this was not true in general, let $k > 0$ be the
smallest positive integer such that there exist $F:\N \to \N$ such
that $F(n+1)-F(n)$ is a polynomial of degree $k$ but $F(n)$ is not
itself a polynomial of degree $k+1$. Let
$f(n)=a_{k}n^{k}+a_{k-1}n^{k-1}+\ldots a_{0} = F(n+1)-F(n)$. Let
$b=\frac{a_{k}}{k+1}$ and let $G(n) = F(n)+bn^{k+1}$. Consider
$g(n)=G(n+1)-G(n) = F(n+1)-F(n)-b(n+1)^{k+1}+bn^{k+1}$ with the
binomial theorem this expands to:
\[
g(n) = \underbrace{a_{k}n^{k}+\ldots+a_{0}}_{=F(n+1)-F(n)} -
b\Big(\sum_{i=0}^{k+1}\big(_{i}^{k+1}\big)n^{i}\Big) + bn^{k+1}\]
We see that the coefficient for $n^{k+1}$ in $g(n)$ is zero. For
$n^{k}$ we have that the coefficient in $g(n)$ is
$a_{k}-b*\big(_{k}^{k+1}\big)$ and we have that
$\big(_{k}^{k+1}\big)=k+1$ and since $b=\frac{a_{k}}{k+1}$, the
coefficient for $n^{k}$ is also zero. So $G(n+1)-G(n)$ is a
polynomial of degree $j$ for some $j k+1$ and $b_{m} \neq 0$. Then we have:\[\left.\begin{array}{rl} &
a_{k+1}n^{k+1}+\ldots+a_{0} =
b_{m}n^{m}+b_{m-1}n^{m-1}+\ldots+b_{0}\\
\iff &
b_{m}n^{m}+\ldots+(b_{k+1}-a_{k+1})n^{k+1}+\ldots+(b_{0}-a_{0})=0\\
\textrm{(dividing through by} ~n^{m}) &
b_{m}+\ldots+\frac{(b_{0}-a_{0})}{n^{m}}=0 ~~(\star)\\
\killbob \] for all $n$. Picking $n'$ sufficiently large, will yield
a contradiction. You can also take the limit of $(\star)$ as $n \to
\infty$. The left hand side tends to $b_{m}$.
\end{document}