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

%  The solutions still need some work!

%\hidesolutions
\showsolutions

\begin{document}

\problemset{6}{October 12, 2004}{\textit{Monday October 18 at 9 PM}}

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

\begin{problem} 
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{align*}
\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{align*}
%
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{align*}
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{align*}

We can also arrive at this answer by considering the present value of the
future payments: the value \emph{today} (the \emph{present value}) of a
contract for $p$ dollars to be paid $n$ years from now is $p/(1.07)^n$.
So the present value of payments of $\$p$ for the next 20 years is
\begin{align*}
\sum_{n=1}^{20} p/(1.07)^n
    & = \frac{p}{1.07}\sum_{n=0}^{19} (1/1.07)^n\\
    & = \frac{p}{1.07}\left(\frac{1-(1/1.07)^{20}}{1-(1/1.07)}\right)\\
    & = 10.594p
\end{align*}
We want to choose $p$ so this value equals 100,000; that is
\[
p = \frac{100000}{10.594} = 9439.29.
\]
 }
\end{problem}

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

\begin{problem}
Find closed-form expressions for 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

\[
\sum_{i=0}^n i^2 x^i
\]

\solution{This follows by differentiating the summation formula for
geometric series twice, and multiplying by $x$ after each
differentiation.  The first differentiation and multiplication by $x$
yields the equation
\[
\sum_{i=0}^{n} i x^i = \frac{x - (n+1)x^{n+1} + n x^{n+2}}{(1 - x)^2}
\]
as in the first set of Notes on Sums.  So
\begin{align*}
\frac{d}{dx}\ \sum_{i=0}^n i x^i
    & = \frac{d}{dx}\ \frac{x - (n+1)x^{n+1} + n x^{n+2}}{(1 - x)^2}\\
\sum_{i=0}^n i^2 x^{i-1}
    & = \frac{1+x-(n+1)^2x^{n}+(2n^2+2n-1)x^{n+1}-n^2x^{n+2}}{(1-x)^3}\\
\sum_{i=0}^n i^2 x^i
    & = x \cdot
    \frac{1+x-(n+1)^2x^{n}+(2n^2+2n-1)x^{n+1}-n^2x^{n+2}}{(1-x)^3}\\
    &= \frac{x+x^2-(n+1)^2x^{n+1}+(2n^2+2n-1)x^{n+2}-n^2x^{n+3}}{(1-x)^3}
\end{align*}
}

\ppart

\[
\sum_{i=0}^n \sum_{j=0}^m 3^{i+j}
\]

\solution{
\begin{align*}
\sum_{i=0}^n \sum_{j=0}^m 3^{i+j}
    & = \sum_{i=0}^n \left(3^i \cdot \sum_{j=0}^m 3^j\right) \\
    & = \left(\sum_{j=0}^m 3^j\right) \cdot \left(\sum_{i=0}^n 3^i\right)\\
    & = \left(\frac{3^{m+1} - 1}{2}\right) \cdot \left(\frac{3^{n+1} - 1}{2}\right)
\end{align*}
}


\eparts
\end{problem}

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

\begin{problem}
Pharaoh Aha I decides to build a ``pyramid'' in his honor consisting
of a single block:

\begin{center}
\includegraphics[height=0.5in]{aha1}
\end{center}

\noindent His successor, Aha II, trumps him by building a larger
pyramid:

\begin{center}
\includegraphics[height=1in]{aha2}
\end{center}

\noindent Not to be outdone, Aha III, builds a still-larger pyramid:

\begin{center}
\includegraphics[height=1.5in]{aha3}
\end{center}

\noindent If this continues, how many blocks will Pharoah Aha $n$
require?  Show your work.
\end{problem}

\solution{Vertical cuts divide the $n$th pyramid into $2n+1$
triangular slabs:

The number of blocks in a triangular slab of height $t$ is:
\begin{align*}
1 + 2 + \ldots + t + \ldots + 2 + 1
    & = t + 2 \sum_{i = 1}^{t-1} i \\
    & = t + 2 \cdot \frac{(t-1)t}{2} \\
    & = t^2
\end{align*}
Thus, the number of blocks in the $n$th pyramid is:
\begin{align*}
1^2 + 2^2 + \ldots + n^2 + \ldots + 2^2 + 1^2
    & = n^2 + 2 \sum_{i = 1}^{n-1} i^2 \\
    & = n^2 + 2 \cdot \frac{(n-1)n(2n-1)}{6} \\
    & = \frac{2n^3 + n}{3}
\end{align*}
}

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

\begin{problem}
Use integration to find upper and lower bounds that differ by at most
0.1 for the following sum.  (You may need to add the first few terms
explicitly and then use integrals to bound the sum of the remaining
terms.)  Show your work.
%
\[
\sum_{i=1}^{\infty} \frac{1}{(2i+1)^2}
\]

\solution{
Let's first try standard bounds:
%
\[
\int_0^{\infty} \frac{1}{(2x+3)^2}\ dx
\quad \leq \quad
\sum_{i=1}^{\infty} \frac{1}{(2i+1)^2}
\quad \leq \quad
\int_0^{\infty} \frac{1}{(2x+1)^2}\ dx
\]
%
Evaluating the integrals gives:
%
\[
\left. -\frac{1}{2(2x+3)}\ \right|_0^{\infty}
\quad \leq \quad
\sum_{i=1}^{\infty} \frac{1}{(2i+1)^2}
\quad \leq \quad
\left. -\frac{1}{2 (2x+1)}\ \right|_0^{\infty}
\]
%
\[
\frac{1}{6}
\quad \leq \quad
\sum_{i=1}^{\infty} \frac{1}{(2i+1)^2}
\quad \leq \quad
\frac{1}{2}
\]
%
These bounds are too far apart, so let's sum the first couple terms
explicitly and bound the rest with integrals.
%
\[
\frac{1}{3^2} + \frac{1}{5^2} + \int_2^{\infty} \frac{1}{(2x+3)^2}\ dx
\quad \leq \quad
\sum_{i=1}^{\infty} \frac{1}{(2i+1)^2}
\quad \leq \quad
\frac{1}{3^2} + \frac{1}{5^2} + \int_2^{\infty} \frac{1}{(2x+1)^2}\ dx
\]
%
Integration now gives:
%
\[
\frac{1}{3^2} + \frac{1}{5^2} +
    \left(\left. - \frac{1}{2 (2x+3)}\ \right|_2^{\infty}\right)
\quad \leq \quad
\sum_{i=1}^{\infty} \frac{1}{(2i+1)^2}
\quad \leq \quad
\frac{1}{3^2} + \frac{1}{5^2} + 
    \left(\left. - \frac{1}{2 (2x+1)}\ \right|_2^{\infty}\right)
\]
\[
\frac{1}{3^2} + \frac{1}{5^2} + \frac{1}{14}
\quad \leq \quad
\sum_{i=1}^{\infty} \frac{1}{(2i+1)^2}
\quad \leq \quad
\frac{1}{3^2} + \frac{1}{5^2} + \frac{1}{10}
\]
%
Now we have bounds that differ by $1/10 - 1/14 < 1/10 = 0.1$.}

\end{problem}

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

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

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

\end{document}                            
