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

\askaboutsolutions

\begin{document}

%% TUTORIAL 7: Sums, Products, Big Oh

\ifshowsolutions
  \tutsol{7}{October 18, 2001}{\stamp}
\else
  \tutprobn{7}{October 18, 2001}{\stamp}
\fi

\begin{problems}

%\printlayout

\problem Suppose you deposit \$100 into your MIT Credit Union account
today, \$99 in one month from now, \$98 in two months from now, and so on.
Given that the interest rate is constantly 0.3\% per month, how long will
it take to save \$5,000?

\solnospace{
First note that you will certainly manage to have saved \$5,000
\emph{some} day, since, even without your earnings from the interest,
you will have $100+99+\cdots+1=100\times 101/2 = 5,050$ dollars after
99~months. 

But fewer months will be needed: After the first deposit you will have
\$100. After the second deposit, you will have \$$(100\times 1.003 +
99)$. After you third deposit, your saved money will be \$$\bigl(
(100\times 1.003 + 99)\times 1.003 + 98) =$ \$$\bigl( 100\times
(1.003)^2 + 99\times 1.003 + 98\bigr)$, and so on. So, after the $n$th 
deposit,  
$$
S_n = \sum_{i=0}^{n-1} (100 - i) (1.003)^{n-i-1}
$$
dollars will be in your account. Substituting $j=n-i-1$, we can
rewrite this as  
$$
\sum_{j=0}^{n-1} \bigl( 100 - (n-j-1)\bigr) (1.003)^{j};
$$
and then as 
$$
(101-n) 
\Bigl( \sum_{j=0}^{n-1} (1.003)^{j}   \Bigr)+
\Bigl( \sum_{j=0}^{n-1} j (1.003)^{j} \Bigr).	
$$
We have closed forms for both of the sums, in Notes \#7. We can
substitute and then solve 
$$
S_n \geq 5,000
$$
for $n$.
}

\problem Riemann's Zeta Function $\zeta(k)$ is defined to be the infinite
summation:
\[
1+\frac1{2^k}+\frac1{3^k} \cdots = \sum_{j \ge 1} \frac1{j^k}
\]
Below is a proof that 
\[
\sum_{k \ge 2} (\zeta(k)-1) = 1
\]
Justify each line of the proof.
\begin{eqnarray}
\sum_{k \ge 2} (\zeta(k)-1) %
& = & \sum_{k \ge 2} \left[ \left( \sum_{j \ge 1} \frac{1}{j^k} \right) - 1 \right] \label{eq:1} \\
& = & \sum_{k \ge 2} \sum_{j \ge 2} \frac{1}{j^k} \label{eq:2} \\
& = & \sum_{j \ge 2} \sum_{k \ge 2} \frac{1}{j^k} \label{eq:3} \\
& = & \sum_{j \ge 2} \frac{1}{j^2} \sum_{k \geq 0} \frac{1}{j^k} \label{eq:4} \\
& = & \sum_{j \ge 2} \frac{1}{j^2} \cdot \frac{1}{1 - 1/j} \label{eq:5} \\
& = & \sum_{j \ge 2} \frac{1}{j (j - 1)} \label{eq:6} \\
& = & \lim_{n \rightarrow \infty} \sum_{j = 2}^{n} \frac{1}{j (j - 1)} \label{eq:7} \\
& = & \lim_{n \rightarrow \infty} \sum_{j = 2}^{n} \frac{1}{j-1} -\frac{1}{j} \label{eq:8} \\
& = & \lim_{n \rightarrow \infty} (1 - \frac{1}{n}) \label{eq:9} \\
& = & 1 \label{eq:10} 
\end{eqnarray}

\solnospace{
\eqref{eq:1}~Definition of $\zeta(k)$.
\eqref{eq:2}~Because ${\displaystyle \sum_{j \ge 1} \cfrac{1}{j^k} = 1 + \sum_{j \ge 2} \cfrac{1}{j^k}}$.
\eqref{eq:3}~Reordering; this is ok because at this point all terms are positive.
\eqref{eq:4}~Because 
$\displaystyle
\sum_{k \ge 2} \cfrac{1}{j^k} = 
\sum_{k \ge 0} \cfrac{1}{j^{k+2}} = 
\sum_{k \ge 0} \cfrac{1}{j^k\cdot j^2} =
\cfrac{1}{j^2} \sum_{k \ge 0} \cfrac{1}{j^k}
$.
\eqref{eq:5}~Theorem~2.2 from Notes~\#7.
\eqref{eq:6}~Algebra inside every summand.
\eqref{eq:7}~Definition of infinite summation.
\eqref{eq:8}~Algebra inside every summand.
\eqref{eq:9}~The sum telescopes: 1 is added once; every one of 
$\cfrac{1}{2}, \cfrac{1}{3}, \dots, \cfrac{1}{n-1}$ is subtracted once
and then added once; $\cfrac{1}{n}$ is subtracted once.
\eqref{eq:10}~Simple limits.
}

\problem \textbf{Asymptotic notation}
% problem 4, problem set 5, fall 1997

Given that $f(x) = O(g(x))$, prove or disprove the following:

\bparts

\ppart 
$f(x)^2 = O(g(x)^2)$

\solnospace{This equation holds.  Since $f(x) = O(g(x))$,
\[
\exists x_0,c\; \forall x \geq x_0, \abs{f(x)} \leq c\abs{g(x)}.
\]
So, $\forall x \geq x_0\, [f(x)^2 \leq c^2g(x)^2]$.  Therefore, there
exist $x_0' \eqdef x_0$ and $c' \eqdef 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)$.}

\ppart
$2^{f(x)} = O(2^{g(x)})$

\solnospace{This equation does not hold.  Let $f(x) \eqdef 2x$ and $g(x)
\eqdef 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, $4^x/2^x = 2^x$, so the
ratio grows without bound as $x$ grows---it is not bounded by a constant.}

\eparts

\end{problems}

\end{document}
