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

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

%  Custom macros.

\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}
\newcommand{\edge}[2]{#1\text{---}#2}
\newcommand{\arc}[2]{#1\!\longrightarrow\!#2}

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

\begin{document}

\lecture{Sums, Approximations, and Asymptotics}{October 12, 2004}

\section{The Value of an Annuity}

If you won the lottery, would you prefer a million dollars today or
\$50,000 a year for the rest of your life?  This is a question about
the value of an annuity.  An \term{annuity} is a financial instrument
that pays out a fixed amount of money at the beginning of every year
for some specified number of years.  In particular, an $n$-year,
$\$m$-payment annuity pays $m$ dollars at the start of each year for
$n$ years.  In some cases, $n$ is finite, but not always.  Examples
include lottery payouts, student loans, and home mortgages.  There are
even Wall Street people who specialize in trading annuities.

A key question is what an annuity is actually worth.  For many
reasons, \$50,000 a year for 20 years is worth much less than a
million dollars right now.  For example, consider the last \$50,000
installment.  If you had that \$50,000 right now, then you could start
earning interest, invest the money in the stock market, or just buy
something fun.  However, if you don't get the \$50,000 for another 20
years, then someone else is earning all the interest or investment
profit.  Furthermore, prices are likely to gradually rise over the
next 20 years, so you when you finally get the money, you won't be
able to buy as much.  Furthermore, people only live so long; if you
were 90 years old, a payout 20 years in the future would be worth next
to nothing!

But what if your choice were between \$50,000 a year for 20 years and
a {\em half} million dollars today?

\subsection{The Future Value of Money}

In order to address such questions, we have to make an assumption
about the future value of money.  Let's put most of the complications
aside and think about this from a simple perspective.  Suppose you
invested \$1 today at an annual interest rate of $p$\%.  Then \$1
today would become $1 + p$ dollars in a year, $(1 + p)^2$ dollars in
two years and so forth.  A reasonable estimate for $p$ these days is
about $6\%$.

Looked at another way, a dollar paid out a year from now is worth $1 /
(1 + p)$ dollars today, a dollar paid in two years is worth only $1 /
(1 + p)^2$ today, etc.  Now we can work out the value of an annuity
that pays $m$ dollars at the start of each year for the next $n$
years:

\[
\begin{array}{lc}
\text{\underline{payments}} & \text{\underline{current value}} \\
\\
\$m \text{ today} & m \\
\\
\$m \text{ in 1 year} & {\displaystyle \frac{m}{1+p}} \\
\\
\$m \text{ in 2 years} & {\displaystyle \frac{m}{(1+p)^2}} \\
\\
\qquad \cdots & \quad \cdots \\
\\
\$m \text{ in $n-1$ years} & {\displaystyle \frac{m}{(1+p)^{n-1}}} \\
\\
\hline
\\
\text{Total current value:} & {\displaystyle V = \sum_{k=1}^{n} \frac{m}{(1+p)^{k-1}}}
\end{array}
\]

So to compute the value of the annuity, we need only evaluate this
sum.  We \textit{could} plug in values for $m$, $n$, and $p$, compute
each term explicitly, and then add them all up.  However, this
particular sum has an equivalent ``closed form'' that makes the job
easier.  In general, a \term{closed form} is a mathematical expression
that can be evaluated with a fixed number of basic operations
(addition, multiplication, exponentiation, etc.)  In contrast,
evaluating the sum above requires a number of operations proportional
to $n$.

\subsection{A Geometric Sum}

Our goal is to find a closed form equivalent to:
%
\[
V = \sum_{k=1}^{n} \frac{m}{(1+p)^{k-1}}
\]
%
Let's begin by rewriting the sum:
%
\begin{align*}
V & = \sum_{j=0}^{n-1} \frac{m}{(1+p)^j} & \text{(substitute $j = k - 1$)} \\
  & = m \sum_{j=0}^{n-1} x^j & \text{(where $x = \frac{1}{1+p}$)}
\end{align*}
%
The goal of these substitutions is to put the summation into a special
form so that we can bash it with a general theorem.  In particular,
the terms of the sum
%
\[
\sum_{j=0}^{n-1} x^j = 1 + x + x^2 + x^3 + \ldots + x^{n-1}
\]
%
form a \term{geometric series}, which means that each term is a
constant times the preceding term.  (In this case, the constant is
$x$.)  And we've already encountered a theorem about geometric sums:

\begin{theorem}
\label{th:geometric-sum}
For all $n \geq 1$ and all $z \neq 1$:
%
\[
\sum_{i=0}^{n} z^j = \frac{1- z^{n+1}}{1 - z}
\]
\end{theorem}
%
This theorem can be proved by induction, but that proof gives no hint
how the formula might be found in the first place.  Here is a more
insightful derivation based on the \term{perturbation method}.  First,
we let $S$ equal the value of the sum and then ``perturb'' it by
multiplying by $z$.
%
\[
\begin{array}{rclllllllllll}
  S & = & 1 & + & z & + & z^2 & + & \ldots & + & z^{n} \\
 zS & = &   &   & z & + & z^2 & + & \ldots & + & z^{n} & + & z^{n+1}
\end{array}
\]
%
The difference between the original sum and the perturbed sum is not
so great, because there is massive cancellation on the right side:
%
\[
S - zS = 1 - z^{n+1}
\]
%
Now solving for $S$ gives the expression in
Theorem~\ref{th:geometric-sum}:
%
\[
S = \frac{1 - z^{n+1}}{1 - z}
\]

You can derive a passable number of summation formulas by mimicking
the approach used above.  We'll look at some other methods for
evaluting sums shortly.

\subsection{Return of the Annuity Problem}

Now we can solve the annuity pricing problem!  The value of an annuity
that pays $m$ dollars at the start of each year for $n$ years is:
%
\begin{align*}
V	& = m \sum_{j=0}^{n-1} x^j \qquad \text{(where $x = \frac{1}{1+p}$)} \\
	& = m \cdot \frac{1 - x^n}{1 - x} \\
	& = m \cdot \frac{1 - \left(\frac{1}{1+p}\right)^n}
			{1 - \left(\frac{1}{1+p}\right)}
\end{align*}
%
We apply Theorem~\ref{th:geometric-sum} on the second line, and undo
the the earlier substitution $x = 1/(1+p)$ on the last line.

The last expression is a closed form; it can be evaluated with a fixed
number of basic operations.  For example, what is the real value of a
winning lottery ticket that pays $\$50,000$ per year for 20 years?
Plugging in $m = \$50,000$, $n = 20$, and $p = 0.6$ gives $V \approx
\$607,906$.  The deferred payments are worth more than a half million
dollars today, but not by much!

\subsection{Infinite Sums}

Would you prefer a million dollars today or \$50,000 a year
\textit{forever}?  This might seem like an easy choice--- when
infinite money is on offer, why worry about inflation?

This is a question about an \term{infinite sum}.  In general, the
value of an infinite sum is defined as the limit of a finite sum as
the number of terms goes to infinity:
%
\[
\sum_{k=0}^{\infty} z_k
\qquad
\text{ means }
\qquad
\lim_{n \to \infty} \sum_{k=0}^{n} z_k
\]

So the value of an annuity with an infinite number of payments is
given by our previous answer in the limit as $n$ goes to infinity:
%
\begin{align*}
V   & = \lim_{n \to \infty} m \cdot \frac{1 - \left(\frac{1}{1+p}\right)^n}
			                 {1 - \left(\frac{1}{1+p}\right)} \\
    & = m \cdot \frac{1}{1 - \left(\frac{1}{1+p}\right)} \\
    & = m \cdot \frac{1 + p}{p}
\end{align*}
%
In the second step, notice that the $1 / (1+p)^n$ term in the
numerator goes to zero in the limit.  The third equation follows by
simplifying.

Plugging in $m = \$50,000$ and $p = 0.6$ into this formula gives $V
\approx \$883,333$.  This means that getting $\$50,000$ per year
\textit{forever} is still not as good as a million dollars today!
Then again, if you had a million dollars today in the bank earning $p
= 6\%$ interest, you could take out and spend $\$60,000$ a year
forever.  So this answer makes some sense.

More generally, we can get a closed form for infinite geometric sums
from Theorem~\ref{th:geometric-sum} by taking a limit.

\begin{corollary}
\label{cor:inf-geometric-sum}
If $|z| < 1$, then:
%
\[
\sum_{i=0}^{\infty} z^i = \frac{1}{1 - z}
\]
\end{corollary}

\begin{proof}
\begin{align*}
\sum_{i=0}^{\infty} z^i
    & = \lim_{n \to \infty} \sum_{i=0}^{n} z^i \\
    & = \lim_{n \to \infty} \frac{1 - z^{n+1}}{1 - z} \\
    & = \frac{1}{1 - z}
\end{align*}
%
The first equation uses the definition of an infinite limit, and the
second uses Theorem~\ref{th:geometric-sum}.  In the limit, the term
$z^{n+1}$ in the numerator vanishes since $|z| < 1$.
\end{proof}

We now have closed forms for both finite and infinite geometric
series.  Some examples are given below.  In each case, the solution
follows immediately from either Theorem~\ref{th:geometric-sum} (for
finite series) or Corollary~\ref{cor:inf-geometric-sum} (for infinite
series).
%
\begin{gather*}
1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \ldots
    = \sum_{i=0}^\infty (1/2)^i
    = \frac{1}{1-(1/2)}
    = 2 \\
1 - \frac{1}{2} + \frac{1}{4} - \frac{1}{8} + \ldots
    = \sum_{i=0}^\infty (-1/2)^i
    = \frac{1}{1 - (-1/2)}
    = \frac{2}{3} \\
1 + 2 + 4 + 8 + \ldots + 2^{n-1}
    = \sum_{i=0}^{n-1} 2^i
    = \frac{1 - 2^n}{1 - 2}
    = 2^n - 1 \\
1 + 3 + 9 + 27 + \ldots + 3^{n-1}
    = \sum_{i=0}^{n-1} 3^i
    = \frac{1 - 3^n}{1 - 3}
    = \frac{3^n - 1}{2}
\end{gather*}

Here is a good rule of thumb: \textit{the sum of a geometric series is
approximately equal to the term with greatest absolute value}.  In the
first two examples, the largest term is equal to 1 and the sums are 2
and 2/3, which are both relatively close to 1.  In the third example,
the sum is about twice the largest term.  In the final example, the
largest term is $3^{n-1}$ and the sum is $(3^n-1)/2$, which is 1.5
times greater.

\section{Variants of Geometric Sums}

You now know everything about geometric series.  But one often
encounters sums that cannot be transformed by simple variable
substitutions to the form $\sum z^i$.  A useful way to obtain new
summation formulas from old is by \textit{differentiating} or
\textit{integrating} with respect to $z$.

For example, consider the following series:
%
\[
\sum_{i=1}^n i z^i = z + 2 z^2 + 3 z^3 + \ldots + n z^n
\]
%
This is not a geometric series, since the ratio between successive
terms is not constant.  So our formula for the sum of a geometric
series cannot be directly applied.  But suppose that we differentiate
both sides of that equation:
%
\begin{align*}
\frac{d}{dz} \ \sum_{i=0}^n z^i
 & = \frac{d}{dz} \ \frac{1 - z^{n+1}}{1 - z} \\
\sum_{i=0}^{n} i z^{i-1}
 & = \frac{-(n+1)z^n (1-z) - (-1)(1-z^{n+1})}{(1 - z)^2} \\
 & = \frac{-(n+1)z^n + (n+1)z^{n+1} + 1 - z^{n+1}}{(1 - z)^2} \\
 & = \frac{1 - (n+1)z^n + n z^{n+1}}{(1 - z)^2}
\end{align*}

Often differentiating or integrating messes up the exponent of $z$ in
every term.  In this case, we now have a formula for a sum of the form
$\sum i z^{i-1}$, but we want a formula for $\sum i z^i$.  The
solution is to multiply both sidez by $z$.  Let's bundle up the result
as a theorem:

\begin{theorem}
\label{th:sum-izi}
For all $n \geq 0$ and all $z \neq 1$:
%
\[
\sum_{i=0}^{n} i z^i = \frac{z - (n+1)z^{n+1} + n z^{n+2}}{(1 - z)^2}
\]
\end{theorem}

If $|z| < 1$, then the sum converges to a finite value even if there
are infinitely many terms.  Taking the limit as $n$ tends infinity
gives:
%
\begin{corollary}
\label{cor:inf-sum-izi}
If $|z| < 1$, then:

\[
\sum_{i=0}^\infty i z^i = \frac{z}{(1-z)^2}
\]
\end{corollary}

As a consequence, suppose you're offered \$50,000 at the end of this
year, \$100,000 at the end of next year, \$150,000 after the following
year, and so on.  How much is this worth?  Surely \textit{this} is
infinite money!  Let's work out the answer:
%
\begin{align*}
V & = \sum_{i=1}^n \frac{m}{(1+p)^i} \\
  & = m \cdot \frac{\frac{1}{1+p}}{\left(1 - \frac{1}{1+p}\right)^2} \\
  & = m \cdot \frac{1+p}{p^2}
\end{align*}
%
The second line follows from Corollary~\ref{cor:inf-sum-izi}.  The
last step is simplification.

Setting $m = \$50,000$ and $p = 0.06$ gives value of the annuity:
\$14,722,222.  Intuitively, even though payments increase every year,
they increase only \textit{linearly} with time.  In contrast, dollars
paid out in the future decrease in value \textit{exponentially} with
time.  As a result, payments in the distant future are almost
worthless, so the value of the annuity is still finite!

Integrating a geometric sum gives yet another summation formula.
Let's start with the formula for an infinite geometric sum:
%
\[
\sum_{i=0}^{\infty} z^i = \frac{1}{1 - z} \qquad (|z| < 1)
\]
%
Now we integrate both sides from 0 to $x$:
%
\begin{align*}
\int_{0}^{x} \sum_{i=0}^{\infty} z^i\ dz
    & = \int_{0}^{x} \frac{1}{1 - z}\ dz \\
\left. \sum_{i=0}^{\infty} \frac{z^{i+1}}{i+1}\ \right|_0^x
    & = - \ln(1 - z)\ \bigr|_0^x \\
\sum_{i=0}^{\infty} \frac{x^{i+1}}{i+1}
    & = - \ln(1 - x)
\end{align*}
%
Reindexing on the left side with the substitution $j = i + 1$ gives
the summation formula:
%
\[
\sum_{j=1}^{\infty} \frac{x^j}{j} = - \ln(1 - x)
\]
%
You might have seen this before: this is the the Taylor expansion for
$- \ln(1-x)$.

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

\section{Sums of Powers}

Long ago, in the before-time, we verified the formula:
%
\[
\sum_{i=1}^n i = \frac{n(n + 1)}{2}
\]
%
The source of this formula is still a mystery!  Sure, we can prove
this statement by induction, but where did the expression on the right
come from in the first place?  Even more inexplicable is the summation
formula for consecutive squares:
%
\begin{equation}
\sum_{i=1}^n i^2 = \frac{(2n+1)(n+1)n}{6} \tag{1} \label{eq:sum-of-squares}
\end{equation}

Here is one way we might discover such formulas.  Remember that sums
are the discrete cousins of integrals.  So we might guess that the sum
of a degree-$k$ polynomial is a degree-$(k+1)$ polynomial, just as if
we were integrating.  If this guess is correct, then
%
\[
\sum_{i=1}^n i^2 = a n^3 + b n^2 + c n + d
\]
%
for some constants $a$, $b$, $c$, and $d$.  All that remains is to
determine these constants.  We can do this by plugging a few values
for $n$ into the equation above.  Each value gives a linear equation
in $a$, $b$, $c$, and $d$.  For example:
%
\begin{align*}
n = 0 & \quad \implies \quad 0 = d \\
n = 1 & \quad \implies \quad 1 = a + b + c + d \\
n = 2 & \quad \implies \quad 5 = 8a + 4b + 2c + d \\
n = 3 & \quad \implies \quad 14 = 27a + 9b + 3c + d
\end{align*}

We now have four equations in four unknowns.  Solving this system
gives $a = 1/3$, $b = 1/2$, $c = 1/6$, and $d = 0$ and so it is
tempting to conclude that:
%
\begin{equation}
\sum_{i=1}^n i^2 = \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6} \tag{2} \label{eq:sum-of-squares2}
\end{equation}
%
\textit{Be careful!}  This equation is valid only if we were correct
in our initial guess at the form of the solution.  If we were wrong,
then the equation above might not hold all $n$!  The only way to be
sure is to verify this formula with an induction proof.  In fact, we
did guess correctly; the expressions on the right sides of
equations~\eqref{eq:sum-of-squares} and~\eqref{eq:sum-of-squares2} are
equal.

\section{Approximating Sums}

Unfortunately, there is no equivalent closed-form for many of the sums
that arise in practice.  Here is an example that we'll gnaw on for
quite a while:
%
\begin{equation}
\sum_{i=1}^n \sqrt{i} \tag{*} \label{eq:sum1}
\end{equation}

There is no closed form exactly equal to this sum, which we'll refer
to as~\eqref{eq:sum1} hereafter.  However, there do exist good
closed-form upper and lower bounds.  And for many practical problems,
bounds and approximations are good enough.

\subsection{Integration Bounds}

One way to cope with sums is pass over to the continuous world and
apply integration techniques.  Suppose that we represent the
sum~\eqref{eq:sum1} with a ``bar graph'' on the coordinate plane:
%
\begin{center}
\unitlength=0.333in
\begin{picture}(12, 9)(-2,-1.5)
\put(0.000000,0){\framebox(1.0,2.000000){}}
\put(1.000000,0){\framebox(1.0,2.828427){}}
\put(2.000000,0){\framebox(1.0,3.464102){}}
\put(3.000000,0){\framebox(1.0,4.000000){}}
\put(8.000000,0){\framebox(1.0,6.000000){}}
\put(0,0){\vector(1,0){10}}
\put(0,0){\vector(0,1){6}}
\put(10.5,0){$x$}
\put(0,6.5){$y$}
\put(0,-0.5){\makebox(0,0){0}}
\put(1,-0.5){\makebox(0,0){1}}
\put(2,-0.5){\makebox(0,0){2}}
\put(3,-0.5){\makebox(0,0){3}}
\put(4,-0.5){\makebox(0,0){4}}
\put(9,-0.5){\makebox(0,0){$n$}}
\put(6,2){\makebox(0,0){\ldots}}
\put(0.5,1.0){\makebox(0,0){$\sqrt{1}$}}
\put(1.5,1.0){\makebox(0,0){$\sqrt{2}$}}
\put(2.5,1.0){\makebox(0,0){$\sqrt{3}$}}
\put(3.5,1.0){\makebox(0,0){$\sqrt{4}$}}
\put(8.5,1.0){\makebox(0,0){$\sqrt{n}$}}
\end{picture}
\end{center}
%
The $i$-th bar from the left has height $\sqrt{i}$ and width $1$.  So
the area of the $i$-th bar is equal to the value of the $i$-th term in
the sum.  Thus, \textit{the area of the bar graph is equal the value
of the sum~\eqref{eq:sum1}}.  Now the graph of the function $y =
\sqrt{x + 1}$ runs just above the bar graph, and the graph of $y =
\sqrt{x}$ runs just below:
%
\begin{center}
\unitlength=0.333in
\begin{picture}(12, 9)(-2,-1.5)
% upper curve
\qbezier(0.000000,2.000000)(0.414214,2.414214)(1.000000,2.828427)
\qbezier(1.000000,2.828427)(1.449490,3.146264)(2.000000,3.464102)
\qbezier(2.000000,3.464102)(2.464102,3.732051)(3.000000,4.000000)
\qbezier(3.000000,4.000000)(3.472136,4.236068)(4.000000,4.472136)
\qbezier(4.000000,4.472136)(4.477226,4.685558)(5.000000,4.898979)
\qbezier(5.000000,4.898979)(5.480741,5.095241)(6.000000,5.291503)
\qbezier(6.000000,5.291503)(6.483315,5.474178)(7.000000,5.656854)
\qbezier(7.000000,5.656854)(7.485281,5.828427)(8.000000,6.000000)
\qbezier(8.000000,6.000000)(8.486833,6.162278)(9.000000,6.324555)
\put(3.75,5.5){\makebox{$y = \sqrt{x+1}$}}
% lower curve
\qbezier(0.000000,0.000000)(0,1)(1.000000,2.000000)
\qbezier(1.000000,2.000000)(1.414214,2.414214)(2.000000,2.828427)
\qbezier(2.000000,2.828427)(2.449490,3.146264)(3.000000,3.464102)
\qbezier(3.000000,3.464102)(3.464102,3.732051)(4.000000,4.000000)
\qbezier(4.000000,4.000000)(4.472136,4.236068)(5.000000,4.472136)
\qbezier(5.000000,4.472136)(5.477226,4.685558)(6.000000,4.898979)
\qbezier(6.000000,4.898979)(6.480741,5.095241)(7.000000,5.291503)
\qbezier(7.000000,5.291503)(7.483315,5.474178)(8.000000,5.656854)
\qbezier(8.000000,5.656854)(8.485281,5.828427)(9.000000,6.000000)
\put(5,4.0){\makebox{$y = \sqrt{x}$}}
% bar graph
\put(0.000000,0){\framebox(1.0,2.000000){}}
\put(1.000000,0){\framebox(1.0,2.828427){}}
\put(2.000000,0){\framebox(1.0,3.464102){}}
\put(3.000000,0){\framebox(1.0,4.000000){}}
\put(8.000000,0){\framebox(1.0,6.000000){}}
% annotations
\put(0,0){\vector(1,0){10}}
\put(0,0){\vector(0,1){6}}
\put(10.5,0){$x$}
\put(0,6.5){$y$}
\put(0,-0.5){\makebox(0,0){0}}
\put(1,-0.5){\makebox(0,0){1}}
\put(2,-0.5){\makebox(0,0){2}}
\put(3,-0.5){\makebox(0,0){3}}
\put(4,-0.5){\makebox(0,0){4}}
\put(9,-0.5){\makebox(0,0){$n$}}
\put(6,2){\makebox(0,0){\ldots}}
\put(0.5,0.5){\makebox(0,0){$\sqrt{1}$}}
\put(1.5,1.0){\makebox(0,0){$\sqrt{2}$}}
\put(2.5,1.0){\makebox(0,0){$\sqrt{3}$}}
\put(3.5,1.0){\makebox(0,0){$\sqrt{4}$}}
\put(8.5,1.0){\makebox(0,0){$\sqrt{n}$}}
\end{picture}
\end{center}
%
So the areas beneath these curves are upper and lower bounds on the
area of the bar graph and thus are upper and lower bounds on
sum~\eqref{eq:sum1}.  In symbols:
%
\[
\int_0^n \sqrt{x}\ dx
\quad \leq \quad
\sum_{i=1}^n \sqrt{i}
\quad \leq \quad
\int_0^n \sqrt{x+1}\ dx
\]

Now we can obtain closed-form bounds by integration:
%
\begin{gather*}
\left.\frac{x^{3/2}}{3/2}\ \right|_0^n
\quad \leq \quad
\sum_{i=1}^n \sqrt{i}
\quad \leq \quad
\left.\frac{(x+1)^{3/2}}{3/2}\ \right|_0^n \\
\frac{2}{3} n^{3/2}
\quad \leq \quad
\sum_{i=1}^n \sqrt{i}
\quad \leq \quad
\frac{2}{3} \bigl((n+1)^{3/2} - 1\bigr)
\end{gather*}
%
These are pretty good bounds.  For example, if $n = 100$, then we get:
%
\[
666.7
\quad \leq \quad
\sqrt{1} + \sqrt{2} + \ldots + \sqrt{100}
\quad \leq \quad
676.1
\]

In order to determine exactly \textit{how good} these bounds are in
general, we'll need a better understanding of the rather complicated
upper bound, $\frac{2}{3} ((n+1)^{3/2} - 1)$.

\subsection{Taylor's Theorem}

In practice, a simple, approximate answer is often better than an
exact, complicated answer.  A great way to get such approximations is
to dredge Taylor's Theorem up from the dark, murky regions of
single-variable calculus.

\begin{theorem}[Taylor's Theorem]
If $f$ is a real-valued function, then
%
\[
f(x) = \frac{f(0)}{0!} + \frac{f'(0)}{1!} x +
       \frac{f''(0)}{2!} x^2 + \ldots + \frac{f^{(n-1)}(0)}{(n-1)!} x^{n-1}
       + \underbrace{\frac{f^{(n)}(z)}{n!} x^n}_{\text{``error term''}}
\]
%
for some $z \in [0,x]$, provided $f$ is continuous on $[0,x]$ and $n$
derivatives exist on $(0,x)$.
\end{theorem}

The idea is to approximate the function $f$ with a short Taylor
series.  We can then analyze the approximation by studying the ``error
term''.  Let's see how this plays out for the function that came up in
the previous section:
%
\[
\frac{2}{3}\bigl((n+1)^{3/2} - 1\bigr)
\]

The crux of this expression is $(n + 1)^{3/2}$.  However, Taylor's
Theorem usually approximates a function $f(x)$ best for $x$ close to
zero.  But $n$ could be a big number, so we're in some trouble.  But
we can rewrite the expression into a more tractable form:
%
\[
\frac{2}{3} \left(n^{3/2} \cdot \left(1+\frac{1}{n}\right)^{3/2} - 1\right)
\]
%
Now the nasty bit is $(1 + 1/n)^{3/2}$.  If we let $x = 1/n$, then our
job is to approximate $(1 + x)^{3/2}$ where \textit{$x$ is close to
zero}.  This is a proper target for Taylor's Theorem.  First, we
compute a few derivatives and their values at 0.
%
\begin{align*}
f(x) & = (1+x)^{3/2}&
f(0) & = 1 \\
f'(x) & = \frac{3}{2} \cdot (1+x)^{1/2} &
f'(0) & = \frac{3}{2} \\
f''(x) & = \frac{3}{2} \cdot \frac{1}{2} \cdot (1+x)^{-1/2} &
f''(0) & = \frac{3}{4}
\end{align*}
%
Now Taylor's Theorem says
%
\begin{align*}
f(x) & = \frac{f(0)}{0!} + \frac{f'(0)}{1!} x + \frac{f''(z)}{2!} x^2 \\
     & = 1 + \frac{3}{2} x + \frac{3}{8} (1+z)^{-1/2} x^2
\end{align*}
%
for some $z \in [0,x]$.  This expression is maximized when $z = 0$, so
we get the upper bound:
%
\[
(1+x)^{3/2} \leq 1 + \frac{3}{2} x + \frac{3}{8} x^2
\]

Now we can upper bound our original expression.
%
\begin{align*}
\frac{2}{3}\bigl((n+1)^{3/2} - 1\bigr)
    & = \frac{2}{3} \left(n^{3/2} \cdot \left(1+\frac{1}{n}\right)^{3/2} - 1\right) \\
    & \leq \frac{2}{3} \left(n^{3/2} \cdot \left( 1 + \frac{3}{2} \cdot \frac{1}{n} + \frac{3}{8} \cdot \frac{1}{n^2} \right) - 1\right) \\
    & = \frac{2}{3} n^{3/2} + \sqrt{n} - \frac{2}{3} + \frac{1}{4 \sqrt{n}}
\end{align*}
%
There are a lot of terms here, so this might not seem like much of an
improvement!  However, each term has a simple form.  And simpler terms
are easier to cancel and combine in subsequent calculations.

Applying Taylor's Theorem involved a lot of grungy math, but you can
see the result in a picture.  This is a plot of the original function
compared to the upper bound we just derived:

\begin{center}
\unitlength=2in
\begin{picture}(1.8,1.3)(0,-0.2)
\put(0,0){\vector(1,0){1.8}}
\put(0,0){\vector(0,1){1.1}}
% function
\qbezier(0.000000,0.000000)(0.049603,0.024801)(0.100000,0.051230)
\qbezier(0.100000,0.051230)(0.149638,0.077260)(0.200000,0.104845)
\qbezier(0.200000,0.104845)(0.249667,0.132048)(0.300000,0.160743)
\qbezier(0.300000,0.160743)(0.349691,0.189071)(0.400000,0.218834)
\qbezier(0.400000,0.218834)(0.449713,0.248244)(0.500000,0.279039)
\qbezier(0.500000,0.279039)(0.549731,0.309493)(0.600000,0.341286)
\qbezier(0.600000,0.341286)(0.649747,0.372749)(0.700000,0.405510)
\qbezier(0.700000,0.405510)(0.749762,0.437950)(0.800000,0.471651)
\qbezier(0.800000,0.471651)(0.849775,0.505041)(0.900000,0.539656)
\qbezier(0.900000,0.539656)(0.949786,0.573969)(1.000000,0.609476)
\qbezier(1.000000,0.609476)(1.049797,0.644687)(1.100000,0.681063)
\qbezier(1.100000,0.681063)(1.149806,0.717151)(1.200000,0.754376)
\qbezier(1.200000,0.754376)(1.249815,0.791319)(1.300000,0.829374)
\qbezier(1.300000,0.829374)(1.349823,0.867154)(1.400000,0.906021)
\qbezier(1.400000,0.906021)(1.449830,0.944619)(1.500000,0.984282)
\qbezier(1.500000,0.984282)(1.549837,1.023682)(1.600000,1.064125)
% upper bound
\qbezier(0.008000,1.109169)(0.017392,0.315506)(0.100000,0.230606)
\qbezier(0.100000,0.230606)(0.135440,0.194183)(0.200000,0.199596)
\qbezier(0.200000,0.199596)(0.241610,0.203085)(0.300000,0.223518)
\qbezier(0.300000,0.223518)(0.344529,0.239100)(0.400000,0.264864)
\qbezier(0.400000,0.264864)(0.446293,0.286365)(0.500000,0.314848)
\qbezier(0.500000,0.314848)(0.547439,0.340006)(0.600000,0.370259)
\qbezier(0.600000,0.370259)(0.648197,0.397999)(0.700000,0.429621)
\qbezier(0.700000,0.429621)(0.748698,0.459347)(0.800000,0.492148)
\qbezier(0.800000,0.492148)(0.849033,0.523499)(0.900000,0.557375)
\qbezier(0.900000,0.557375)(0.949259,0.590115)(1.000000,0.625000)
\qbezier(1.000000,0.625000)(1.049414,0.658972)(1.100000,0.694817)
\qbezier(1.100000,0.694817)(1.149524,0.729910)(1.200000,0.766676)
\qbezier(1.200000,0.766676)(1.249603,0.802806)(1.300000,0.840463)
\qbezier(1.300000,0.840463)(1.349661,0.877568)(1.400000,0.916086)
\qbezier(1.400000,0.916086)(1.449704,0.954118)(1.500000,0.993474)
\qbezier(1.500000,0.993474)(1.549738,1.032392)(1.600000,1.072563)
% annotations
\put(0,-0.1){\makebox(0,0){$n = 0$}}
\put(1.6,-0.1){\makebox(0,0){$n = 1.6$}}
\put(0.9,0.2){\makebox(0,0){$y = \frac{2}{3}((n+1)^{3/2} - 1)$}}
\put(0.9,1.0){\makebox(0,0){$y = \frac{2}{3} n^{3/2} + \sqrt{n} - \frac{2}{3} + \frac{1}{4 \sqrt{n}}$}}
\end{picture}
\end{center}

\noindent The picture shows that our upper bound is \textit{extremely}
close to the original function, except for very small values of $n$.

\subsection{Back to the Sum}

Before we got to yammering on about Taylor's Theorem, we proved bounds
on the sum~\eqref{eq:sum1}:
%
\[
\frac{2}{3} n^{3/2}
\quad \leq \quad
\sum_{i=1}^n \sqrt{i}
\quad \leq \quad
\frac{2}{3} \bigl((n+1)^{3/2} - 1\bigr)
\]
%
Let's rewrite the right side using the upper bound we just derived:
%
\[
\begin{array}{rcccl}
{\displaystyle \frac{2}{3} n^{3/2}}
& \leq &
{\displaystyle \sum_{i=1}^n \sqrt{i}}
& \leq &
{\displaystyle
    \frac{2}{3} n^{3/2} + \sqrt{n} - \frac{2}{3} + \frac{1}{4 \sqrt{n}}}

\end{array}
\]
%
Now the dominant term in both the lower and upper bounds is
$\frac{2}{3}n^{2/3}$, so we can compare the two more readily.  As you
can see, the gap between the bounds is at most $\sqrt{n}$, which is
small relative to the sum as a whole.  In fact, the gap between upper
and lower bounds that we actually observed for $n = 100$ was very
nearly $\sqrt{100} = 10$.
%
\[
666.7
\quad \leq \quad
\sqrt{1} + \sqrt{2} + \ldots + \sqrt{100}
\quad \leq \quad
676.1
\]

There is an elaborate system of notation for describing the quality of
approximations.  One simple convention is:
%
\[
f(n) \sim g(n) \hspace{0.5in}
\text{means} \hspace{0.5in}
\lim_{n\to\infty} \frac{f(n)}{g(n)} = 1
\]
%
In terms of this notation, we've just shown that:
%
\[
\sum_{i=1}^n \sqrt{i} \quad \sim \quad \frac{2}{3}n^{3/2}
\]
%
Thus, with a little loss of accuracy, we can replace this vicious sum
with a simple closed form.

\subsection{Another Integration Example}

Let's work through one more example of using integrals to bound a
nasty sum.  This time our target is:
%
\[
\sum_{i=1}^n \frac{1}{\sqrt{n}}
\]
%
As before, we construct a bar graph whose area is equal to the value
of the sum.  Then we find curves that lie just above and below the
bars:

\begin{center}
\unitlength=0.5in
\begin{picture}(9,7)(-1,-1)
\qbezier(0.500000,5.656854)(0.679623,4.640754)(1.000000,4.000000)
\qbezier(1.000000,4.000000)(1.359246,3.281509)(2.000000,2.828427)
\qbezier(2.000000,2.828427)(2.416273,2.534078)(3.000000,2.309401)
\qbezier(3.000000,2.309401)(3.440334,2.139917)(4.000000,2.000000)
\qbezier(4.000000,2.000000)(4.453637,1.886591)(5.000000,1.788854)
\qbezier(5.000000,1.788854)(5.462085,1.706194)(6.000000,1.632993)
\qbezier(6.000000,1.632993)(6.467927,1.569316)(7.000000,1.511858)
\qbezier(7.000000,1.511858)(7.472208,1.460864)(8.000000,1.414214)
\put(0.000000,0){\framebox(1.0,4.000000){}}
\put(1.000000,0){\framebox(1.0,2.828427){}}
\put(2.000000,0){\framebox(1.0,2.309401){}}
%\put(3.000000,0){\framebox(1.0,2.000000){}}
%\put(4.000000,0){\framebox(1.0,1.788854){}}
%\put(5.000000,0){\framebox(1.0,1.632993){}}
%\put(6.000000,0){\framebox(1.0,1.511858){}}
\put(7.000000,0){\framebox(1.0,1.414214){}}
\qbezier(0.000000,4.000000)(0.359246,3.281509)(1.000000,2.828427)
\qbezier(1.000000,2.828427)(1.416273,2.534078)(2.000000,2.309401)
\qbezier(2.000000,2.309401)(2.440334,2.139917)(3.000000,2.000000)
\qbezier(3.000000,2.000000)(3.453637,1.886591)(4.000000,1.788854)
\qbezier(4.000000,1.788854)(4.462085,1.706194)(5.000000,1.632993)
\qbezier(5.000000,1.632993)(5.467927,1.569316)(6.000000,1.511858)
\qbezier(6.000000,1.511858)(6.472208,1.460864)(7.000000,1.414214)
\qbezier(7.000000,1.414214)(7.475480,1.372187)(8.000000,1.333333)
\put(0,0){\vector(1,0){9}}
\put(0,0){\vector(0,1){6}}
\put(0,-0.5){\makebox(0,0){0}}
\put(1,-0.5){\makebox(0,0){1}}
\put(2,-0.5){\makebox(0,0){2}}
\put(3,-0.5){\makebox(0,0){3}}
\put(8,-0.5){\makebox(0,0){$n$}}
\put(0.5,0.5){\makebox(0,0){${\displaystyle \frac{1}{\sqrt{1}}}$}}
\put(1.5,0.5){\makebox(0,0){${\displaystyle \frac{1}{\sqrt{2}}}$}}
\put(2.5,0.5){\makebox(0,0){${\displaystyle \frac{1}{\sqrt{3}}}$}}
\put(7.5,0.5){\makebox(0,0){${\displaystyle \frac{1}{\sqrt{n}}}$}}
\put(5,0.9){\makebox(0,0){${\displaystyle y = \frac{1}{\sqrt{n+1}}}$}}
\put(4,2.75){\makebox(0,0){${\displaystyle y = \frac{1}{\sqrt{n}}}$}}
\end{picture}
\end{center}

In this way, we get the bounds:
%
\[
\int_0^n \frac{1}{\sqrt{x + 1}}\ dx
\qquad \leq \qquad
\sum_{i=1}^n \frac{1}{\sqrt{n}}
\qquad \leq \qquad
\int_0^n \frac{1}{\sqrt{x}}\ dx
\]
%
Now the picture shows that most of the error arises because of the
large gap between the two curves for small values of $n$.  In
particular, the upper curve goes off to infinity as $n$ approaches
zero!

We can eliminate some of this error by summing a couple terms
explicitly, and bounding the remaining terms with integrals.  For
example, summing two terms explicitly gives:
%
\[
\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} +
\int_2^n \frac{1}{\sqrt{x + 1}}\ dx
\qquad \leq \qquad
\sum_{i=1}^n \frac{1}{\sqrt{n}}
\qquad \leq \qquad
\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} +
\int_2^n \frac{1}{\sqrt{x}}\ dx
\]
%
Evaluating the integrals and simplifying, we find:
%
\[
\frac{2 + \sqrt{2} - 4 \sqrt{3}}{2} + 
2 \sqrt{n + 1}
\qquad \leq \qquad
\sum_{i=1}^n \frac{1}{\sqrt{n}}
\qquad \leq \qquad
\frac{2 - 3 \sqrt{2}}{2} + 
2 \sqrt{n}
\]
%
Computing the values of the constants gives:
%
\[
2 \sqrt{n + 1} - 1.75
\qquad \leq \qquad
\sum_{i=1}^n \frac{1}{\sqrt{n}}
\qquad \leq \qquad
2 \sqrt{n} - 1.12
\]
%
These bounds are quite tight; they always differ by less than 1.  So
once again, we've gotten a good handle on a sum that has no exact
closed-form equivalent.
\end{document}
