\documentclass[12pt]{article}

\begin{document}
\begin{center} % Begin a centering environment
\bf % Begin boldfacing
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2007\
\rm % Roman (end boldfacing)
Homework 1a \\  % The \\ indicates a newline
Due Thursday, January 18  \\
\end{center} % End of the centering environment

\begin{itemize}  % Begin an itemized list (each item is preceded by a bullet when typeset)
	\item This assignment must be typeset using \LaTeX.  You are welcome to start with this
file and modify it.  (The \LaTeX file is posted on the Algorithms website in the ``Assignments'' section.)
	\item Note that the margins here are very wide!  This is the default setting in \LaTeX.  Please use this setting as it allows the grutors room to write comments to you in the margins.
	\item Please recall that homeworks are due at the beginning of the next
class.
	\item This homework set is intended to review a few mathematical
fundamentals that we'll be using extensively.
	item Bonus problems are optional and should be turned in on a separate sheet.  You are strongly encouraged to work on bonus problems when you can.  They will provide you with deeper understanding of the material and can bump up your homework score significantly. 
	\item An important part of being a computer scientist or mathematician
is the ability to express solutions clearly and thoroughly.
Therefore, you are expected to explain each step of your solution
and to present your solutions clearly and precisely.  A portion of the score on each problem will be for quality of presentation.
\end{itemize} % End of the itemized list

\begin{enumerate} % Begin an enumerated list.  LaTeX will number the items sequentiallly.

\item \textbf{ [15 Points] Properties of Logs.} \\  %textbf{blah blah blah} just boldfaces the stuff in braces
The objective of this problem is to remind you of some important identities of logarithms that we'll be using throughout the course.

% Here's some math!  The $ symbol begins typesetting in math mode until the next $ is found.
% There are many mathematical functions that LaTeX knows about.  For example \log is the logarithm
% function.  Anytime you have something like \log_{b} LaTeX interprets the underscore to mean
% "subscript" and the contents of the stuff in braces as the stuff to put in the subscript.  Similarly,
% b^{blah} means that blah is the superscript. The $\ell$ here is a nice script lower case letter "l".
% You could use just a regular "l", but it looks to much like the digit one: "1".
Let's begin by proving that $\log_{b} xy = \log_{b} x + \log_{b} y$.
The proof goes as follows:
Let
$k = \log_{b} xy$, $\ell = \log_{b} x$, and $m = \log_{b} y$.
Then,
$b^{k} = xy$, $b^{\ell} = x$, and $b^{m} = y$, by the definition of the
logarithm.
Thus, $b^{k} = b^{\ell} b^{m} = b^{\ell + m}$
by properties of exponents.
Thus, $k = \ell + m$, which is what we had set out to prove.

Now give proofs for each of the following properties of logarithms.
Write your proofs out carefully.  You should assume that $a, b, c, n$
are positive real numbers (not necessarily integers).
        \begin{enumerate}
                \item $\log_{b} a^{n} = n \log_{b} a$.
                \item $\log_{b} a = \frac{\log_{c} a}{\log_{c} b}$.
                \item $a^{\log_{b} n} = n^{\log_{b} a}$.  (This result is sometimes called the ``log-switching theorem'' since it says that we can ``switch'' $a$ and $n$.)
        \end{enumerate}

\item \textbf{[10 Points] The Geometric Series.}
Please begin by reading the handout on writing good inductive proofs.
\begin{enumerate}
  	\item Use induction on $n$ to show that for all integers
$n \geq 0$ %\geq is the "greater than or equal symbols"
% What's below?  The \[ symbol on a line by itself enters into a math mode that is different from $
% that $ means math to be typeset within text whereas \[ ... \] means math to be typeset on its own 
% (as in a stand-alone formula, equation, etc.).
\[
1 + a + a^{2} + a^{3} + \ldots + a^{n} = \frac{a^{n+1} - 1}{a - 1}
\]
where $a$ is some arbitrary real number other than 1.
  	\item Explain where your induction proof relied on the fact that $a \neq
1$.
\end{enumerate}

\item \textbf{[10 Points] The Flash Psychic!}
The objective of this problem is to reinforce clear and precise writing on mathematical material.

Take a look at the ``Flash Mind Reader'' at:
% The verbatim environment typesets text verbatim, and does not subject its content to
% to interpretation by LaTeX.  This is good for URL's and other text with strange symbols that
% LaTeX might otherwise try to interpret as its own special instructions.
\begin{verbatim}
http://www.cs.hmc.edu/courses/2007/spring/cs140/homework/psychic.swf
\end{verbatim}
and also linked from the Homework page from the course website.

Write a clear and precise explanation of how this works.  That is, explain the mathematics behind this trick.  

\item \textbf{ [20 Points] OPTIONAL BONUS PROBLEM!}
{\bf The Arithmetic and Geometric Means.}
Let $x_{1}, \ldots, x_{n}$ be positive real numbers.  The {\em arithmetic
mean} of these numbers is defined to be $\frac{x_{1} + x_{2} + \ldots + x_{n}}{\
n}$ and the {\em geometric mean} is defined to be
$(x_{1}x_{2} \cdots x_{n})^{1/n}$.
In this problem we show that the arithmetic mean of $n$ numbers is at least
as large as the geometric mean of those numbers.
        \begin{enumerate}
        \item Use induction to show that if $x_{1} x_{2} \cdots x_{n} = 1$
        then $x_{1} + x_{2} + \ldots + x_{n} \geq n$.
        Observe that this is a special case of the statement we are trying
        to prove.
        \item Use this fact to show that the arithmetic mean is at least
        as large as the geometric mean.  (No induction required here; just
        a little algebra.)
        \end{enumerate}

\end{enumerate}
\end{document}

