\documentclass[12pt]{article}

\usepackage{fullpage}

\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168 \\
Fall 2003\\
Instructor: B Thom\\
\rm
Homework 1a\\
Due Thursday, Sept. 4\\
\end{center}
\vspace{0.5cm}

\begin{itemize}

\item The reading material for this week is Chapters 1, 2, and 3 of CLRS.
\item Please recall that homeworks are due at the \em{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 \em{should be turned in on a separate sheet}.
\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 write your solutions neatly.
The graders will deduct points for missing steps or solutions which they cannot easily read.
\item The homeworks sets are also posted on the course web page, both in pdf format as well
as in \LaTeX.  You are encouraged (but by no means required) to submit your homeworks
in \LaTeX.  
\end{itemize}

\begin{enumerate}
\item {\bf [15 points] Properties of Logs.} \\
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 \emph{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}$.
        \end{enumerate}

\item {\bf [10 points] The Geometric Series.}
\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 {\bf [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}

