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

%\hidesolutions
\showsolutions

\begin{document}

\recitation{10}{March 11, 2005}

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

\textbox{
\begin{align*}
1 + z + z^2 + \ldots + z^{n-1} & = \frac{1 - z^n}{1 - z} & (z \neq 1) \\
1 + z + x^2 + \ldots & = \frac{1}{1 - z} & (|z| < 1) \\
1 + 2 + 3 + \ldots + n & = \frac{n(n+1)}{2} \\
1^2 + 2^2 + 3^2 + \ldots + n^2 & = \frac{n(n+\frac{1}{2})(n+1)}{3} \\
1^3 + 2^3 + 3^3 + \ldots + n^3 & = \frac{n^2(n+1)^2}{4}
\end{align*}

\begin{theorem*}[Taylor's theorem]
Suppose that $f:\mathbb{R} \to \mathbb{R}$ is $n+1$ times
differentiable on the interval $[0,x]$.  Then
%
\[
f(x) = f(0) + f'(0) x + \frac{f''(0) x^2}{2!}
            + \ldots + \frac{f^{(n)}(0) x^n}{n!} + \frac{f^{(n+1)}(z) x^{n+1}}{(n+1)!}
\]
%
for some $z \in [0,x]$.
\end{theorem*}

}

\newpage

\section{Sums and Approximations}

\begin{problem}
Evaluate the following sums.

\bparts

\ppart
\[
1 + \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \ldots
\]

\solution[\vspace{1in}]{The formula for the sum of an infinite geometric series
with ratio $1/2$ gives:
%
\[
\frac{1}{1 - \frac{1}{2}} = 2
\]}

\ppart
\[
1 - \frac{1}{2} + \frac{1}{2^2} - \frac{1}{2^3} + \ldots
\]

\solution[\vspace{1in}]{The formula for the sum of an infinite geometric series
with ratio $- 1/2$ gives:
%
\[
\frac{1}{1 - \paren{- \frac{1}{2}}} = 2 / 3
\]}

\ppart
\[
1 + 2 + 4 + 8 + \ldots + 2^{n-1}
\]

\solution[\vspace{1in}]{The formula for the sum of a (finite) geometric series with
ratio 2 gives:
%
\[
\frac{1-2^n}{1 - 2} = 2^n - 1
\]}

\ppart
\[
\sum_{k=n}^{2n} k^2
\]

\solution[\vspace{1in}]{
\begin{align*}
\sum_{k=n+1}^{2n} k^2
    & = \sum_{k=1}^{2n} k^2 - \sum_{k=1}^n k^2 \\
    & = \frac{2n(2n+\frac{1}{2})(2n+1)}{3} -
        \frac{n(n+\frac{1}{2})(n+1)}{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}

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

\newpage

\begin{problem}
You've seen this neat trick for evaluating a geometric sum:
%
\begin{align*}
S & = 1 + z + z^2 + \ldots + z^n \\
zS & = z + z^2 + \ldots + z^n + z^{n+1} \\
S - z S & = 1 - z^{n+1} \\
S & = \frac{1-z^{n+1}}{1 - z}
\end{align*}

Use the same approach to find a closed-form expression for this sum:
%
\begin{align*}
T & = 1 z + 2 z^2 + 3 z^3 + \ldots + n z^n
\end{align*}
\end{problem}

\solution[\vspace{3in}]{
\begin{align*}
z T & = 1 z^2 + 2 z^3 + 3 z^4 + \ldots + n z^{n+1} \\
T - zT & = z + z^2 + z^3 + \ldots + z^n - n z^{n+1} \\
       & = \frac{1 - z^{n+1}}{1 - z} - 1 - n z^{n+1} \\
T & = \frac{1 - z^{n+1}}{(1 - z)^2} - \frac{1 + n z^{n+1}}{1 - z}
\end{align*}
}

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

\newpage

\begin{problem}
Here is a nasty product:
%
\[
\paren{1 + \frac{1}{n^2}}
\paren{1 + \frac{2}{n^2}}
\paren{1 + \frac{3}{n^2}}
\cdots
\paren{1 + \frac{n}{n^2}}
\]
%
Remarkably, an expression similar to this one comes up in analyzing
the distribution of birthdays.  Let's make sense of it.

\bparts

\ppart Give a two-term Taylor approximation for $e^x$.  (Forget about
the error term.)

\solution[\vspace{1in}]{
\[
e^x \approx 1 + x
\]
}

\ppart This is probably the most wide-used approximation in computer
science.  The fact that x appears at ``ground level'' in the
approximation and in the exponent of $e^x$ lets us translate sums into
products and vice-versa.  Rewrite the product using this
approximation.

\solution[\vspace{1.75in}]{
\[
e^{1/n^2} \cdot 
e^{2/n^2} \cdot 
e^{3/n^2} \cdot 
\cdots
e^{n/n^2}
=
e^{\frac{1 + 2 + \ldots + n}{n^2}}
\]
}

\ppart Now use a standard summation formula to simplify the exponent.

\solution[\vspace{1.75in}]{
The formula $1 + 2 + 3 + \ldots + n = n(n+1)/2$ gives:
%
\[
e^{n(n+1)/(2n^2)} = e^{1/2 + 1/2n}
\]
}

\ppart What constant does this approach for large $n$?

\solution{$\sqrt{e}$}

\eparts

\end{problem}

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

\newpage

\begin{problem} Let's use Taylor's Theorem to find some approximations
for the function $\sqrt{1 + x}$.

\bparts

\ppart Give a three-term Taylor approximation for $\sqrt{1 + x}$.

\solution[\vspace{1.5in}]{First, we compute two derivatives:
%
\begin{align*}
f'(x) & = \frac{1}{2 \sqrt{1 + x}} \\
f''(x) & = - \frac{1}{4 (1 + x)^{3/2}}
\end{align*}
%
Now we plug into Taylor's theorem:
%
\begin{align*}
f(x) & \approx f(0) + x f'(0) \\
     & 1 + \frac{x}{2} - \frac{x^2}{8}
\end{align*}}

\ppart Sketch the function $\sqrt{1 + x}$ and your approximation.  How
good is the approximation when $x = 8$?

\solution[\vspace{2in}]{The approximation is pretty bad when $x = 8$.
The actual value is 3, but the approximation is -3.}

\ppart Using this approximation and the fact that $\sqrt{1 + x} =
\sqrt{x} \sqrt{1 + 1/x}$, give an approximation for $\sqrt{1 + x}$
that is accurate for \textit{large} $x$

\solution[\vspace{1.5in}]{
\begin{align*}
\sqrt{1 + x}
    & = \sqrt{x} \sqrt{1 + 1/x} \\
    & \approx \sqrt{x} \paren{1 + \frac{1}{2 x} + \frac{1}{8 x^2}}
\end{align*}
}

\ppart Estimate:
%
\[
\sqrt{1,000,001}
\]
%
to a dozen places beyond the decimal point.  You can try to check your
answer with a calculator, but you'd better use a good one!

\solution{
\begin{align*}
\sqrt{1,000,001}
  & \approx 1000 \cdot \paren{1 + \frac{1}{2 \cdot 10^6} + \frac{1}{8 \cdot 10^{12}}} \\
  & = 1000.000500000125
\end{align*}
}

\eparts

\end{problem}

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

\end{document}
