% Topics:
%  x arithmetic and geometric sums
%  o taylor series (oh well...)
%  x integration bounds
%  xx harmonic sums
%  x recurrences, esp. formulation

\documentclass[twoside,12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\begin{document}

\problemset{6}{March 15, 2005}{Monday, March 28 at 9 PM in Room 32-044}

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

\begin{problem}
Sammy the Shark is a financial service provider who offers loans on
the following terms.

\begin{itemize}

\item Sammy loans a client $m$ dollars in the morning.  This puts the
client $m$ dollars in debt to Sammy.

\item Each evening, Sammy first charges a ``service fee'', which
increases the client's debt by $f$ dollars, and then Sammy charges
interest, which multiplies the debt by a factor of $p$.  For example,
if Sammy's interest rate were a modest 5\% per day, then $p$ would be
$1.05$.

\end{itemize}

\bparts

\ppart What is the client's debt at the end of the first day?

\solution{At the end of the first day, the client owes
  Sammy $(m + f) p = m p + f p$ dollars.}

\ppart What is the client's debt at the end of the second day?

\solution{$((m + f) p + f) p = m p^2 + f p^2 + f p$}

\ppart Write a formula for the client's debt after $d$ days and find
an equivalent closed form.

\solution{
The client's debt after three days is
%
\[
(((m + f) p + f) p + f) p  =  m p^3 + f p^3 + f p^2 + f p.
\]
%
Generalizing from this pattern, the client owes
%
\[
m p^d + \sum_{k=1}^d fp^k
\]
%
dollars after $d$ days.  Applying the formula for a geometric sum gives:
%
\[
m p^d + f \cdot \paren{\frac{p^{d+1} - 1}{p - 1} - 1}
\]
}

\eparts

\end{problem}

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

\begin{problem}
Find closed-form expressions equal to the following sums.  Show your work.

\bparts

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

\solution{Split the expression into two geometric series and then
apply the formula for the sum of a geometric series.
%
\begin{align*}
\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{align*}}

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

\solution{
Taking the logarithm reduces this product to an easy sum.
%
\begin{align*}
\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{align*}
}

\ppart
\[
\sum_{j=1}^n \sum_{i=0}^{\infty} j^{5/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{align*}
\sum_{j=1}^n \sum_{i=0}^{\infty} j^{5/3} \cdot \left(1 - \frac{1}{2 j^{1/3}}\right)^i
    & = \sum_{j=1}^n j^{5/3} \cdot \frac{1}{1 - \left(1 - \frac{1}{2 j^{1/3}}\right)} \\
    & = \sum_{j=1}^n 2j^2 \\
    & = \frac{2n (n+\frac{1}{2})(n+1)}{3}
\end{align*}
}

\eparts

\end{problem}

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

\iffalse
\begin{problem}
The 6.042 course staff considered competing against a team of students
in the box-stacking game.  Naturally, this prompted us to search for
the best way to cheat.  Our best idea was to secretly weight all of
our boxes, moving the center of mass nearer to one end as shown below:
%
\begin{center}
\includegraphics[height=1.5in]{pset8-box.eps}
\end{center}
%
Of course, the students would be given ordinary, unweighted boxes.  If
both teams built optimal structures, how much farther would the
staff's stack extend?  Assume that each team has $n$ boxes.
\end{problem}

\solution{As in the original analysis, define the ``offset'' of a
stack of blocks to be the horizontal distance from the center of mass
to the rightmost edge.  Let $X_n$ be the maximum possible offset for a
stack of $n$ blocks.  For a single block, the offset is $X_1 = 1 -
1/r$ as indicated in the diagram.

This is also the maximum possible overhang,
since we can place the center of mass directly over the edge of the
table.  As before, regard a stack of $n$ blocks as a stack of $n-1$
blocks atop a single block.  At best, the center of mass of the top
$n-1$ blocks is directly above the rightmost edge of the bottom block.
Now the center-of-mass formula gives:
%
\begin{align*}
X_n & = \frac{X_{n-1} \cdot (n-1) + (X_{n-1} + 1 - 1/r) \cdot 1}{n} \\
    & = X_{n-1} + (1-1/r) \cdot \frac{1}{n}
\end{align*}
%
Expanding the recurrence equation, we find:
%
\begin{align*}
X_n
  & = (1-1/r) \cdot \paren{\frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{n}} \\
  & = (1-1/r) H_n
\end{align*}
%
This implies that the course staff's stack would extend $(1-1/r) \cdot
H_n$ block-lengths past the edge of the table, which is nearly twice
as far as the student stack when $r$ is large.}
\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?

\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}
Use integration to find lower and upper bounds on the following
infinite sum that differ by at most $0.1$.  Show your work.
%
\[
S = \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \frac{1}{4^2} + \ldots
\]
%
To achieve this accuracy, add up the first few terms explicitly and
then use integration to bound all remaining terms.
\end{problem}

\solution{
The sum of the first three terms is:
%
\[
s = \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} = \frac{49}{36}
\]
%
An upper bound on the remaining terms is:
%
\[
\int_3^\infty \frac{1}{x^2}\ dx = \frac{1}{3}
\]
%
And a lower bound is:
%
\[
\int_3^\infty \frac{1}{(x+1)^2}\ dx = \frac{1}{4}
\]
%
Overall, we have:
%
\[
\frac{58}{36} \leq \frac{49}{36} + \frac{1}{4} \leq S \leq \frac{49}{36} + \frac{1}{3} = \frac{61}{36}
\]
%
These bounds differ by $1/12 < 0.1$.  The actual value of the sum is
$\pi^2 / 6$, though the proof is not easy.}

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


\begin{problem}
A seasoned MIT undergraduate can:

\begin{itemize}
\item Complete a problem set in 2 days.
\item Write a paper in 2 days.
\item Take a 2-day road trip.
\item Study for an exam in 1 day.
\item Play foosball for an entire day.
\end{itemize}

An \textit{$n$-day schedule} is a sequence of activities that require a
total of $n$ days.  For example, here are three possible 7-day schedules:

\begin{center}
\begin{tabular}{l}
pset, paper, pset, foosball \\
paper, study, foosball, pset, study \\
road trip, road trip, road trip, study
\end{tabular}
\end{center}

\bparts

\ppart Express the number of possible $n$-day schedules using a
recurrence equation and sufficient base cases.

\solution{
\begin{align*}
S(0) & = 1,\\
S(1) & = 2.
\end{align*}
Any schedule for $n>1$ days ends with one of 3 possible 2-day activities
or one of 2 possible 1-day activities.  So
\begin{align*}
S(n) & = 2S(n-1) + 3S(n-2) & \text{for $n>1$.}
\end{align*}
}

\ppart Find a closed-form expression for the number of possible
$n$-day schedules by solving the recurrence.

\solution{The characteristic polynomial for this linear homogeneous
recurrence is $x^2-2x-3 = (x+1)(x-3)$.  Hence the solution is of the
form $S(n) = a(-1)^n + b3^n$.  Letting $n=0$, we conclude that $a+b =
1$, and letting $n=1$, we conclude $-a+3b =2$, so $b=3/4$, $a=1/4$,
and the solution is:
%
\[
S(n) = \frac{3^{n+1} + (-1)^{n}}{4}.
\]
}

\eparts

\end{problem}

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

\begin{problem} Find a closed-form expression for $T(n)$, which
is defined by the following recurrence:
%
\begin{align*}
T(0) & = 0 \\
T(1) & = 1 \\
T(n) & = 5 T(n-1) - 6 T(n-2) + 6 \qquad \text{for all } n \geq 2
\end{align*}
\end{problem}

\solution{The characteristic equation is $x^2 - 5 x + 6 = 0$, which has roots $x = 2$ and $x = 3$.  Thus, the homogenous solution is:
%
\[
T(n) = A \cdot 2^n + B \cdot 3^n
\]
%
For a particular solution, let's first guess $T(n) = c$:
%
\begin{align*}
c & = 5 c - 6 c + 6 \\
\implies c & = 3
\end{align*}
%
Our guess was correct; $T(n) = 3$ is a particular solution.  Adding
this to the homogenous solution gives the general solution:
%
\[
T(n) = A \cdot 2^n + B \cdot 3^n + 3
\]
%
Substituting $n = 0$ and $n = 1$ gives:
%
\begin{align*}
0 & = A + B + 3 \\
1 & = 2 A + 3 B + 3
\end{align*}
%
Solving this system gives $A = -7$ and $B = 4$.  Therefore:
%
\[
T(n) = -7 \cdot 2^n + 4 \cdot 3^n + 3
\]
}

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

\begin{problem}
Determine which of these choices
\[
\Theta(n), \quad
\Theta(n^2 \log n), \quad
\Theta(n^2), \quad
\Theta(1), \quad
\Theta(2^n), \quad
\Theta(2^{n \ln n}), \quad
\text{none of these}
\]
describes each function's asymptotic behavior.  Proofs are not
required, but briefly explain your answers.

\bparts
\ppart
\[
n + \ln n + (\ln n)^2
\]

\solution{Both $n > \ln n$ and $n > (\ln n)^2$ hold for all
sufficiently large $n$.  Thus, for all sufficiently large $n$:
\[
n < n + \ln n + (\ln n)^2 < n + n + n
\]
So $n + \ln n + (\ln n)^2 = \Theta(n)$.
}

\ppart
\[
\frac{n^2 + 2n - 3}{n^2 - 7}
\]

\solution{
Observe that:
\[
\lim_{n \to \infty} \frac{n^2 + 2n - 3}{n^2 - 7} = 1
\]
This means, that for all sufficiently large $n$, the fraction lies, for
example, between, $0.99$ and $1.01$ and is therefore $\Theta(1)$.}

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

\solution{Geometric sums are dominated by their largest term, which is
$2^{2n+1} = 2 \cdot 4^n$.  This is $\Theta(4^n)$, which does not
appear in the list provided.}

\ppart
\[
\ln (n^2!)
\]

\solution{
By Stirling's formula:
\[
n^2! \sim \sqrt{2 \pi n^2} \left(\frac{n^2}{e}\right)^{n^2}
\]
Taking logarithms gives:
%
\begin{align*}
\ln(n^2!)
    & \sim \ln(\sqrt{2 \pi n^2} \left(\frac{n^2}{e}\right)^{n^2}) \\
    & = \ln(\sqrt{2 \pi n^2}) + \ln\left(\frac{n^2}{e}\right)^{n^2}
\end{align*}
%
The first term is tiny compared to the second, which we can rewrite as:
%
\[
\ln\left(\frac{n^2}{e}\right)^{n^2}
     = n^2 \ln\left(\frac{n^2}{e}\right) = \Theta(n^2 \ln n)
\]
}

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

\solution{The expression in parentheses is always at least $1/2$ and
at most $1$.  Thus, we have the bounds:
%
\[
\frac{1}{2} \sum_{k=1}^{n} k
\leq
\sum_{k=1}^{n} k \left(1 - \frac{1}{2^k}\right)
\leq
\sum_{k=1}^{n} k
\]
%
Since the first expression and the last are both $\Theta(n^2)$, so is
the one in the middle.}

\eparts

\end{problem}

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

\begin{problem}
A \textit{triangular number} is an integer $n$ of the form
%
\[
n = 1 + 2 + 3 + \ldots + k = \frac{k (k+1)}{2}
\]
%
where $k$ is a positive integer.

\bparts

\ppart Describe a solution to the four-peg Towers of Hanoi puzzle with
$k(k+1)/2$ disks that requires $T_k$ moves, where:
%
\begin{align*}
T_1 & = 1 \\
T_k & = 2 T_{k-1} + 2^k - 1
\end{align*}

\ppart Find a closed form expression equal to $T_k$.

\solution{This is an inhomogenous linear equation.  Let's begin by
trying to find a particular solution.  There is both an exponential
term ($2^k$) and a constant term, so we might guess something of the
form $a 2^k + c$:
%
\begin{align*}
a 2^k + c & = 2 (a 2^{k-1} + c) + 2^k - 1 \\
          & = (a + 1) 2^k + 2 c - 1 \\
\implies 0 & = 2^k + (c - 1)
\end{align*}
%
Evidently, the constant term is $c = 1$, but the exponential part is
more complicated.  Our recipe says we should next try a particular
solution of the form $a 2^k + b k 2^k + 1$:
%
\begin{align*}
a 2^k + b k 2^k + 1
    & = 2 (a 2^{k-1} + b(k-1) 2^{k-1} + 1) + 2^k - 1 \\
    & = (a - b + 1) 2^k + b k 2^k - 1
\end{align*}
%
Equating the coefficients of the $2^k$ terms gives $a = a - b + 1$,
which implies $b = 1$.  Thus, $a 2^k + k 2^k + 1$ is a particular
solution for all $a$.  As long as we have this degree of freedom, we
might as well choose $a$ so this solution is consistent with the
boundary condition $T_1 = 1$ and be done:
%
\[
a 2^1 + 1 \cdot 2^1 + 1 = 1 \quad \implies \quad a = -1
\]
%
Therefore, the solution to the recurrence is $T_k = (k - 1)2^k + 1$.}

\ppart Approximately how many moves are required to solve the
four-peg, $n$-disk Towers of Hanoi puzzle as a function of $n$?
Assume $n$ is a triangular number.  (For style points, make correct
use of asymptotic notation.)

\solution{We have $k = \frac{1}{2}(\sqrt{8n+1}-1) = \sqrt{2n} +
O(1)$.  So the number of moves required is
$\Theta(\sqrt{n}2^{\sqrt{2n}})$.}

\eparts

\end{problem}

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

\end{document}
