\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}

\begin{problems}

%BEGIN Kavita's problems
% Fall 1998

%**************
%   PSET 4    *
%**************
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)}

\begin{problemparts}

\problempart  Sum the following infinite series.

\[
\sum_{i=0}^{\infty} \frac{4^i - 3^i}{5^i}
\]

\solution{
\begin{eqnarray*}
\sum_{i=0}^{\infty} \frac{4^i - 3^i}{5^i}
	& = & \sum_{i=0}^{\infty} \left(\frac{4}{5}\right)^i -
	      \sum_{i=0}^{\infty} \left(\frac{3}{5}\right)^i \\
	& = & \frac{1}{1 - 4/5} - \frac{1}{1 - 3/5} \\
	& = & \frac{5}{2}
\end{eqnarray*}

In the first step, we split the one summation into two.  The second
step uses the formula for the sum of a geometric series.  The last
step is simplification.
}

\problempart For the following summation use the integral method to find
upper and lower bounds that differ by at most 0.1.  Note that you may
need to add the first few terms explicitly and then use integrals to
bound the sum of the remaining terms.

\[
\sum_{i=1}^{\infty} \frac{1}{i^2}
\]

\solution{
We can upper bound the summation as follows:

\begin{eqnarray*}
\sum_{i=1}^{\infty} \frac{1}{i^2}
	& \leq &	\frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
			\int_3^{\infty} \frac{1}{x^2} \ dx \\
	& = &		\frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
			\left( - \frac{1}{x} \right)_3^{\infty} \\
	& = &		\frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
			\frac{1}{3} \\
	& = &		1.694\ldots
\end{eqnarray*}

We can lower bound the summation similarly:

\begin{eqnarray*}
\sum_{i=1}^{\infty} \frac{1}{i^2}
	& \geq &	\frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
			\int_3^{\infty} \frac{1}{(x+1)^2} \ dx \\
	& = &		\frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
			\left( - \frac{1}{x+1} \right)_3^{\infty} \\
	& = &		\frac{1}{1} + \frac{1}{4} + \frac{1}{9} +
			\frac{1}{4} \\
	& = &		1.611\ldots
\end{eqnarray*}
}

(The actual value of the summation turns out to be $\pi^2 / 6 =
1.644\ldots$.)

\end{problemparts}


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

%END   Kavita's problems

%BEGIN Joe's problems
\problem %source: spring00 ps5
Consider the following summation:
\[\sum_{k=2}^n {\frac{1}{k(k-1)}}\] 

\begin{problemparts}
\problempart
Find a closed form solution for this summation.

\hint Try using partial fractions to break $\frac{1}{k(k-1)}$
into a difference of two terms.

\omitsolution{

  
  \medskip
  \textbf{Solution:} 

It is easy to find that $\frac{1}{k(k-1)} = \frac{1}{k-1} - \frac{1}{k}$.
So we have:
 
\begin{eqnarray*}
\sum_{k=2}^n {\frac{1}{k(k-1)}} & = & 
\sum_{k=2}^n \left(\frac{1}{k-1} - \frac{1}{k} \right)  \\
 & = & \sum_{k=2}^n \frac{1}{k-1} - \sum_{k=2}^n\frac{1}{k}  \\
 & = & \frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{n-2} + \frac{1}{n-1} \;\; -\\
 &   & \left[ \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n-1} + \frac{1}{n} \right]
\end{eqnarray*}

So all that does not cancel out is $1 - \frac{1}{n}$.


}

\problempart Use induction to verify your closed form solution (i.e.,
prove that it is correct).

\omitsolution{

  
  \medskip
  \textbf{Solution:} 

$P(n) := \left[ \sum_{k=2}^n {\frac{1}{k(k-1)}} = 1 - \frac{1}{n} \right] $

\emph{Base case:} $P(2)$ is true because the only term in the summation is
$\frac{1}{2(2-1)} = \frac{1}{2} = 1 - \frac{1}{2}$.

\emph{Inductive step:} Assuming $P(n)$, show $P(n+1)$.
\begin{eqnarray*}
\sum_{k=2}^{n+1} {\frac{1}{k(k-1)}} & = & 
\sum_{k=2}^{n} {\frac{1}{k(k-1)}} \; + \; \frac{1}{(n+1)(n)}  \\
 & = & 1 - \frac{1}{n} \; + \; \frac{1}{(n+1)(n)} 
 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\textbf{IH}  \\
 & = & 1 - \frac{n+1}{(n+1)n} \; + \; \frac{1}{(n+1)(n)}  \\
 & = & 1 - \frac{n}{(n+1)n}  \\
 & = & 1 - \frac{1}{n+1}  \\
\end{eqnarray*}

 

}

\end{problemparts}

\problem %source: spring00 ps5
Find closed-form expressions for the following sums:

\mbox{}

\begin{problemparts}

\problempart
\vspace{-2\baselineskip}
\[
\sum_{k=0}^n \frac{8^k - 5^k}{9^k}
\]

\omitsolution{

  
  \medskip
  \textbf{Solution:} 

\begin{eqnarray*}
\sum_{k=0}^n \frac{8^k - 5^k}{9^k} & = & 
\sum_{k=0}^n \left[ \frac{8^k}{9^k} - \frac{5^k}{9^k} \right]  \\
 & = & \sum_{k=0}^n \left[ \left(\frac{8}{9}\right)^k - \left(\frac{5}{9}\right)^k \right]  \\
 & = & \sum_{k=0}^n \left(\frac{8}{9}\right)^k - \sum_{k=0}^n \left(\frac{5}{9}\right)^k  \\
 & = & \frac{1 - \left(\frac{8}{9}\right)^{n+1}}{1 - \frac{8}{9}}  - 
       \frac{1 - \left(\frac{5}{9}\right)^{n+1}}{1 - \frac{5}{9}}  \\
 & = & \frac{1 + \frac{1}{3}\left(\frac{5}{9}\right)^{n+1} - \left(\frac{8}{9}\right)^{n+1}}{12}  \\
\end{eqnarray*}

\medskip


}


\problempart
\vspace{-2\baselineskip}
\[
\sum_{i=1}^n \sum_{j=0}^{\infty} i^{7/16} \cdot \left(1 - \frac{1}{4 i^{9/16}}\right)^j
\]

\omitsolution{

  
  \medskip
  \textbf{Solution:} 

This sum is actually just a sum of a geometric series followed by the sum 
of an arithmetic series.

\begin{eqnarray*}
\sum_{i=1}^n \sum_{j=0}^{\infty} i^{7/16} \cdot \left(1 - \frac{1}{4 i^{9/16}}\right)^j
        & = &   \sum_{i=1}^n i^{7/16} \cdot \frac{1}{1 - \left(1 - \frac{1}{4 i^{9/16}}\right)} \\
        & = &   \sum_{i=1}^n 4i \\
        & = &   2 n (n+1)
\end{eqnarray*}


}

\end{problemparts}

\problem %source: spring00 ps5

\textit{Note: This problem is only worth one point.  Give it some
  thought but don't exhaust yourself on it.}

Consider the sum of the following sequence:
\[1 - 1 + \frac{1}{2} - \frac{1}{2} + \frac{1}{3} - \frac{1}{3}
 + \frac{1}{4} - \frac{1}{4} + \frac{1}{5} - \frac{1}{5} + \ldots \]

To sum it, suppose we rearrange the terms and write it as:
\begin{eqnarray*}
 & (1 + \frac{1}{2} - 1) & +  \\
 & (\frac{1}{3} + \frac{1}{4} - \frac{1}{2}) & +  \\
 & (\frac{1}{5} + \frac{1}{6} - \frac{1}{3}) & +  \\
 & (\frac{1}{7} + \frac{1}{8} - \frac{1}{4}) & +  \\
 & \ldots & 
\end{eqnarray*}

which we can write as a summation as:
\[%
a = \sum_{n=1}^{\infty} \left( \frac{1}{2n-1} + \frac{1}{2n} - \frac{1}{n} \right) %
  = \sum_{n=1}^{\infty} \frac{1}{2n(2n-1)} %
\]

On the other hand, we arrange the original summation as
\begin{eqnarray*}
 & (1 - 1 - \frac{1}{2}) & +  \\
 & (\frac{1}{2} - \frac{1}{3} - \frac{1}{4}) & +  \\
 & (\frac{1}{3} - \frac{1}{5} - \frac{1}{6}) & +  \\
 & (\frac{1}{4} - \frac{1}{7} - \frac{1}{8}) & +  \\
 & \ldots &
\end{eqnarray*}
\[%
b = \sum_{n=1}^{\infty} \left( \frac{1}{n} - \frac{1}{2n-1} - \frac{1}{2n} \right) %
  = \sum_{n=1}^{\infty} \frac{-1}{2n(2n-1)} %
  = - a
\]

How is this possible?  Choose the correct response from the options
below. Be prepared to back up your answer.

%\begin{problemparts}
%\problempart
%I find the above somewhat disturbing, but I can't resolve it.
%\problempart
%Don't toy with me. Your petty tricks are no match for my superior mathematical skills.
%\problempart
%It's 4 am tuesday morning. I'm not even coherent enough to be disturbed.
%\end{problemparts}

\begin{itemize}
\item[\textbf{a)}] \ I find the above somewhat disturbing, but I can't
resolve it.
\item[\textbf{b)}] \ Don't toy with me. Your petty tricks are no match 
for my superior mathematical skills.
\item[\textbf{c)}] \ It's 4am Tuesday morning. I'm not even coherent enough
to be disturbed.
\end{itemize}

\omitsolution{

  
  \medskip
  \textbf{Solution:} 

        Of course, this is a personal question. However, if you answered \textbf{c}, you
really should get started earlier -- for your own good.

        Students who answered \textbf{b} may have seen a hint it the two harmonic summations
(positive and negative) hiding within the original series.
The original summation is only \emph{conditionally} convergent. (This means that
if you sum the absolute value of the terms, 
$2 \cdot \sum_{n=1}^{\infty} \frac{1}{n}$,
the summation is not finite). With such summations, you cannot freely rearrange the 
terms. In fact, there is a theorem that says that any series that converges but does
not converge \emph{absolutely} can be rearranged to form any real number.

        It is not insightful to declare that $ a = 0 = -0$. While this is part of the
contradiction above, it is clearly not the answer. Every term in the first summation
is positive. Every term in the second summation is negative. Neither can be zero, as
a result. In fact, they are somewhere around $\pm log(2)$. Similarly, it is not
adequate to say that the sums diverge or are not well-defined. Both summations, as
well as the original zero-sum, really do converge on finite numbers. 

        Don't worry about the details here. However, you should take from this a warning
about being too loose with your math, much as you must avoid making flawed but convincing
proofs.


}

\problem %source: spring00 ps6
Determine the flaw in the following reasoning and explain your answer.

\[
\left( \sum_{j=1}^n a_j \right) \left( \sum_{k=1}^n 1/a_k \right) =
\sum_{j=1}^n \sum_{k=1}^n a_j/a_k =
\sum_{k=1}^n \sum_{k=1}^n a_k/a_k =
\sum_{k=1}^n \sum_{k=1}^n 1 =
\sum_{k=1}^n n = n^2
\]

\solution{%
  not done yet!
  }

\problem %source: spring00 ps6
In this problem, we will prove that the ``average'' number of divisors
of a number of size about $n$ is ``about'' $\ln n$.  More formally,
let $t(n)$ be the number of divisors of the number $n$, and let
\[
T(n) = \frac{1}{n} \sum_{j=1}^n t(j)
\]
be the average number of divisors of all numbers less than or equal to
$n$.  Show that $T(n) \sim \ln n$.  

{\bf Hint:} Let the function $f(i,j)=1$ if $i$ is a divisor of $j$,
and $0$ otherwise.  What do the row and column sums of $f(i,j)$ mean?

\solution{%
  not done yet!
  }

\problem %source: spring00 ps7-5
% source: fall94 ps7
% topic: binomial theorem
inomial theorem to evaluate the expressions
\[\sum_{k=0}^{n}{n\choose k}r^k 
\;\;\mbox{ and }\;\;
\sum_{k=0}^{n}{n\choose k}(-r)^k\ .\]
%       (\hint $(-1)^k = \pm (-1)^{n-k}$.)
Use your analysis to conclude that if $r$ is odd, then
\[\left. 2^{n-1} \;\right| \sum_{\stackrel{\scriptstyle k=0}{k {\mathrm{\ even}}}}^{n}{n\choose k}r^{k}\ .\]

Note that if $r=1$, this sum simply counts the number of even-sized
subsets of an $n$-set, which we know is exactly $2^{n-1}$.


%END   Joe's problems

%BEGIN Ray's problems

%%%%%%%  S99 ps5


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


\problem {\bf (16 points)} Find closed-form expressions for the
following sums.

\begin{problemparts}

\iffalse

\problempart
\[
\sum_{i=0}^n \frac{9^n - 7^n}{11^n}
\]

\solution{Split the expression into two geometric series and then
apply the formula for the sum of a geometric series.

\begin{eqnarray*}
\sum_{i=0}^n \frac{9^i - 7^i}{11^i}
	& = &	\sum_{i=0}^n \left(\frac{9}{11}\right)^i -
		\sum_{i=0}^n \left(\frac{7}{11}\right)^i \\
	& = &	\frac{1 - \left(\frac{9}{11}\right)^{n+1}}{1 - \frac{9}{11}}
	      - \frac{1 - \left(\frac{7}{11}\right)^{n+1}}{1 - \frac{7}{11}} \\
	& = &	- \frac{11}{2} \cdot \left(\frac{9}{11}\right)^{n+1}
		+ \frac{11}{4} \cdot \left(\frac{7}{11}\right)^{n+1}
		+ \frac{11}{4}
\end{eqnarray*}

}
\fi

\problempart
\[
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \sum_{k=0}^{\infty} 2^{-(i +2j +3k)}
\]

\solution{ Apply the formula for the sum of a geometric series three
times.

\begin{eqnarray*}
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \sum_{k=0}^{\infty} 2^{-(i +2j +3k)}
	& = &	\sum_{i=0}^{\infty} 2^{-i} \cdot
		\left(\sum_{j=0}^{\infty} 2^{-2j} \cdot
		\left(\sum_{k=0}^{\infty} 2^{-3k} \right) \right) \\
	& = &	\sum_{i=0}^{\infty} 2^{-i} \cdot
		\left(\sum_{j=0}^{\infty} 2^{-2j} \cdot
		\frac{8}{7} \right) \\
	& = &	\sum_{i=0}^{\infty} 2^{-i} \cdot
		\frac{4}{3} \cdot \frac{8}{7} \\
	& = &	\frac{2}{1} \cdot \frac{4}{3} \cdot \frac{8}{7} \\
	& = &	\frac{64}{21}
\end{eqnarray*}
}

\iffalse

\problempart
\[
\sum_{i=n+1}^{2n} i^2
\]

\solution{
This expression is the difference of two sums of squares, which can be
reduced to a closed form by a standard formula.

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

\problempart
\[
\prod_{i=1}^{n} 3^{4i + 5}
\]

\solution{This product can be reduced to an easy sum by taking a
logarithm.

\begin{eqnarray*}
\prod_{i=1}^{n} 3^{4i + 5}
	& = &	3^{\log_3\left( \prod_{i=1}^{n} 3^{4i + 5} \right)} \\
	& = &	3^{\sum_{i=1}^n 4i+5} \\
	& = &	3^{2n(n+1) + 5n}
\end{eqnarray*}
}
\fi

\problempart

\[
\sum_{j=1}^n \sum_{i=0}^{\infty} j^{2/3} \cdot \left(1 - \frac{1}{2 j^{1/3}}\right)^i
\]

\solution{This fearsome-looking sum is a paper tiger; we just apply
the formula for the sum of a geometric series followed by the formula
for the sum of an arithmetic series.

\begin{eqnarray*}
\sum_{j=1}^n \sum_{i=0}^{\infty} j^{2/3} \cdot \left(1 - \frac{1}{2 j^{1/3}}\right)^i
	& = &	\sum_{j=1}^n j^{2/3} \cdot \frac{1}{1 - \left(1 - \frac{1}{2 j^{1/3}}\right)} \\
	& = &	\sum_{j=1}^n 2j \\
	& = &	n (n+1)
\end{eqnarray*}
}
\iffalse

\problempart

\[
\prod_{i=2}^{n} \left(1 - \frac{1}{i^2}\right)
\]

\solution{ We give two solutions.  First, evaluating a few terms
suggests that the product is equal to

\[
\frac{n+1}{2n}.
\]

We could verify this by induction.  The calculation needed for the
inductive step is shown below.

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

As an alternative approach, we might observe that this is a
``telescoping product''.

\begin{eqnarray*}
\prod_{i=2}^{n} \left(1 - \frac{1}{i^2}\right)
	& = & \prod_{i=2}^{n} \frac{(i-1)(i+1)}{i^2} \\
	& = & \frac{1 \cdot 3}{2 \cdot 2}
		\cdot \frac{2 \cdot 4}{3 \cdot 3}
		\cdot \frac{3 \cdot 5}{4 \cdot 4} \cdots
		\frac{(n-1) \cdot (n+1)}{n \cdot n} \\
	& = &	\frac{1}{2} \cdot {n+1}{n}
\end{eqnarray*}
}
\fi

\end{problemparts}



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

\problem {\bf (10 points)}  Let 
\[S_n ::= \sum_{k=1}^{n} 1/(2k-1) .\]

\bparts
\ppart Find a closed form expression for $S_n$ in terms of the harmonic
numbers $H_n$ and $H_{2n}$.

\ppart Use an approximation for the harmonic numbers to show that
\[
S_n = \ln(2 \sqrt{n}) + O(1).
\]

\solution{Recall that

\begin{eqnarray*}
H_n	& = &	\frac{1}{1}+\frac{1}{2}+\frac{1}{3} + \ldots +\frac{1}{n} \\
	& = &	\ln(n) + \gamma + o(1).
\end{eqnarray*}

where $\gamma = 0.577215\ldots$.  The sum in the problem can be
written as follows:

\begin{eqnarray*}
\sum_{k=1}^{n} \frac{1}{2k-1}
	& = &
\left(\frac{1}{1}+\frac{1}{2}+\frac{1}{3} + \ldots +\frac{1}{2n}\right) \\
	&   &	\mbox{} -
\left(\frac{1}{2}+\frac{1}{4}+\frac{1}{6} + \ldots +\frac{1}{2n}\right) \\
	& = &	H_{2n} - \frac{1}{2} \cdot H_{n} \\
	& = &	\ln(2n) + \gamma - \frac{1}{2} (\ln(n) - \gamma) + o(1) \\
	& = &	\ln\left(2 \sqrt{n}\right) + O(1)
\end{eqnarray*}
}
\eparts

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



%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset5 problem2 spring98 (Rosen 1.7, 11 and 12)
\problem \bparts

\ppart Find a closed form solution for \[\sum_{k=1}^n {1
/k(k+1)}\] \hint Use the fact that ${1 / k(k+1)}=1 / k - 1 / (k+1)$.

\solution{
We will use the fact that
\[\sum_{j=0}^{n-1} (a_j-a_{j+1}) = a_0 - a_n,\]
where $a_0, a_1, ..., a_n$ is a sequence of real numbers.  (This type of
sum is called {\em telescoping}, for obvious reasons).  This holds almost
by inspection: we can say that the $-a_{j+1}$ in one term of the summation
will be the $a_j$ in the subsequent term, and the only $a_j$'s that don't
cancel out in this manner are $a_0$, since there is no term before
$(a_0-a_1)$ in the summation, and $a_n$, since there is no term after
$(a_{n-1}-a_{n})$ in the summation.
Formally, this equation can be verified by an easy induction which
we omit.

Now (to get back to the problem at hand), using the given hint, 
$$\sum_{k=1}^n {1 \over {(k(k+1))}} = \sum_{k=1}^n {{1 \over k} - {1 \over {(k+1)}}}$$
Letting $a_i=\frac{1}{i+1}$, for $0\leq i \leq n-1$, the righthand sum above is
$$\sum_{i=0}^{n-1} (a_i - a_{i+1}) = a_0-a_n.$$
Now
\begin{eqnarray*}
a_0-a_n & = & {1 \over{0+ 1}} - {1 \over {n+1}} \\
&=& 1- {1 \over {n+1}}\\
&=& {n \over {n+1}}.
\end{eqnarray*}
}

\ppart Use induction to verify your closed form.

\solution{
Proof by induction. Let $P(n)$ be the statement that 
$$\forall n>1, \sum_{k=1}^n {1 \over {(k(k+1))}} = {n \over {n+1}}$$

Base Case. P(1) is true since
$$\sum_{k=1}^1 {1 \over {(k(k+1))}}={ 1 \over 2} = { 1 \over {1+1}}$$.

Inductive Step. Assume $P(n)$ is true. Then
\begin{eqnarray*}
\sum_{k=1}^{n+1} {1 \over {(k(k+1))}} &=&{1 \over {(n+1)((n+1)+1)}}  +  \sum_{k=1}^n {1 \over {(k(k+1))}}\\
&=& {1 \over {(n+1)(n+2)}}  + {n \over {n+1}}\\
&=&{ {n^2+2n+1} \over {(n+1)(n+2)}}\\
&=&{ {(n+1)^2} \over {(n+1)(n+2)}}\\
&=&{ {n+1} \over {((n+1)+1)}}\\
\end{eqnarray*}
Therefore by induction, 
$$\forall n>1, \sum_{k=1}^n {1 \over {(k(k+1))}} = {n \over {n+1}}$$
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset5 problem3 spring98
\problem 
Find a closed form solution for \[\prod_{i=1}^n 2 \cdot 4^i\]

\solution{
We know that $\prod_{i=1}^n 2 \cdot 4^i =(2\cdot4^1) \cdot (2\cdot4^2) \cdot ... \cdot (2\cdot4^n).$
Taking $\log_2$ of both sides of the equation gives us
\begin{eqnarray*}
\log_2(\prod_{i=1}^n 2\cdot4^i)&=&\log_2(2\cdot4^1 \cdot 2\cdot4^2 \cdot ... \cdot 2\cdot4^n)\\
&=&\log_2(2\cdot4^1)+\log_2(2\cdot4^2)+...+\log_2(2\cdot4^n)\\
&=&\sum_{j=1}^n\log_2(2\cdot4^j)\\
&=&\sum_{j=1}^n(\log_2(2) + \log_2(4^j))\\
&=&\sum_{j=1}^n (1 +  2j)\\
&=&n+n(n+1)\\
&=&n^2+2n.
\end{eqnarray*}
Now, exponentiating both sides of the equation gives
$\prod_{i=1}^n 2\cdot4^i=2^{n^2+2n}$
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset5 problem4 spring98 (from fall95 pset6, revised)
\problem 

 	Let $0< x < 1$ and $0 < y < 1$.  Evaluate the following infinite sums.
\bparts
\ppart $$\sum_{i=1}^{\infty} \sum_{j=1}^{\infty} x^i y^{i+2j}.$$

\solution {
\begin{eqnarray*}
\sum_{i=1}^\infty \sum_{j=1}^\infty x^iy^{i+2j}
 & = &  \sum_{i=1}^\infty [(xy)^i (\sum_{j=1}^\infty (y^2)^j)] \\
 & = &  \sum_{i=1}^\infty [(xy)^i (y^2/(1-y^2))]\\
 & = &  [\sum_{i=1}^\infty (xy)^i] y^2/(1-y^2)\\
 & = & [xy/(1-xy)] y^2/(1-y^2) \\
 & = & (xy^3)/(1-xy)(1-y^2).
\end{eqnarray*}
}

\ppart $$\sum_{i=1}^{\infty} \sum_{j=1}^{\infty} ij x^i y^j.$$

\solution{
\begin{eqnarray*}
{\displaystyle \sum_{i=1}^\infty \sum_{j=1}^\infty ijx^iy^j} & = & {\displaystyle \sum_{i=1}^\infty [ix^i (\sum_{j=1}^\infty jy^j)]} \\
 & = & {\displaystyle [\sum_{i=1}^\infty ix^i] (\sum_{j=1}^\infty jy^j)} \\
 & = & [x/(1-x)^2] y/(1-y)^2 \\
 & = & (xy)/((1-x)(1-y))^2
\end{eqnarray*}
}

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset5 problem8 spring98 (from fall95 pset6, revised)
\problem 
\bparts
\ppart Find a closed form solution for
$\sum_{i=1}^n i^2x^i$.

\solution{
From lecture 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 
\begin{eqnarray*}
{\displaystyle \sum_{i=1}^n i^2x^{i-1}} &=& \frac{1+x-(n+1)^2x^{n}+(2n^2+2n-1)x^{n+1}-n^2x^{n+2}}{(1-x)^3}\\
{\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}
\end{eqnarray*}
}

\ppart Verify your closed form by induction.

\solution{
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+1} i^2x^i}
& = & {\displaystyle \sum_{i=1}^n i^2x^i} + (n+1)^2x^{n+1} \\
 & = & \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$.
}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset5 problem9 spring98
\problem 

Let $S_n = \sum_{i=1}^n i^{1 /3}$.  Use the integral method to determine
\[\lim_{n \rightarrow \infty} \frac{S_n}{n^{4 / 3}} \]

\solution{
We use the integral method for bounding $S_n$. 
\[\int_0^n x^{\frac{1}{3}}dx \leq S_n \leq \int_1^{n+1}x^{\frac{1}{3}}dx.\]
That is,
\[\frac{(3/4)n^{4/3}}{n^{4/3}}  \leq \frac{S_n}{n^{4/3}} \leq   \frac{(3/4)((n+1)^{4/3} - 1)}{n^{4/3}}\]
Taking limits as $n \rightarrow \infty$ we find that
\[3/4 \leq {\displaystyle \lim_{n \rightarrow \infty}\frac{S_n}{n^{4/3} }} \leq 3/4\]

Therefore, ${\displaystyle \lim_{n\rightarrow\infty}\frac{S_n}{n^{4/3}}} = 3/4.$
}
%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000  Problem Set 6     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem {\bf (16 points)} Find closed-form expressions for the
following sums.

\begin{problemparts}

\iffalse

\problempart
\[
\sum_{i=0}^n \frac{9^n - 7^n}{11^n}
\]

\solution{Split the expression into two geometric series and then
apply the formula for the sum of a geometric series.

\begin{eqnarray*}
\sum_{i=0}^n \frac{9^i - 7^i}{11^i}
    & = &   \sum_{i=0}^n \left(\frac{9}{11}\right)^i -
        \sum_{i=0}^n \left(\frac{7}{11}\right)^i \\
    & = &   \frac{1 - \left(\frac{9}{11}\right)^{n+1}}{1 - \frac{9}{11}}
          - \frac{1 - \left(\frac{7}{11}\right)^{n+1}}{1 - \frac{7}{11}} \\
    & = &   - \frac{11}{2} \cdot \left(\frac{9}{11}\right)^{n+1}
        + \frac{11}{4} \cdot \left(\frac{7}{11}\right)^{n+1}
        + \frac{11}{4}
\end{eqnarray*}

}
\fi

\problempart
\[
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \sum_{k=0}^{\infty} 2^{-(i +2j +3k)}
\]

\solution{ 
 \textbf{Solution:}\\
Apply the formula for the sum of a geometric series three
times.

\begin{eqnarray*}
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \sum_{k=0}^{\infty} 2^{-(i +2j +3k)}
    & = &   \sum_{i=0}^{\infty} 2^{-i} \cdot
        \left(\sum_{j=0}^{\infty} 2^{-2j} \cdot
        \left(\sum_{k=0}^{\infty} 2^{-3k} \right) \right) \\
    & = &   \sum_{i=0}^{\infty} 2^{-i} \cdot
        \left(\sum_{j=0}^{\infty} 2^{-2j} \cdot
        \frac{8}{7} \right) \\
    & = &   \sum_{i=0}^{\infty} 2^{-i} \cdot
        \frac{4}{3} \cdot \frac{8}{7} \\
    & = &   \frac{2}{1} \cdot \frac{4}{3} \cdot \frac{8}{7} \\
    & = &   \frac{64}{21}
\end{eqnarray*}
}

\iffalse

\problempart
\[
\sum_{i=n+1}^{2n} i^2
\]

\solution{
This expression is the difference of two sums of squares, which can be
reduced to a closed form by a standard formula.

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

\problempart
\[
\prod_{i=1}^{n} 3^{4i + 5}
\]

\solution{This product can be reduced to an easy sum by taking a
logarithm.

\begin{eqnarray*}
\prod_{i=1}^{n} 3^{4i + 5}
    & = &   3^{\log_3\left( \prod_{i=1}^{n} 3^{4i + 5} \right)} \\
    & = &   3^{\sum_{i=1}^n 4i+5} \\
    & = &   3^{2n(n+1) + 5n}
\end{eqnarray*}
}
\fi

\problempart

\[
\sum_{j=1}^n \sum_{i=0}^{\infty} j^{2/3} \cdot \left(1 - \frac{1}{2 j^{1/3}}\right)^i
\]

\solution{
\textbf{Solution:}\\
This fearsome-looking sum is a paper tiger; we just apply
the formula for the sum of a geometric series followed by the formula
for the sum of an arithmetic series.

\begin{eqnarray*}
\sum_{j=1}^n \sum_{i=0}^{\infty} j^{2/3} \cdot \left(1 - \frac{1}{2 j^{1/3}}\right)^i
    & = &   \sum_{j=1}^n j^{2/3} \cdot \frac{1}{1 - \left(1 - \frac{1}{2 j^{1/3}}\right)} \\
    & = &   \sum_{j=1}^n 2j \\
    & = &   n (n+1)
\end{eqnarray*}
}
\iffalse

\problempart

\[
\prod_{i=2}^{n} \left(1 - \frac{1}{i^2}\right)
\]

\solution{ We give two solutions.  First, evaluating a few terms
suggests that the product is equal to

\[
\frac{n+1}{2n}.
\]

We could verify this by induction.  The calculation needed for the
inductive step is shown below.

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

As an alternative approach, we might observe that this is a
``telescoping product''.

\begin{eqnarray*}
\prod_{i=2}^{n} \left(1 - \frac{1}{i^2}\right)
    & = & \prod_{i=2}^{n} \frac{(i-1)(i+1)}{i^2} \\
    & = & \frac{1 \cdot 3}{2 \cdot 2}
        \cdot \frac{2 \cdot 4}{3 \cdot 3}
        \cdot \frac{3 \cdot 5}{4 \cdot 4} \cdots
        \frac{(n-1) \cdot (n+1)}{n \cdot n} \\
    & = &   \frac{1}{2} \cdot {n+1}{n}
\end{eqnarray*}
}
\fi

\end{problemparts}      

%%%%%%%%%%%%%%  Fall 2000   Problem Set 6    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem 
% problem 2, problem set 6, fall 1996

Find a closed-form expression for the summation
$\displaystyle\sum_{i=1}^n{i^2x^i}$.% and prove your answer is correct.

\solution{%
  %\begin{solution}
\textbf{Solution:}\\
    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}\]

    We prove that the above closed-form expression for the summation
    is correct by induction on the upper bound $n$ of the summation.
    In particular, let $P(n)$ be the predicate 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$.
  %\end{solution}
  }
                   
%%%%%%%%%%%%%%  Fall 2000  Problem Set 6     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem
% problem 3, problem set 6, fall 1996
% similar to CLR 3.2-1

Show that $\sum_{k=1}^{\infty}{1/k^{3/2}}$ is bounded above by a constant.

\solution{%
  %\begin{solution}
\textbf{Solution:}\\
    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$.
  %\end{solution}
}
                   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%END   George's problems


%BEGIN Tina's problems
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% fall 99 pset 6, #3
\problem \textbf{Summations}

Recall that $H_n$ is the $n\kth$ harmonic number, i.e., \[
H_n=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots+\frac{1}{n} \]

\bparts

\ppart Rosen \S 1.7 exercise 21 (Do not quote the answer from the back, and
instead explicitly show the steps involved in calculating that answer.)

\solution{
(i) \begin{eqnarray*}
\sum_{k=1}^n 2k-1 &=& \sum_{k=1}^n k^2-(k-1)^2\\ 
                  &=& n^2 - (n-1)^2 + (n-1)^2 - (n-2)^2+(n-2)^2 - (n-3)^2 \\ 
                   && + \cdots + 1^2 - 1^2 + 0^2 \\
                  &=& n^2
\end{eqnarray*}

(ii) $\sum_{k=1}^n 2k-1=-n + 2\sum_{k=1}^n k$.  This implies that
\begin{eqnarray*}
\sum_{k=1}^n k & = & \frac{1}{2}\left[n + \sum_{k=1}^n 2k-1\right]\\
               & = & \frac{1}{2}(n + n^2)\\
               & = & \frac{1}{2}n(1+n)
\end{eqnarray*}
\hfill$\Box$
}

\eparts

Find a closed form for each of the following:

\bparts

\ppart $\sum_{k=0}^{\infty} i^k/2^{k/4}$, where $i$ is $\sqrt{-1}$.

\solution{Note that we can separate this sum into several pieces:
\begin{center}
\begin{tabular}{rl}
(1) & $1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots +$ \\
(2) & $\frac{i}{2^{1/4}} + \frac{i}{2^{5/4}} + \frac{i}{2^{9/4}} +
\frac{i}{2^{13/4}} + \cdots +$ \\
(3) & $\frac{-1}{2^{2/4}} + \frac{-1}{2^{6/4}} + \frac{-1}{2^{10/4}} +
\frac{-1}{2^{14/4}} + \cdots +$ \\
(4) & $\frac{-i}{2^{3/4}} + \frac{-i}{2^{7/4}} + \frac{-i}{2^{11/4}} +
\frac{-i}{2^{15/4}} + \cdots$
\end{tabular}
\end{center}
You should recognize the first summation: it converges to 2.  The
second summation is therefore simply $\frac{i}{2^{1/4}}$ times the
first summation, leaving $2^{3/4}i$.  Similarly, the third and fourth
summations are $-\sqrt{2}$ and $-2^{1/4}i$, respectively.  The total is
then $(2 - \sqrt{2}) + i(2^{3/4}-2^{1/4})$, or
$(1+2^{-1/4}i)(2-\sqrt{2})$.\hfill$\Box$

}

\ppart $\sum_{k=1}^{\infty} 1/k(k+n)$ (Your
solution may involve the harmonic number function.)

\solution{Note by partial fractions that
\[ \frac{n}{k(k+n)}=\frac{1}{k}-\frac{1}{k+n} \]
Let $K>n$, then 
\[
\sum_{k=1}^K \left(\frac{1}{k}-\frac{1}{k+n}\right) = \sum_{k=1}^n
\frac{1}{k}-\sum_{k=K+1}^{K+n}\frac{1}{k}
\]
But 
\[
\sum_{k=K+1}^{K+n}\frac{1}{k}\le \frac{n}{K+1}
\] 
Therefore 
\[
\lim_{K\to\infty} \sum_{k=K+1}^{K+n}\frac{1}{k} = 0
\] 
Hence 
\[
\lim_{K\to\infty} \sum_{k=1}^K \left(\frac{1}{k}-\frac{1}{k+n}\right) = H_n
\]
i.e.
\[
\sum_{k=1}^{\infty} \frac{1}{k(k+n)} = \frac{H_n}{n}
\]
%\begin{eqnarray*}
%\sum_{k=1}^{\infty} \frac{1}{k(k+n)} &=& \frac{1}{n}\sum_{k=1}^{\infty}
%\left[\frac{1}{k}-\frac{1}{k+n}\right] \\
%&=& \frac{1}{n}\left[\sum_{k=1}^{\infty}\frac{1}{k} -
%\sum_{k=1}^{\infty}\frac{1}{k+n}\right] \\
%&=& \frac{1}{n}\left[\sum_{k=1}^{n}\frac{1}{k} +
%\sum_{k=n+1}^{\infty}\frac{1}{k} - 
%\sum_{k=1}^{\infty}\frac{1}{k+n}\right] \\
%&=& \frac{1}{n}\left[\sum_{k=1}^{n}\frac{1}{k} +
%\sum_{k=n+1}^{\infty}\frac{1}{k} - 
%\sum_{k=n+1}^{\infty}\frac{1}{k}\right] \\
%&=& \frac{1}{n}\sum_{k=1}^{n}\frac{1}{k} \\
%&=& \frac{H_n}{n}
%\end{eqnarray*}
%\hfill$\Box$
}

\ppart $\sum_{i=1}^\infty\sum_{j=1}^\infty ix^iy^{i+2j}$

\solution{\begin{eqnarray*}
\sum_{i=1}^\infty\sum_{j=1}^\infty ix^iy^{i+2j} & = &
\sum_{i=1}^\infty\left[i(xy)^i\left(\sum_{j=1}^\infty
y^{2j}\right)\right] \\
&=& \sum_{i=1}^\infty\left[i(xy)^i\left(\sum_{j=1}^\infty
(y^2)^j\right)\right] \\
&=&
\sum_{i=1}^\infty\left[i(xy)^i\left(\frac{y^2}{1-y^2}\right)\right] \\ 
&=&
\frac{y^2}{1-y^2}\sum_{i=1}^\infty\left[i(xy)^i\right] \\ 
&=&
\frac{y^2}{1-y^2}\cdot\frac{xy}{(1-xy)^2} \\ 
&=& \frac{xy^3}{(1-y^2)(1-xy)^2}
\end{eqnarray*}
}

\eparts

Find asymptotically tight bounds\footnote{We say that function $f$
provides an asymptotically tight bound for a function $g$ if $lim_{n \to
\infty} f(n)/g(n) = 1$.  That is, $f \sim g$ using the notation from
Lecture Notes 8, \S 2.4.} for the following:

\bparts
\ppart $\sum_{k=1}^{n} k^4$

\solution{\begin{eqnarray*}
\sum_{k=1}^{n+1} k^4 &\leq& \int_{1}^{n+2} x^4\ dx \\
&=&\frac{(n+2)^5-1}{5}\\
&\sim&\frac{n^5}{5}
\end{eqnarray*}
\begin{eqnarray*}
\sum_{k=1}^{n+1} k^4 &\geq& \int_{0}^{n+1} x^4\ dx \\
&=&\frac{(n+1)^5}{5}\\
&\sim&\frac{n^5}{5}
\end{eqnarray*}\hfill$\Box$}

\ppart $\sum_{k=1}^{n} e^{\sqrt{k}}/\sqrt{k}$

\solution{Note that with $u=\sqrt{x}$, $du=\frac{1}{2 \sqrt{x}}\ dx$.
So,
\begin{eqnarray*}
\sum_{k=1}^{n} \frac{e^{\sqrt{k}}}{\sqrt{k}} &\leq& \int_{1}^{n+1}
\frac{e^{\sqrt{x}}}{\sqrt{x}}\ dx \\
&=& 2(e^{\sqrt{n+1}}-e)\\
&\sim& 2 e^{\sqrt{n}}
%\\
%&\leq& e^{\sqrt{n}+1}-e \\
%&=& e\cdot e^{\sqrt{n}}-e \\
%&\sim& e^{\sqrt{n}}
\end{eqnarray*}
To see why the last line holds, notice that
$\sqrt{n+1}-\sqrt{n}=\frac{1}{\sqrt{n+1}+\sqrt{n}}$,
so $\sqrt{n+1}-\sqrt{n}\to 0$ as $n\to\infty$. Thus
$\lim_{n\to\infty} \frac{e^{\sqrt{n+1}}}{e^{\sqrt{n}}} = 1$.\\
Finally, 
\begin{eqnarray*}
\sum_{k=1}^{n} \frac{e^{\sqrt{k}}}{\sqrt{k}} &\geq& \int_{0}^{n}
\frac{e^{\sqrt{x}}}{\sqrt{x}}\ dx \\
&=& 2 e^{\sqrt{n}}-2\\
&\sim& 2 e^{\sqrt{n}}.
\end{eqnarray*}\hfill$\Box$}

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%END   Tina's problems

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%BEGIN   Jaime's Problem 1
%SOURCE  Fall 2001 Tutorial 7, problem 1

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

%END     Jaime's Problem 1

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%BEGIN   Jaime's Problem 2
%SOURCE  Fall 2001 Tutorial 7, problem 2


\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} \labe
l{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 \g
e 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.
}

%END     Jaime's Problem 2

\end{problems}

\end{ducument}
