\documentstyle[12pt,twoside,amstex]{article}
\input{macros-course}

\begin{document}
\pset{5}{September 30, 1997}{Tuesday, October 7}

{\bf Reading assignment: Rosen 1.7-1.8 }

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
%A stupid annuity problem
\problem{\bf [10 points]}

A college loan officer offers you the following deal. He will give you 
\$22,000 at the start of each year for four years starting today to pay for 
your college tuition. In return, you must pay \$10,000 at the start of each 
year for twelve years starting in four years. The annual interest rate is
8\%. Compute the present value of the loan and of the return.
Is this a fair deal?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
%some limits
\problem{\bf [10 points]}

Compute the following limits.

\begin {enumerate}
\item $\sum_{i=1}^{\infty} \frac {1}{i(i+1)}$.
\item $ \lim_{n \rightarrow \infty}  1/n + 1/(n+1) + \ldots + 1/2n$
%\item $ \lim_{n \rightarrow \infty} \frac{n}{2^n} \sum_{k=1}^{n}\frac{2^k}{k}$

%{\it (Hint:  Write $S_n = \frac{n}{2^n} \sum_{k=1}^{n}\frac{2^k}{k}$ and try
%to express $S_n$ in terms of $S_{n-1}$.  Then take the limit.)}

\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
%Theta and o
\problem{\bf [10 points]}

Rank the following functions by order of growth; that is find an arrangement $g_1 = \alpha(g_2) = \alpha(g_3) = \ldots = \alpha(g_6)$ and state whether $\alpha$ is $o$ or $\Theta$ for each step.
\begin{itemize}
\item $n(\log_2 n)^5$
\item $n^3$
\item $n!$
\item $(n!)^2$
\item $n^n$
\item $3\cdot 8^{\log_2 n} + 4^{\log_2 n}$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
%Don't log the O's
\problem{\bf [10 points]}

Suppose that $f(x) = O(g(x))$.

\bparts
\ppart
Does it follow that $2^{f(x)} = O(2^{g(x)})$?
\ppart 
Does it follow that $f(x)^2 = O(g(x)^2)$?
\eparts

Prove your answer to both parts.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
%bounding summations
\problem{\bf [10 points]}

Give asymptotically tights bounds for the following summations.

\bparts

\ppart $\sum_{k=1}^{n} k^5$

%\ppart $\sum_{k=1}^{n} k^2 log^5 k$
 
\ppart $\sum_{k=1}^{n} \ln^2 k$

\ppart $\sum_{k=1}^n \frac{1}{\sqrt{k}}$

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
\problem{\bf [10 points]}

Given that $x<1$ and $y<1$, express the following in closed form

\begin{Large}
\begin{equation*}
\prod_{p=1}^{\infty} \prod_{q=p}^{\infty} e^{ -{pq \over 2}x^{p/2}y^q}
\end{equation*}
\end{Large}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
\problem{\bf [10 points]}

Show that
 
\bparts
\ppart $\floor{x+1/2} = \Theta(x)$.
\ppart $\log(x^2+1) = \Theta(\log_2{x})$.
\ppart $\log_{10}{x} = \Theta(\log_2{x})$.
\ppart $\log(n!) = \Theta(n\log{n})$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 8
\problem{\bf [10 points]}

Recall that the harmonic numbers are given by 
$H_n = \sum_{i=1}^{n} {1 \over i}$.
Prove that
\[
\sum_{k=1}^n H_k = (n+1)H_n-n
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%A nice result
%Problem 9
\problem{\bf [10 points]}

Find a closed form expression for $\sum_{i=1}^n i^3$. Prove it is correct.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 10

\problem {\bf [10 points]}

Suppose that $f(n) = \Theta(n^{1.5})$.  Find a tight theta bound for
$\sum_{i=1}^n f(i)$.  Prove that your answer is correct.

\end{problems} 
\end{document}



