\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}

\begin{document}

{\bf Tutorial 5 Solutions}

\date{}

\section{}
\begin{enumerate}
\item
Is a Harvard degree really worth more than an MIT degree?!
Let us say that a person with a harvard degree earns $\$10,000i$ in 
his/her $i^{th}$ year after graduation, whereas a person with an MIT
degree earns $\$1000i^2$ after their $i^{th}$ year.  
This is before taking inflation into account.
Assume inflation is a fixed $8\%$ every year. That is $\$(1+p)$ 
a year from now is worth $1 today ($p = 0.08).

\begin{enumerate}
\item How much is a Harvard degree holder worth $n$ years after 
graduation (in terms of today's currency value) ?

\item How much is an MIT degree worth in $n$ years?

\item Is a Harvard person always worth more? If not, after how
many years is an MIT person worth more ?

\end{enumerate}

One dollar after year $i$ is worth $\frac{1}{(1+p)^i}$ in today's currency.

So $$H_n = \sum_{i=1}^{n} {10000i \over (1+p)^i}$$
$$M_n = \sum_{i=1}^{n} {1000i^2 \over (1+p)^i}$$
\begin{enumerate}
\item From lecture the sum 
$$\sum_{i=0}^{n} ix^i = 
{x - (n+1) x^{n+1} + n x^{n+2} \over (1-x)^2}$$
So $$H_n = 10000({x - (n+1) x^{n+1} + n x^{n+2} \over (1-x)^2})$$
for $x = 1/1.08$.

\item To calculate the sum $\sum_{i=0}^n i^2x^i$, let us
differentiate both sides of 
$$\sum_{i=0}^n ix^i = {x - (n+1) x^{n+1} + n x^{n+2} \over (1-x)^2}$$
$$\sum_{i=0}^{n}i^2 x^{i-1} ={(1-x)^2(1-(n+1)^2x^n +n(n+2)x^{n+1}) +2(1-x)(x-(n+1)x^{n+1}+nx^{n+2}) \over (1-x)^4}$$
$$= {1 + x - (n+1)^2x^{n} + (2n^2+2n-1)x^{n+1} -n^2x^{n+2} \over (1-x)^3}$$
Multiplying both sides by $x$ we have:
$$\sum_{i=0}^{n}i^2 x^{i} = {x + x^2 - (n+1)^2x^{n+1} + (2n^2+2n-1)x^{n+2} -n^2x^{n+3} \over (1-x)^3}$$ 

So $$M_n = 1000({x + x^2 - (n+1)^2x^{n+1} + (2n^2+2n-1)x^{n+2} -n^2x^{n+3} \over (1-x)^3})$$


\item Take $x = 1/1.08$ and solve for $n$ such that $M_n \geq H_n$. We see that
$n = 17$ is a long enough wait for an MIT student to get ahead. After 
17 years, the MIT graduate has earned $M_{17} = \$674,680.28$ while the
Harvard graduate has earned only $H_{17} = \$657,099.62$.

\end{enumerate}

\item Relate the following pairs of functions $f,g$ using asymptotic
symbols. E.g. $f(x) = O(g(x))$, $f(x) = \omega(g(x))$.  
\begin{enumerate}
\item $f(x) = x^{\log 2m}$, $g(x) = (2m)^{\log x}$
\item $f(x) = x^{\log x}$, $g(x) = (\log x)^x$
\item For integers $n$, $f(n) = 2^{{\cal H}_n}$, $g(n) = {\cal H}_{2^n}$. 
\end{enumerate}

\begin{enumerate}

\item Take logarithms on both sides.
$$\log f(x) = \log 2m \log x$$
$$\log g(x) = \log x \log 2m$$
So $f(x) = g(x)$. One could say $f(x) = \theta(g(x))$.

\item 
We can show that $f(x) = o(g(x))$.
Rewrite $f(x) = x^{\log_2 x} = 2^{(\log x)^2}$ and $g(x) = 2^{x \log \log x}$.
Then $$Lim_{x \rightarrow \infty} { f(x) \over g(x) } 
= Lim_{x \rightarrow \infty} {2^{(\log x)^2} \over 2^{x \log \log x}}$$
$$=Lim_{x \rightarrow \infty} {1 \over 2^{x \log \log x - (\log x)^2}}=0$$
%$$=Lim_{x \rightarrow \infty} {1 \over x^{\log x (x \frac{\log \log x}{(\log x)^2} - 1)}} = 0$$

\item We know that
$$\ln (n+1) \leq H_n \leq 1+ \ln n$$
Or $ n+1 \leq e^{H_n} \leq ne$

On the other hand, $ \ln (e^n) < \ln (e^n +1) \leq H_{e^n} \leq 1 + \ln (e^n)$.

That is $ n \leq H_{e^n} \leq n+1$.

From this we can say that $f(n) = O(g(n))$ by choosing $c = e, n_0 = 1$.
Also $g(n) = O(f(n))$ with $c=1, n_0 =1$. Hence $f(n) = \theta(g(n))$.

\end{enumerate}

\end{enumerate}

\end{document}

