\documentclass[12pt]{article}
\textwidth = 6.5 in
\textheight = 9 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,gastex}
\def\rmdefault{bch} % Use Charter for main text font.

\def\BOX#1{\fbox{\vbox to #1{\vss\hbox to #1{\hss}}}}
\def\Bigbox{\BOX{0.25in}}
\def\Bigbox{\raisebox{-0.5ex}[0.25in][0pt]{\BOX{0.25in}}}

\newcommand{\headers}[3]{
   \newpage\setcounter{page}{1}
   \def\@oddhead{$\underline{\hbox to\textwidth{%
	\textbf{\rlap{#1}\phantom{hj}\hfill #2 \hfill \llap{#3}}}}$}
   \def\@oddfoot{\hfill\thepage\hfill}
}


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

\headers{CS 173}{Homework 1 (due 4 September)}{Fall 2009}

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

This homework contains 5 problems worth a total of 40 points.
It is due on Friday, September 4th at noon.   For this week, homeworks
can be turned in at class or, after class, at Margaret's office
(3214 Siebel).   If the door is shut, push the homework under the door.
This is a temporary arrangement until they work out the last few
details so we can use the newly installed dropboxes.  

\end{center}


\bigskip\hrule

\begin{enumerate}

%----------------------------------------------------------------------
\item \textbf{[10 points] Logarithms, Exponents, etc}

Simplify the following expressions as much as possible,
\textbf{without using a calculator (either hardware or software)}.
Do not approximate. Express all rational numbers as fractions. 
For complex numbers use $i$ to represent the value $\sqrt{-1}$.
Show your work.

\begin{enumerate}
\item $\frac{(2^3 \times 2^5)^{10}}{512}$
\item $\lfloor -4.6\rfloor + \lceil -4.6\rceil$
\item $(\log_2 13)(\log_{13} 2048)$
\item $\frac{\log_3(81^k)}{7k}$
\item $(1+i)(2-i)(3-i)$
\end{enumerate}


%----------------------------------------------------------------------
\item \textbf{[7 points] Manipulating equations}

\begin{enumerate}
\item Suppose that $x^2 + 3x - 18 < 0$.   
Which interval(s) of the real line must $x$ belong to?  
Explain clearly why your answer is correct.

\item (1 point) What are the formulas for the sin and cosine of the angle $x+y$ in
terms of the sin and cosine of $x$ and the sin and cosine of $y$?   I.e.
go look them up in your favorite reference book or web page.

\item Using your answer to (b),
show that the following equality holds, where 
$x$ is a real number, $n$ is a natural number, and $i$ is $\sqrt{-1}$.

$$(\cos x + i \sin x)(\cos(nx) + i \sin(nx)) = \cos((n+1)x) + i \sin((n+1)x)$$

It's sufficient to give a
short sequence of equations with brief justifications.   

\end{enumerate}


%----------------------------------------------------------------------
\newpage
\item \textbf{[6 points] Functions}

Suppose we define functions $F$ and $G$ (on the real numbers) by 
$F(x) = x -6$ and $G(x) = x^2 + 8$.   Compute the values of the following,
simplifying as much as you can.   Show your work.

\begin{itemize}
\item $F(G(y))$
\item $G(F(y))$
\item $\frac{F(F(G(2)))}{F(\pi)}$
\end{itemize}



%----------------------------------------------------------------------
\item \textbf{[8 points] Summations}

Solve these short problems involving sums and products.   Show your work.
You can assume that all variables are integers.


\begin{enumerate}
\item Rewrite $\sum_{k=0}^n (k+1)\pi^{k}$ as a sum whose index runs from
4 to $n+4$.

\item Break up the sum $\sum_{j=1}^p j2^j$ into its first term plus
a sum containing the remaining terms.   That is, give us the $j=1$
term of this summation.   Then use 
summation notation to write an expression that contains all of
$\sum_{j=1}^p j2^j$ except for the first term.  

\item My homework partner claims that I can rewrite
$\sum_{k=1}^n k^2$ as $(\sum_{k=1}^n k)(\sum_{k=1}^n k)$?  Is he right?
Convince me that your answer is correct.

\item Evaluate this sum $\sum_{j=0}^n (4j^3 + 5)$.  That is, give an equivalent
expression which doesn't involve a summation.   (Table 2 in section 2.4 of Rosen
may be helpful here.)


\end{enumerate}

%----------------------------------------------------------------------
\item \textbf{[9 points] Propositional Logic}

\begin{enumerate}
\item Translate the following sentence into propositional logic.
Use the shorthand symbols (e.g. $\vee$) and define the meaning of
each of your propositional variables.   (See p. 11 of Rosen for
examples.)

\begin{quote}
If poison ivy grows around here and this plant has groups of three leaves, then
I need to wash my hands.
\end{quote}

\item For which values of $p$, $q$, and $r$ 
is the following logical expression true?

$$(\neg p \vee q) \wedge (q \rightarrow r) \wedge (\neg r \vee p)$$

Give a succinct description of which combinations of
input values work, rather than the whole truth table.

\item Show that these two expressions aren't logically equivalent, by
giving specific values for $p$, $q$, and $r$ for which the two expressions
produce different values.

$$(p \rightarrow q) \wedge r$$
$$p \rightarrow (q \wedge r)$$


\end{enumerate}


%----------------------------------------------------------------------
\end{enumerate}
\end{document}

