\documentstyle[12pt,epic,eepic,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{6}{October 29, 1996}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

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 too fair of a deal for you!

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
We first come up with a formula for ${\displaystyle \sum_{i=1}^n
i^2x^i}$ and then prove it using induction. From class notes we know that
\[{\displaystyle \sum_{i=1}^n ix^i} = \frac{x - (n+1)x^{n+1} + nx^{n+2}}{(1-x)^2}.\] 
Differentiating (with respect to $x$) the above expression and
multiplying with $x$ we find that 
\[{\displaystyle \sum_{i=1}^n i^2x^i} = \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3}\]

Proof by induction. Let $P(n)$ be the statement that 
\[{\displaystyle \sum_{i=1}^n i^2x^i} = \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3}.\]
Base Case. $P(1)$ is true since
\[{\displaystyle \sum_{i=1}^1 i^2x^i} = x = \frac{x+x^2-4x^2+3x^3-x^4}{(1-x)^3}.\]
Inductive Step. Assume $P(n)$ is true. Then
\begin{eqnarray*}
{\displaystyle \sum_{i=1}^n i^2x^i} + (n+1)^2x^{n+1} & = & \\
{\displaystyle \sum_{i=1}^{n+1} i^2x^i} & = & \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3} + (n+1)^2x^{n+1} \\
& = & \frac{x+x^2-(n+2)^2x^{n+2}+(2(n+1)^2+2(n+1)-1)x^{n+3}-(n+1)^2x^{n+4}}{(1-x)^3}
\end{eqnarray*}
Thus $P(n+1)$ is true. Hence, $P(n)$ is true for all $n$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

We use the integral method for bounding the infinite sum. Since 
$f(k)=\frac{1}{k^{3/2}}$ is monotonically decreasing for $k>1$, we have:
\begin{eqnarray*}
 \sum_{k=1}^\infty{1/{k^{3/2}}} &=& 1 + \sum_{k=2}^\infty{1/{k^{3/2}}} \\
                                &\leq& 1+ \int_1^\infty{\frac{1}{x^{3/2}}}dx\\
                                &=& 1 + \left [{\frac{-2}{\sqrt{x}}}\right ]_1^\infty\\
                                &=& 1 + (0 + 2)\\
                                &=& 3
\end{eqnarray*}
Hence, $\sum_{k=1}^\infty{1/{k^{3/2}}} \leq 3$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\begin{eqnarray*}
\sum_{i=1}^\infty{\sum_{j=1}^\infty{{{ij}\over{2}}x^{i/2}}{y^{j+i/2}}} &=&
{\frac{1}{2}}\cdot (\sum_{i=1}^\infty{i(\sqrt{xy})^i})\cdot (\sum_{j=1}^\infty{jy^j})\\
&=& {\frac{1}{2}}\cdot {\frac{\sqrt{xy}}{(1-\sqrt{xy})^2}}\cdot 
{\frac{y}{(1-y)^2}} \\
&=& {\frac{\sqrt{x}~y^{3/2}}{2{(1-\sqrt{xy})^2}{(1-y)^2}}}
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\bparts
\ppart
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)$.
\ppart If we show $\log(n!) = \Omega(n\log n)$, then together with part (a)
we have shown that $\log(n!) = \Theta(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)$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\bparts
\ppart For $x>2$ we certainly have $\floor{x+1/2} \leq 2x$, and also
$x\leq 2\floor{x+1/2}$.
\ppart 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)$.
\ppart This follows from the fact that $\log_{10}{x} = C(\log_2{x})$,
where $C = 1/\log_2{10}$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}

\end{document}





