\documentclass[11pt]{article}
\usepackage{amsfonts}
\addtolength{\textwidth}{\oddsidemargin}  %i.e., left margin
\addtolength{\textwidth}{0.75in}
\addtolength{\textheight}{1in}
\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}

\begin{document}
\begin{center}
Intro to Mathematical Reasoning (Math 300) -- 
Homework 6\footnote{Version 2/22/04}
\end{center}

\begin{enumerate}
\item 
\begin{enumerate}
\item
Prove
that every positive integer can be written as the sum
of one or more distinct powers of 2. (Hint: Use the principle
of complete induction.  For the induction step, 
divide into cases according to whether $n$ is a power of
2 or not. (Here we say that a number is a power of 2 if
it is equal to $2^k$ for some nonnegative integer $k$).
In the case that
$n$ is not a power of 2, let $m$ be the largest
power of 2 that is less than or equal to $n$.
Apply the induction hypothesis to $n-m$.)
\item 
It is not true that every positive integer
can be written as the sum of one or more distinct powers of 3.
Therefore your argument in the previous problem should not
work if you modify the argument by replacing powers of
2 by powers of 3.  (If it {\em does} work for powers of 3, then there
is something wrong with your proof!  Find the error and correct it before
doing this problem.)
Explain precisely where your argument fails if you replace powers of 2
by powers of 3.
\end{enumerate}
\item
\begin{enumerate}
\item Give an example of a relation on $\{a,b,c,d\}$ that
is symmetric and reflexive but not transitive.
\item Give an example of a relation on $\{a,b,c,d\}$ that
is reflexive and transitive but not symmetric.
\item Give an example of a relation on $\{a,b,c,d\}$ that
is symmetric and transitive but not reflexive.
\item Is it possible to have a relation on $\{a,b,c,d\}$ that is neither
symmetric nor antisymmetric?  Explain.
\item Is it possible to have a relation on $\{a,b,c,d\}$ that is both
symmetric and antisymmetric?  Explain.
\end{enumerate}
\item
Let $Q$ be the relation defined on $\mathbb{R}$ consisting
of all ordered pairs $(x,y)$ such that $x<y+1$.
For each of the four properties in definition 4.1.8 determine
whether $Q$ satisfies the property.  In each case, carefully
prove your answer.
\item Do exercise 4.2.17 and  prove Theorem 4.2.18 in the book
\item
Prove Theorem 4.2.22 in the book.
\end{enumerate}



\end{document}










