\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Spring 2004\\
\rm
Homework 1a\\
Due on 1/22/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}
\end{enumerate}
\end{document}
