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

\begin{document}
\psol{5}{October 10, 1997}

\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?


\bigskip

Present value of what the college loan officer offers
\begin{eqnarray*}
 & = & 22000 + 22000/1.08 + 22000/(1.08)^2 + 22000/(1.08)^3 \\
 & = & 22000(1 - \frac{1}{(1.08)^4})/(1 - \frac{1}{1.08}) \\
 & = & 22000 * 3.577\\
 & = & \$78,696.13
\end{eqnarray*}

Present value of what you must pay in return 
\begin{eqnarray*}
 & = & 10000/(1.08)^4 + 10000/(1.08)^5 + \ldots + 10000/(1.08)^{15} \\
 & = & (10000/(1.08)^4)(1 - \frac{1}{(1.08)^{12}})/(1 - \frac{1}{1.08}) \\
 & = & \$59,823.82
\end{eqnarray*}

This is a very fair deal for you!

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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}


\bigskip

\begin {enumerate}
\item 
Using partial fractions, we find that 
$\frac {1}{i(i+1)} = \frac {1}{i} - \frac {1}{i+1}$.

\begin{eqnarray*}
\sum_{i=1}^{n} \frac {1}{i(i+1)} & = & 
\sum_{i=1}^{n} \left(\frac {1}{i} - \frac {1}{i+1} \right)\\
& = & 1 + \sum_{i=2}^{n} \frac {1}{i} - \sum_{i=2}^{n+1} \frac {1}{i}\\
& = & 1- \frac{1}{n+1}\\
\end{eqnarray*}

Taking the limit in the above expression we conclude that 
$\sum_{i=1}^{\infty} \frac {1}{i(i+1)} = 1$.
  

\item

$ 1/n + 1/(n+1) + \ldots + 1/2n) \leq \int_{n-1}^{2n} \frac{1}{n} dn = \left. \ln n \right|_{n-1}^{2n} = \ln (\frac{2n}{n-1})$

$ 1/n + 1/(n+1) + \ldots + 1/2n) \geq \int_{n}^{2n+1} \frac{1}{n} dn = \left. \ln n \right|_{n}^{2n+1} = \ln (\frac{2n+1}{n}) $


$ \lim_{n \rightarrow \infty} \ln (\frac{2n+1}{n}) = \ln 2$

$ \lim_{n \rightarrow \infty} \ln (\frac{2n}{n-1}) = \ln 2$


The upper and lower bounds converge to $\ln 2$.

\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}


\bigskip

\[ n(\log_2 n)^5 = o(n^3) = \Theta(3\cdot 8^{\log_2 n} + 4^{\log_2 n}) = o(n!) = o(n^n) = o((n!)^2). \]

To get the last two equalities we use Stirling's formula
\begin{center}
$n! = \sqrt{2 \pi n} {\left({n \over e}\right)}^n e^{a_n}$, where 
${1 \over 12n+1} \leq  a_n \leq {1 \over 12n}$
\end{center}

We have

\[ {n! \over n^n} = 
{ \sqrt{2 \pi n} {\left({n \over e}\right)}^n e^{a_n} \over n^n } =
  \sqrt{2 \pi n} {\left({1 \over e}\right)}^n e^{a_n}
\]

Taking the limit $n \rightarrow \infty$ in the above expression 
we have $e^{a_n} \rightarrow 1$ and  
$\sqrt{2 \pi n} {\left({1 \over e}\right)}^n \rightarrow 0$ because
$n = o(e^n)$.  Therefore the whole expression goes to $0$.
We conclude that $n! = o(n^n)$.

To get the last equality, we have:
\[ {n^n \over (n!)^2} = 
{n^n \over (2 \pi n) {\left({n \over e}\right)}^{2n} e^{2a_n}} =
{1 \over (2 \pi n) {\left({n \over e^2}\right)}^n e^{2a_n}  } 
\]

The last expression goes to $0$ as $n \rightarrow \infty$, so we 
conclude that $n^n = o((n!)^2)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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.

\bigskip

\begin{enumerate}

\item
This does not follow. Let $f(x) = 2x$ and $g(x) = x$. Then 
$f(x) = O(g(x))$. Now $2^{f(x)} = 2^{2x} =  4^x$, and
$2^{g(x)} = 2^x$, and $4^x\neq O(2^x)$. Indeed,
$\frac{4^x}{2^x} = 2^x$, so the ratio grows without bound as $x$ grows--
it is not bounded by a constant.

\item
Yes.  Since  $f(x) = O(g(x))$,
$\exists x_0,c$ such that $\forall x \geq x_0, |f(x)| \leq cg(x)$.
So, $\forall x \geq x_0, f(x)^2 \leq c^2g(x)^2$.
Therefore, there exist $x_0' = x_0$ and $c' = c^2$ such that 
$\forall x \geq x_0', f(x)^2 \leq c'g(x)^2$.
So  $f(x)^2 = O(g(x)^2)$
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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

\begin{enumerate}
\item

\begin{eqnarray*}
\sum_{k=1}^{n} k^5 & \leq & \int_{1}^{n+1} x^5 dx\\
& = & \frac{(n+1)^6 -1}{6}\\
& \sim & n^6/6
\end{eqnarray*}

\begin{eqnarray*}
\sum_{k=1}^{n} k^5 & \geq & \int_{0}^{n} x^5 dx\\
& = & \frac{n^6}{6}\\
& \sim & n^6/6
\end{eqnarray*}

It follows that $\sum_{k=1}^{n} k^5 = \Theta(n^6/6)$.

\item

\begin{eqnarray*}
\sum_{k=1}^{n} \ln^2 k & \leq & \int_{1}^{n+1} \ln^2 x dx\\
& = & \int_{0}^{ln(n+1)} u^2 e^{u} du\\
& = & e^{\ln(n+1)}\ln^2(n+1) + \text{lower order stuff}\\
& = & O(n \ln^2 n)\\
\end{eqnarray*}

\begin{eqnarray*}
\sum_{k=1}^{n} \ln^2 k & \geq & \int_{1}^{n} \ln^2 x dx\\
& = & \int_{0}^{ln(n)} u^2 e^{u} du\\
& = & e^{\ln(n)}\ln^2(n) + \text{lower order stuff}\\
& = & \Omega(n \ln^2 n)\\
\end{eqnarray*}

It follows that $\sum_{k=1}^{n} \ln^2 k = \Theta(n \ln^2 n)$.

\item
\begin{eqnarray*}
\sum_{k=1}^n \frac{1}{\sqrt{k}} & \leq & \int_{0}^{n}\frac{1}{\sqrt{x}} dx\\
& = & 2 \sqrt{n}\\
& \sim & 2 \sqrt{n}
\end{eqnarray*}

\begin{eqnarray*}
\sum_{k=1}^n \frac{1}{\sqrt{k}} & \geq & \int_{1}^{n+1}\frac{1}{\sqrt{x}} dx\\
& = & 2 (\sqrt{n+1} - 1)\\
& \sim & 2\sqrt{n}
\end{eqnarray*}

It follows that $\sum_{k=1}^n \frac{1}{\sqrt{k}} = \Theta(2 \sqrt{n})$.
 
\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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}

\bigskip


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

Now we compute  
$\sum_{p=1}^{\infty} \sum_{q=p}^{\infty} {pq \over 2}x^{p/2}y^q$.

\begin{eqnarray*}
\sum_{q=p}^{\infty}{pq \over 2}x^{p/2}y^q & = &
{p \over 2}x^{p/2} \sum_{q=p}^{\infty}q y^q\\
& = & {p \over 2}x^{p/2} \left( \sum_{q=1}^{\infty}q y^q
- \sum_{q=1}^{p-1}q y^q \right)\\
%& = & {p \over 2}x^{p/2} y \sum_{q=p}^{\infty} {d \over dy} y^q\\
%& = & {p \over 2}x^{p/2} y {d \over dy} {y^p \over 1-y}\\
& = & {p \over 2}x^{p/2} y 
\left( {py^{p-1} \over 1-y} - {y^p \over (1-y)^2} \right)\\
\end{eqnarray*}


We know from tutorial that

$$
\sum_{k=1}^{\infty} k^2 a^k = {2a^2 \over (1-a)^3} - {a \over (1-a)^2}
$$

We will use this to compute the sum over $p$.

\begin{eqnarray*}
\sum_{p=1}^{\infty} \sum_{q=p}^{\infty} {pq \over 2}x^{p/2}y^q & = &
\sum_{p=1}^{\infty} {p \over 2}x^{p/2} y
\left( {py^{p-1} \over 1-y} - {y^p \over (1-y)^2} \right)\\
& = & {1 \over 2(1-y)} \sum_{p=1}^{\infty} p^2 (yx^{1/2})^p
- {y \over 2(1-y)^2} \sum_{p=1}^{\infty} p(yx^{1/2})^p\\ 
& = & {1 \over 2(1-y)} \left( {2xy^2 \over (1-yx^{1/2})^2} 
- {yx^{1/2} \over (1-yx^{1/2})^2} \right) 
- {y \over 2(1-y)^2} {yx^{1/2} \over (1-yx^{1/2})^2}
\end{eqnarray*}

Therefore the final result is

\[
\prod_{p=1}^{\infty} \prod_{q=p}^{\infty} e^{ -{pq \over 2}x^{p/2}y^q} =
exp{\left(  {1 \over 2(1-y)} \left( {2xy^2 \over (1-yx^{1/2})^2} 
- {yx^{1/2} \over (1-yx^{1/2})^2} \right) 
- {y \over 2(1-y)^2} {yx^{1/2} \over (1-yx^{1/2})^2} \right) }
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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


\begin{enumerate}
\item
 For $x>2$ we certainly have $\floor{x+1/2} \leq 2x$, and also
$x\leq 2\floor{x+1/2}$.
\item
 For $x>2$, $\log(x^2+1)\leq \log(2x^2) = 1 + 2\log x\leq 3\log x$
(recall that $\log$ means $\log_2$). On the other hand, since
$x < x^2+1$ for all positive $x$, we have $\log x \leq \log(x^2+1)$.
\item
This follows from the fact that $\log_{10}{x} = C(\log_2{x})$,
where $C = 1/\log_2{10}$.
\item
Clearly $n!\leq n^n,~\forall~n\geq 1$. Therefore, 
$\log(n!) \leq \log(n^n) = n\log n$. Thus, $\log(n!) = O(n\log n)$.

Approximate $\log(n!)$ with
{\em Stirling's formula} for $n!$ to get:
\begin{eqnarray*}
\log(n!) &=& \log(\sqrt{2\pi n}\left ( {n}\over {e} \right )^ne^{a_n}) ~~~~~~\mbox{where~ ${1\over{12n+1}}\leq a_n \leq {1\over{12n}}$}\\
         &=& \log{\sqrt{2\pi n}} + \log{n^n} - \log{e^n} + \log{e^{a_n}}\\
         &=& \log{\sqrt{2\pi n}} + n\log{n} - n\log{e} + {a_n}\log{e}\\  
         &\geq& n\log{n} - n\log{e} \\
         &\geq& {1\over{2}}n\log n ~~~~~~\mbox{since~~ $n\log{e}\leq {n\over{2}}\log{n}$ ~~~for $n\geq e^2$}
\end{eqnarray*}
Hence, $\log(n!) = \Omega(n \log n)$, which together with part (a) implies
that $\log(n!) = \Theta(n \log n)$.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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
\]


\bigskip

We could use induction, or the following.

\begin{eqnarray*}
 \sum_{k=1}^n H_k & = & \sum_{k=1}^{n} \sum_{j=1}^k {1\over j} \\
 &=& \sum_{1\leq j\leq k\leq n} {1\over j} \\
 &=& \sum_{j=1}^{n} \sum_{k=j}^n {1\over j} \\
 &=& \sum_{j=1}^n{n-j+1\over j} \\
 &=& \sum_{j=1}^n\left({n+1\over j} - 1\right) \\
 &=& (n+1)\sum_{j=1}^{n}{1\over j}-n \\
 &=& (n+1)H_n - n
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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.

\bigskip

By bounding the above summation with integrals we can conclude that
$\sum_{i=1}^n i^3 \sim n^4/4$.

We try an expression of the form 
$n^4/4 + a_3 n^3 + a_2 n^2 + a_1 n + a_0$.

By setting $n=0$, we conclude that $a_0 = 0$.
By computing the values of the summation for $n =1,2,3$ we obtain

\begin{eqnarray*}
n=1 & 1 = 1/4 + a_3 + a_2 + a_1\\
n=2 & 9 = 1/4 + 8a_3 + 4a_2 + 2a_1\\
n=3 & 36 = 1/4 + 27a_3 + 9a_2 + 3a_1\\
\end{eqnarray*}

Solving this system of linear equations we obtain $a_1 = 0$,
$a_2 = 1/4$, and $a_3 = 1/2$.

so our guess is 
$\sum_{i=1}^n i^3 = n^4/4 + n^3/2 + n^2/4 = (n(n+1)/2)^2$.
We prove it by induction.


{\bf Base case:}
$n=1$

$1 = ((1 \cdot 2)/2)^2$

{\bf Inductive step:}

\begin{eqnarray*}
\sum_{i=1}^{n+1} i^3 & = & \sum_{i=1}^{n} i^3 + (n+1)^3\\
& = & (n(n+1)/2)^2 + (n+1)^3\\
& = & { (n+1)^2 \over 4} (n^2+4(n+1))\\
& = & { (n+1)^2 (n+2)^2 \over 4}\\
\end{eqnarray*}

The induction is complete.



 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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.

\bigskip

For some constants $c_1,c_2$ and $n_0 \in \nat$,
we have that $\forall n \geq n_0, c_1 n^{1.5} < f(n) < c_2 n^{1.5}$.

Let $L$ denote the constant $L = f(1) + \ldots + f(n_0)$.

\begin{eqnarray*}
\sum_{i=1}^n f(i) & \leq & c_2 \sum_{i=1}^n  n^{1.5}
+ f(1) + \ldots + f(n_0)\\
& \leq & c_2 \int_{1}^{n+1} x^{1.5} dx + L\\
& = & c_2 \frac{ (n+1)^{2.5} - 1}{2.5} + L\\
& \leq & c_2 2^{2.5} n^{2.5} + L\\
& \leq & (c_2 2^{2.5} + L) n^{2.5}\\
\end{eqnarray*}

\begin{eqnarray*}
\sum_{i=1}^n f(i) & \geq & c_1 \sum_{i=1}^n  n^{1.5}
+ f(1) + \ldots + f(n_0)\\
& \geq & c_1 \int_{0}^{n} x^{1.5} dx + L\\
& = & c_1 \frac{ n^{2.5}}{2.5} + L\\
& \geq & {c_1 \over 2.5} n^{2.5}\\
\end{eqnarray*}

We have found constants $c_1' = {c_1 \over 2.5}$ and
$c_2' = c_2 2^{2.5} + L$ such that
$ c_1' n^{2.5} \leq \sum_{i=1}^n f(i) \leq c_2' n^{2.5}$.
We conclude that $\sum_{i=1}^n f(i) = \Theta(n^{2.5})$.

\end{problems} 
\end{document}



