\documentclass[12pt]{article}
\textwidth = 6.7 in
\textheight = 9.2 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.2 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\usepackage{amsmath,amssymb,enumerate}
%\def\rmdefault{bch} % Use Charter for main text font.

% =========================================================
\begin{document}

\begin{center}
{\LARGE
\textbf{CS 173: Discrete Structures, Fall 2009}
\\
\textbf{Homework 6}
\\[1ex]}
\end{center}

This homework contains 5 problems worth a total of 50 regular points,
plus a 5-point bonus problem.
It is due on Friday, October 16 at noon.   Put your homework in
the appropriate dropbox in the Siebel basement.

Since the main point of this assignment is to learn how to write
proofs by induction, you must use this proof technique when the
problem says to use it, even if a non-inductive proof is also possible.


\begin{enumerate}
%----------------------------------------------------------------------
\item 
\textbf{Recursive definition [12 points]}



Give a simple closed-form definition 
for each of the following
recursively-defined subsets of the real plane.
Give both a precise definition using set-builder notation and
also an informal geometrical description using a picture and/or words.

\begin{enumerate}
\item The set $T$ defined by:

   \begin{enumerate}
   \item $(2,2) \in T$
   \item If $(x,y) \in T$, then $(y,x) \in T$.
   \item If $(x,y) \in T$, then $(-x,y) \in T$.
   \end{enumerate}

\item The set $S$ defined by:

   \begin{enumerate}
   \item $(2,2) \in S$
   \item If $(x,y) \in S$, and $n$ is any positive integer,
     then $(ny,nx) \in S$.
   \end{enumerate}

\item The set $M$ defined by:

   \begin{enumerate}
   \item $(2,2) \in M$
   \item If $(x,y) \in M$, then $(y,x) \in M$.
   \item If $(x,y) \in M$, then $(-x,y) \in M$.
   \item If $(x,y) \in M$, and $\alpha$ is any real number $\ge 1$,
     then $(\alpha y,\alpha x) \in M$.
   \end{enumerate}

\end{enumerate}


%----------------------------------------------------------------------
\item 
\textbf{Induction [10 points]} 

Use induction to prove that the following equation holds for
all positive integers $n$:

$$\sum_{k=1}^n \frac{1}{k(k+1)} = \frac{n}{n+1}$$

\newpage
%----------------------------------------------------------------------
\item 
\textbf{Son of induction [10 points]} 

Define a function $g: \mathbb{N} \rightarrow \mathbb{R}$  by

\begin{itemize}
\item   $g(0) = 0$
\item   $g(n) = n + 3g(n-1)$ for all integers $n \ge 1$
\end{itemize}

\begin{enumerate}
\item Calculate the next four values of $g$, 
i.e.  $g(1)$, $g(2)$, $g(3)$, $g(4)$.
\item Use induction to prove
that $g(n) = \frac{3^{n+1} - 2n -3}{4}$ for every integer $n \ge 0$.
\end{enumerate}


%----------------------------------------------------------------------
\item 
\textbf{Induction on congruences} [6 points]

We've proved that if $a \equiv b \pmod{p}$ and $c \equiv d \pmod{p}$, then
$a + c \equiv b+d \pmod{p}$ and $ac \equiv bd \pmod{p}$,
for any integers $a$, $b$, $c$, and $d$ and any positive integer $p$.
Using one or both of these facts and induction,
prove the following claim:

\begin{quote}
For any integers $a$ and $b$ and any positive integers $n$ and $p$,
if $a \equiv b \pmod{p}$, then $a^n \equiv b^n \pmod{p}$.
\end{quote}

%----------------------------------------------------------------------
\item 
\textbf{Function composition and strictly increasing [12 points]} 

In this problem, assume that the domain of each function
is a subset of the real numbers, e.g. the reals, the rationals, 
the even integers.   And assume the same for the co-domain.
With this assumption, 
recall that a function $f$ is strictly increasing if
$x < y$ implies that $f(x) < f(y)$.

\begin{enumerate}
\item If $f:A \rightarrow B$ is a strictly increasing function, prove that 
the reverse implication holds.   That is, that $f(x) < f(y)$ implies
that $x < y$.   Hint:  proof by contrapositive is one good approach.

\item Suppose that $f:A \rightarrow B$ and $g:B \rightarrow C$.
Prove that if $g$ and $g\circ f$ are both strictly increasing, 
$f$ is also strictly increasing.
(Hint: use the result from part a.)

\item If $f$ and $g\circ f$ are both strictly increasing, 
it is not necessarily the case that
$g$ is also strictly increasing.   Give a counter-example that
show why this implication fails.

\end{enumerate}

%----------------------------------------------------------------------
\item 
\textbf{BONUS:  Induction and geometry  [5 point]} 

Recall:  bonus means you don't have to do this problem, especially
if you are overloaded or having trouble with the previous problems.

Claim: Suppose that we draw any number of straight lines in the plane,
with the restriction that no two are parallel and no intersection
point belongs to more than two lines.  The lines divide up the plane
into a set of regions.   We're going to color each region red or green.
It is possible to choose the color for each region so that
adjacent regions never have the same color.

In this claim, ``adjacent'' means that the two regions share an edge.
Two regions touching at a single point are not considered adjacent.
Also remember that a ``line'' (as opposed to a ``line segment'') goes
off to infinity at both ends.   So each line cuts the plane into two pieces.

Use induction to prove this claim.


\end{enumerate}

\end{document}
