\documentclass[12pt]{article}
\usepackage{geometry}

\begin{document}
	\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2012\\
	\rm
	Homework 1a\\
	Due Thursday, January 19  \\
\end{center}

\begin{itemize}
	\large
	\item \textbf{Please submit each problem separately.}
	\small\ \ For example, this assignment has three required problems, so you will have three separate submissions, one for Problem 1, one for Problem 2, and one for Problem 3 (and perhaps another for the bonus problem if you choose to do it).  Each submission should have your name on it and the problem number.  Each problem will go to a different grutor for grading, so please keep these submissions separate (not stapled to one another).
	
	\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 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. 
	\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}
\normalsize

\begin{enumerate}

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

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 (\emph{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 since we will be grading your solution to this problem (and others throughout this course) with a heavy emphasis on the quality of presentation.
\begin{enumerate}
  	\item Use induction on $n$ to show that for all integers $n \geq 0$
	\[
	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:
\begin{verbatim}
http://www.cs.hmc.edu/courses/2012/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 Bonus Points] OPTIONAL BONUS PROBLEM!}
\textbf{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$. 
                
        \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}

