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

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{6}{October 17, 1996}{Start of Class, Tuesday, October 22}

{\bf Reading:} Sections 1.7--1.8
of {\it Discrete Mathematics and its Applications} by Kenneth H.
Rosen, Chapters 2--3 of CLR (Handout 17).

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf [15 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\%. Is this a fair deal?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf [15 points]}

Find a closed form expression $f(n)$ for 
$\displaystyle\sum_{i=1}^n{i^2x^i}$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%similar to 3.2-1
{\bf [15 points]} 

Show that $\sum_{k=1}^{\infty}{1/k^{3/2}}$ is bounded above by a constant.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf [15 points]}

Let $0 < x < 1$ and $0 < y < 1$. Evaluate the following infinite sum.
\[ 
\sum_{i=1}^\infty{\sum_{j=1}^\infty{{{ij}\over{2}}x^{i/2}}{y^{j+i/2}}}
\]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%problem 42, 1.8--problem 2.2-4, clr
{\bf [15 points]}
\bparts
\ppart Determine whether $\log(n!) = O(n\log{n})$. Justify your answer.
\ppart Determine whether $\log(n!) = \Theta(n\log{n})$. Justify your answer.
\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%1.8-30
{\bf [10 points]}

Suppose that $f(x) = O(g(x))$. Does it follow that $2^{f(x)} = O(2^{g(x)})$?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%1.8-22
{\bf [15 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})$.
\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems} 
\end{document}


