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

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

\problem {\bf (10 points)} A banker loans \$100,000 to the Addams
family so that they can purchase a new dilapidated mansion.  At the
end of each year for the next 20 years, Morticia Addams will drop by
the bank to make a payment on the loan.  The banker will immediately
invest this returned money at a 7\% annual rate of return.

What annual payment should the banker require of the Addams family so
that his return after 20 years is the same as if he had invested the
whole amount at 7\% today instead of making the loan?

\solution{

Suppose that Morticia pays $p$ dollars at the end of each year for 20
years.  The banker can invest the first payment for 19 years, the
second payment for 18 years, etc.  Therefore, after 20 years his total
cash is:

\begin{eqnarray*}
\sum_{i=0}^{19} p \cdot 1.07^i
	& = &	p \cdot \sum_{i=0}^{19} 1.07^i \\
	& = &	p \cdot \frac{1.07^{20} - 1}{1.07 - 1}
\end{eqnarray*}

The second equation uses the formula for the sum of a finite
geometric series.

On the other hand, if the banker invests the money at 7\% today, then
after 20 years his total cash is $100,000 \cdot 1.07^{20}$.

Equating these two expressions and solving for $p$, Morticia's annual
payment, we find:

\begin{eqnarray*}
p \cdot \frac{1.07^{20} - 1}{1.07 - 1}
	& = & 100,000 \cdot 1.07^{20} \\
p	& = &	100,000 \cdot 1.07^{20} \cdot
		\frac{1.07 - 1}{1.07^{20} - 1} \\
	& \approx & \$9439.29
\end{eqnarray*}
}

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

%**************
%   PSET 5    *
%**************
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (15 points)}  In 1997 there was a breakthrough on a
long-standing problem in computer science called The Traveling
Salesman Problem.  The idea is that there is a salesman who wants to
visit $n$ cities scattered around the country.  The problem is to
determine the order in which he should visit the cities so as to
minimize the total distance that he travels, assuming that he can go
in a straight line between any two cities.  Surprisingly, this problem
is very difficult when the number of cities $n$ is large.

The breakthrough was an algorithm that efficiently computes a
nearly-optimal solution, a route for the salesman that has length at
most 10\% greater than the shortest possible route.  The running time
of the algorithm is described in the orginal publication as ``nearly
linear'' in the number of cities.  More precisely, the algorithm
requires about $n
\ln^{400} n$ steps.

\begin{problemparts}

\problempart Prove that $n \ln^{400} n$ is $o(n^{1.1})$.  This shows that
the algorithm truly is ``nearly linear'' in an asymptotic sense.  You
may make use of L'Hopital's rule:

\[
	\text{If} \  
\lim_{n\rightarrow\infty} f(n) = \infty
	\ \text{and} \ 
\lim_{n\rightarrow\infty} g(n) = \infty,
	\ \text{then} \  
\lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} =
	\lim_{n\rightarrow\infty} \frac{f'(n)}{g'(n)}.
\]

\solution{
\begin{proof}
We will first use L'Hopital's Rule to prove that the ratio of the two
running times tends to zero.

\begin{eqnarray*}
\lim_{n\rightarrow\infty} \frac{n \ln^{400} n}{n^{1.1}}
	& = & \lim_{n\rightarrow\infty} \frac{\ln^{400} n}{n^{0.1}} \\
	& = & \left( \lim_{n\rightarrow\infty} \frac{\ln n}{n^{1/4000}}
		\right)^{400} \\
	& = & \left( \lim_{n\rightarrow\infty} \frac{1/n}
		{\frac{1}{4000}n^{-3999/4000}}\right)^{400} \\
	& = & \left( \lim_{n\rightarrow\infty} \frac{4000}
		{n^{1/4000}}\right)^{400} \\
	& = & 0^{400} \\
	& = & 0
\end{eqnarray*}

The first step is simplification.  The second step uses the fact that
the limit of a product is the product of the limits.  L'Hopital's rule
is applied in the third step, and the remaining steps are
simplifications.

The definition of a limit implies that for all $c > 0$, there exists
an $n_0$ such that $n \ln^{400} n / n^{1.1} < c$ for all $n \geq
n_0$.  Rewriting this inequality as $n \ln^{400} n < c n^{1.1}$, we
establish that $n \ln^{400} n = o(n^{1.1})$ by the definition of $o$.
\end{proof}
}

\problempart Find a specific value of $n$ such that $n^{1.1}$ is actually
greater than $n \ln^{400} n$.

\solution{ We forgot to rule out small values of $n$.  Thus, for
example, $n = 1$ is an acceptable answer worth full credit.  However,
you are a SUPERIOR HUMAN BEING if you followed the intent of the
question and identified an $n$ such that the inequality holds for that
value and for all larger values.

Suppose that we choose $n = e^{50000}$, a number with more than
twenty-one thousand digits.  Then $n^{1.1}$ is equal to $e^{55000}$,
and $n \ln^{400} n$ is equal to $e^{50000} \cdot 50000^{400} =
e^{50000 + 400 \ln 50000} \approx e^{54328}$, which is a little
smaller.

Note that setting $n$ equal to $e^{40000}$--- a paltry seventeen
thousand digit number--- would not suffice.  Asymptotic notation can
be misleading!  }

\end{problemparts}

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

\problem {\bf (10 points)}  Order the functions in each set below so that
each function is either $O$ or $\Theta$ of the next function.
Indicate whether the stronger $\Theta$ relationship holds in each
case.  No proofs are required.

{\bf Example. \quad} $n^2$, $n$, $n^3 / (n + 1)$, $3n^2$
\begin{eqnarray*}
n	& = &	O(n^2) \\
n^2 	& = &	\Theta(3n^2) \\
3n^2	& = &	\Theta(n^3 / (n+1))
\end{eqnarray*}

\begin{problemparts}
\problempart $\ln n, \ln \sqrt{n}, \sqrt{\ln n}, n^{1/n}$

\solution{
\begin{eqnarray*}
n^{1/n}		& = &	O(\sqrt{\ln n}) \\
\sqrt{\ln n}	& = &	O(\ln \sqrt{n}) \\
\ln \sqrt{n}	& = &	\Theta(\ln n)
\end{eqnarray*}
}

\problempart $(\sqrt{n})^{2 \ln \ln n}, n, n \ln n, \ln n^{\ln n},
\ln n!$

\solution{ The notation $\ln n^{\ln n}$ was ambiguous, and so two
solutions are acceptable.

\begin{eqnarray*}
n		& = &	O(n \ln n) \\
n \ln n	& = &	\Theta(\ln n!) \\
\ln n!		& = &	O((\ln n)^{\ln n}) \\
(\ln n)^{\ln n}	& = &	\Theta((\sqrt{n})^{2 \ln \ln n})
\end{eqnarray*}

Alternatively,

\begin{eqnarray*}
\ln(n^{\ln n})	& = &	O(n) \\
n		& = &	O(n \ln n) \\
n \ln n		& = &	\Theta(\ln n!) \\
\ln n!		& = &	O((\sqrt{n})^{2 \ln \ln n})
\end{eqnarray*}
}

\problempart $n!, n^n, (n/3)^n, n^{n + \ln \ln n}, e^{n \ln \ln n}$

\solution{
\begin{eqnarray*}
e^{n \ln \ln n}	& = &	O((n/3)^n) \\
(n/3)^n			& = &	O(n!) \\
n!			& = &	O(n^n) \\
n^n			& = &	O(n^{n + \ln \ln n})
\end{eqnarray*}

The hardest relation here was probably $(n/3)^n = O(n!)$.  The
integral method gives the following.

\begin{eqnarray*}
\ln n!	& \geq & 	\int_1^n \ln u \ du \\
	& = &		n \ln n - n + 1 \\
n!	& \geq &	e^{n \ln n - n + 1} \\
	& \geq &	\left(\frac{n}{e}\right)^n
\end{eqnarray*}

The ratio $(n/3)^n$ divided by $(n/e)^n$ is equal to $(e/3)^n$, which
tends to 0 as $n$ goes to infinity.  This implies an $O$-relationship
rather than a $\Theta$-relationship.  }

\end{problemparts}

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

\problem {\bf (20 points)} Recently, Theory Pig found a small piece of
blue crayon behind the filing cabinet in Professor Lynch's office.
Theory Pig was delighted to find that with this wondrous new toy he
could draw pretty blue rectangles with a width of $w$ centimeters and
a height of $\ln w$ centimeters for any $w > 1$ that he took a fancy
to.

\centerline{
\begin{picture}(250,200)
\put(0,50){\framebox(200,100)}
\put(95,160){$w$}
\put(210,100){$\ln w$}
\end{picture}
}

Our pal proudly presented this remarkable discovery to 6.042 TA
Rodrigo Leroux.  Rodrigo was unimpressed: ``Yeah, but what if I want a
rectangle with an area of $n$ square centimeters?  Then what should be
the width $w$?''  Fidgeting nervously with his crayon, Theory Pig
replied that he believed the width should be $\Theta(n / \ln n)$
asymptotically, but that unfortunately he could not rigorously prove
this fact.  Rodrigo replied, ``If you can't play with your toys
properly, then they'll be taken away!''  And then he confiscated
Theory Pig's crayon!

Return joy to our little pal's world by supplying a proof of his
claim.

\solution{
Let $f(w) = w \ln w$.  Then a rectangle with width $w$ has area
$f(w)$.  Consequently, a rectangle with area $n$ should have width
$f^{-1}(n)$.  We can now formalize the problem as follows.

\bigskip
{\bf Claim. \quad} If $f(w) = w \ln w$, then $f^{-1}(n) = \Theta(n /
\ln n)$.
\bigskip

\begin{proof}
We must prove that there exists an $n_0$ and constants $c_1, c_2 > 0$
such that for all $n > n_0$

\[
c_1 \cdot \frac{n}{\ln n} \geq f^{-1}(n) \geq c_2 \cdot \frac{n}{\ln n}.
\]

Since $f$ is an increasing function, the above inequalities hold if
and only if

\begin{eqnarray*}
f\left(c_1 \cdot \frac{n}{\ln n}\right) \geq
	f(f^{-1}(n)) \geq
	f\left(c_2 \cdot \frac{n}{\ln n}\right).
\end{eqnarray*}

Suppose that we choose $c_1 = e$ and $c_2 = 1$.  Then the inqualities
can be rewritten as follows:

\begin{eqnarray*}
e \cdot \frac{n}{\ln n} \cdot \ln\left(
		e \cdot \frac{n}{\ln n} \right) \geq
	n \geq
	\frac{n}{\ln n} \cdot \ln\left( \frac{n}{\ln n} \right) \\ \\
n \cdot \left(e + \frac{e}{\ln n} - \frac{e \ln \ln n}{\ln n}\right) \geq
	n \geq
	n \cdot \left(1 - \frac{\ln \ln n}{\ln n}\right)
\end{eqnarray*}

In the expression on the left, the $e \ln \ln n / \ln n$ term is
$o(1)$, and so the expression in parentheses is greater than 1 for all
sufficiently large $n$.  In the expression on the right, the $\ln
\ln n / \ln n$ term is positive for all $n > e$, and so the expression is
parentheses is less than 1 for all sufficiently large $n$.  Therefore,
there exists an $n_0$ such that both inequalities hold for all $n >
n_0$ as desired.
\end{proof}
}

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

%END   Kavita's problems

%BEGIN Joe's problems
%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

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


\problem {\bf (10 points)} Use the integral method to find a $\Theta$
bound on the following sum.

\[
\sum_{i=1}^n i \ln i
\]

\solution{
We can bound the sum with two integrals.

\[
\int_1^n i \ln i \ di \ \leq \ 
	\sum_{i=1}^n i \ln i \ \leq \  
	\int_1^n (i+1) \ln(i+1) \ di
\]

Integration by parts gives the indefinite integral

\begin{eqnarray*}
\int i \ln i \ di
	& = &	\frac{1}{2} i^2 \ln i - \frac{1}{4} i^2 + C
\end{eqnarray*}

Substituting the appropriate integration ranges gives the bound
$\Theta(n^2 \ln n)$.}



%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems

\end{problems}

\end{ducument}


