\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Fall 2004\\
\rm
Homework 1a\\
Due on Thursday, 09/02/04 (beginning of class)\\
\end{center}
\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] Growth of Functions.}
In this problem you will be doing two proofs by induction.  Please write
your proofs clearly, with a basis, induction hypothesis, and induction
step.


\begin{enumerate}
\item Use induction to show that $n^{2} \geq 2n+1$ for $n \geq 3$. 



\item Now use induction to show that $2^{n} \geq n^{2}$ for $n \geq 5$.  
(Using the result from part (a) of this problem will be most useful in 
doing this proof correctly!)



\end{enumerate}
\item {\bf [15 points] Extra Credit (due Friday at 6pm): Arithmetic and Geometric Meanings.}
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}
