\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

\begin{document} 
\inclassproblems{8, Fri.}


\iffalse
\begin{problem}
Regrouping or reordering the terms of an infinite series is ok for
\emph{absolutely convergent} series, namely, series for which the sum of
the absolute values of their terms converges.  In other cases, rearranging
terms is not ok.  \iffalse An extreme example is
\[
S \eqdef \sum_{i=0}^{\infty} (-1)^i = 1 + (-1) + 1 + (-1) + \cdots
\]
because by regrouping the terms we can deduce:
\begin{eqnarray*}
S & = & [ 1 + (-1) ] + [ 1 + (-1) ] + \cdots = 0 + 0 + \cdots = 0,\\
S & = & 1 + [(-1) + 1] + [(-1) + 1] + \cdots = 1 + 0 + 0 + \cdots = 1.
\end{eqnarray*}

To see the problem here, let $S_n \eqdef \sum_{i=0}^{n}(-1)^i$.  Then $S_n
= 1$ for odd $n$ and $S_n = 0$ for even $n$.  Hence $S_n$ does not have a
well-defined limit as $n$ tends to infinity, implying that $S$ is not a
convergent series.

Even for convergent, but not absolutely convergent, series, rearranging
terms can cause big changes.\fi
For example, consider the series
\begin{equation}\label{1n}
1 - 1/2 + 1/3 - 1/4 \dots
\end{equation}
which converges, but is not absolutely convergent.

Let $r$ be any real number.  Explain how to reorder terms in~(\ref{1n}), so
that the resulting series converges to $r$.

\solution{

Note that the sum of the negative terms goes to negative infinity, because
the sum
\[
-1/2 - 1/4 - 1/6 -  \dots - 1/2n = -H_n/2 \sim (-\ln n)/ 2
\]
and $\ln n$ goes to infinity with $n$.  Similarly, the sum of the positive
terms goes to positive infinity.

To reorder the terms to converge to $r$, begin by taking the positive terms
in decreasing order until their sum first exceeds $r$.  Next, take the
negative terms in order of decreasing magnitude until the sum of all the
terms taken---positive and negative---first goes below $r$.  Now take the
remaining positive terms in decreasing order until the sum again exceeds $r$,
then the negative terms till the sum goes below $r$, and so on.  It is always
possible to move the sum above or below $r$ by taking enough of the remaining
positive or negative terms, because the remaining positive terms sum to
positive infinity and the remaining negative terms sum to negative
infinity.  Also, the running sum of the positive and negative terms taken
in this way goes above and below $r$ at most by the magnitude of the last
term taken.  Since the magnitude of the terms goes to zero, this implies
that the sum goes above and below $r$ by an amount that decreases to zero.
But this is exactly what it means to say the sum converges to $r$.


This argument applies to \emph{any} convergent series that is not
absolutely convergent to show that it can be reordered to converge to
\emph{any} desired number, or to diverge.  The moral: when reordering terms
in a series, be sure to check for absolute convergence.
}

\end{problem}
\fi

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

\begin{problem}
There is a bug on the edge of a 1-meter rug.  The bug wants to cross
to the other side of the rug.  It crawls at 1 cm per second.  However,
at the end of each second, a malicious first-grader named Mildred
Anderson \textit{stretches} the rug by 1 meter.  Assume that her
action is instantaneous and the rug stretches uniformly.  Thus, here's
what happens in the first few seconds:

\begin{itemize}

\item The bug walks 1 cm in the first second, so 99 cm remain ahead.

\item Mildred stretches the rug by 1 meter, which doubles its length.
So now there are 2 cm behind the bug and 198 cm ahead.

\item The bug walks another 1 cm in the next second, leaving 3 cm
behind and 197 cm ahead.

\item Then Mildred strikes, stretching the rug from 2 meters to 3
meters.  So there are now $3 \cdot (3 / 2) = 4.5$ cm behind the bug
and $197 \cdot (3/2) = 295.5$ cm ahead.

\item The bug walks another 1 cm in the third second, and so on.

\end{itemize}

Your job is to determine this poor bug's fate.

\bparts

\item During second $i$, what \textit{fraction} of the rug does the
bug cross? 

\solution{During second $i$, the length of the rug is $100i$ cm and
the bug crosses 1 cm.  Therefore, the fraction that the bug crosses is
$1 / 100i$.}

\item Over the first $n$ seconds, what fraction of the rug does the
bug cross altogether?  Express your answer in terms of the Harmonic
number $H_n$.

\solution{The bug crosses $1/100$ of the rug in the first second,
$1/200$ in the second, $1/300$ in the third, and so forth.  Thus, over
the first $n$ seconds, the fraction crossed by the bug is:
%
\[
\sum_{k=1}^{n} \frac{1}{100k} = H_n / 100
\]
%
(This formula is valid only until the bug reaches the far side of the
rug.)}

\item Approximately how many seconds does the bug need to cross the
entire rug?

\solution{The bug arrives at the far side when the fraction it has
crossed reaches 1.  This occurs when $n$, the number of seconds
elapsed, is sufficiently large that $H_n / 100 \geq 1$.  Now $H_n$ is
approximately $\ln n$, so the bug arrives about when:
%
\begin{align*}
\frac{\ln n}{100} & \geq 1 \\
\ln n & \geq 100 \\
n & \geq e^{100} \approx 10^{43} \text{ seconds}
\end{align*}
}

\eparts

\end{problem}

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

\begin{problem}
Using the method described in lecture, a truck can travel across any size
desert if there is a large enough supply of gas at the border of the
desert.  Show that if there is a large enough supply of gas at the border,
a truck can also make a \emph{round trip} across any size desert.

\solution{
Given that it can make a one-way trip across any desert, it can make a
two-way trip by executing the one-way strategy for twice the desert width,
but turning around when it gets to the desert edge instead of continuing.

A considerably more efficient approach uses ideas similar to the one-way
crossing strategy: let $R_n$ be the distance a truck can travel into the
desert \emph{and return} on $n$ tanks of gas.  Clearly, $R_1 = 1/2$.

On $n+1$ tanks, the strategy is to have truck travel distance $x$ and back
$n$ times, leaving $1-2x$ tanks of gas at distance $x$ into the desert on
each trip.  It then makes one more one-way trip to $x$.  This leaves it
with $n(1-2x) + 1-x$ tanks of gas at position $x$.  Leaving an $x$th of a
tank so it can get back, if the remaining $(n(1-2x) + 1-x) -x =
(n+1)(1-2x)$ tanks equal $n$, it can execute the $n$-tank round trip
strategy from position $x$ and still return to the desert border.  So, letting
\begin{eqnarray}
(n+1)(1-2x) & = & n\\
x & = & 1/2(n+1)\\
R_{n+1} & = & R_n + x = R_n + 1/2(n+1).
\end{eqnarray}
Therefore,
\[
R_n = 1/2 (1 + 1/2 + 1/3 + \cdots + 1/n) = H_{n}/2.
\]
}
\end{problem}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}
There is a number $a$ such that $\sum_{i=1}^\infty i^p$ converges iff $p <
a$.  What is the value of $a$?  Prove it.

\solution{$a= -1$.

For $p=-1$, the sum is the harmonic series which we know does not
converge.  Since the term $i^p$ is increasing in $p$ for $i>1$, the sum
will be larger, and hence also diverge for $p>-1$.

By the integral method, the sum is $\Theta$ of the integral from
1 to $\infty$ of $x^p$.  For $p<-1$, the indefinite integral is $x^{p+1}/(p+1) =
\Theta(1/x^\epsilon)$ for $\epsilon = -1 - p > 0$, so the integral
evaluates to a constant.  Hence the sum is bounded above, and since it is
increasing, it has a finite limit, \ie it converges.}

\end{problem}


\end{document}
