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

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

%  Custom macros.

\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}

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

\begin{document}

\lecture{Sums and Approximations}{March 10, 2005}

When you analyze the running time of an algorithm, the probability
some procedure succeeds, or the behavior of a load-balancing or
communications scheme, you'll \textit{rarely} get a simple answer.
The world is not so kind.  More likely, you'll end up with a
complicated sum:
%
\[
\sum_{k=1}^n \frac{1}{k + \sqrt{k}}
\]
%
Or 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}}
\]
%
Or you might get an answer that is just tad too complicated to grasp
intuitively:
%
\[
\left(1 +  \frac{72 / n}{100}\right)^n
\]
%
And these examples are relatively benign!

So the ability to cope with such messy mathematical expressions is an
important skill in computer science--- and in many other areas of
science and engineering.  This might not seem glorious, but people who
can cut monstrous expressions down to size in moments can seem
\textit{pretty amazing} to the uninitiated.  This week, we'll equip
you with the most useful tricks of the trade.

\section{The Value of an Annuity}

Would you prefer a million dollars today or \$20,000 a year for the
next fifty years?

This is a question about the value of an \term{annuity}, 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.

For many reasons, \$20,000 a year for 50 years is worth much less than
a million dollars right now.  For example, consider the last \$20,000
installment.  If you had that \$20,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 \$20,000 for another 50
years, then someone else is earning all the interest or investment
profit.  Furthermore, prices are likely to gradually rise over the
next 50 years, so you when you finally get the money, you won't be
able to buy as much.  Finally, people only live so long; if you were
60 years old, a payout 50 years in the future would be worth next to
nothing!

But what if your choice were between \textit{\$40,000} a year for 50
years and a million dollars today?  Now which is better?  What is an
annuity is actually worth?

\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-minded perspective.  The
average rate of inflation in the United States from 1980 to 2004 was
about $p = 3.5\%$ per year.  This means that the price of a selection
of basic goods increases by about 3.5\% each year.  If this trend
continues, then goods costing \$100 today will cost:
%
\begin{align*}
\$100 (1 + p) & = \$103.50 \text{ in 1 year} \\
\$100 (1 + p)^2 & = \$107.12 \text{ in 2 year} \\
 \ldots \\
\$100 (1 + p)^k &            \text{ in k years}
\end{align*}
%
Looked at another way, $k$ years from now, \$100 will have the buying
power of just $100 / (1 + p)^k$ dollars today.

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}} \\[1.5ex]
\$m \text{ today} & m \\[1.5ex]
\$m \text{ in 1 year} & {\displaystyle \frac{m}{1+p}} \\[2ex]
\$m \text{ in 2 years} & {\displaystyle \frac{m}{(1+p)^2}} \\[1.5ex]
\qquad \cdots & \quad \cdots \\[1.5ex]
\$m \text{ in $n-1$ years} & {\displaystyle \frac{m}{(1+p)^{n-1}}} \\[1.5ex]
\\
\hline
\\
\text{Total current value:} & {\displaystyle V = \sum_{k=0}^{n-1} \frac{m}{(1+p)^k}}
\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 the summation:
%
\[
V = \sum_{k=0}^{n-1} \frac{m}{(1+p)^k}
  = m + \frac{m}{1+p} + \frac{m}{(1+p)^2} + \ldots + \frac{m}{(1+p)^{k-1}}
\]
%
This is a \term{geometric sum}, which means that consecutive terms all
have the same ratio.  In particular, the second term is $1 / (1 + p)$
times the first, the third is $1/ (1 + p)$ times the second, and so
forth.  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_{k=0}^{n-1} z^k = \frac{1- z^{n}}{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-1} \\
 zS & = &   &   & z & + & z^2 & + & \ldots & + & z^{n-1} & + & z^{n}
\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}
\]
%
Now solving for $S$ gives the expression in
Theorem~\ref{th:geometric-sum}:
%
\[
S = \frac{1 - z^{n}}{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	& = \sum_{k=0}^{n-1} \frac{m}{(1+k)^p} \\
        & = m \sum_{k=0}^{n-1} z^k \qquad \text{(where $z = \frac{1}{1+p}$)} \\
	& = m \cdot \frac{1 - z^n}{1 - z} \\
	& = 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 $z = 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 $\$40,000$ per year for 50 years?
Plugging in $m = \$40,000$, $n = 50$, and $p = 0.035$ gives $V \approx
\$971,063$.  You'd be better off taking the million dollars today!

\subsection{Infinite Sums}

All right, would you prefer a million dollars today or \$40,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 = \$40,000$ and $p = 0.035$ into this formula gives $V
\approx \$1,182,857$.  The value of money drops off so fast that even
an \textit{infinite} number of payments are worth on a bit over a
million dollars.  In fact, the total value of all payments beyond the
50th is only about \$200,000!

\iffalse
Thinking about this another way helps understand this result:
If you had a million dollars in the bank earning $3.5\%$ interest,
then you could take out and spend \$35,000 year forever.
\fi

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-1} z^i \\
    & = \lim_{n \to \infty} \frac{1 - z^n}{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.


\iffalse
\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)$.
\fi

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

\section{Sums of Powers}

Pharaoh Aha I decides to build a ``pyramid'' in his own honor
consisting of a single block:
%
\begin{center}
\includegraphics[height=0.5in]{aha1}
\end{center}
%
His successor, Aha II, trumps him by building a larger pyramid:
%
\begin{center}
\includegraphics[height=1in]{aha2}
\end{center}
%
Not to be outdone, Aha III builds a still-larger pyramid:
%
\begin{center}
\includegraphics[height=1.5in]{aha3}
\end{center}
%
If this madness continues, how many blocks will Pharoah Aha $n$
require?  Let's break the problem down by chopping the $n$-th pyramid
into $n$ horizontal slabs:
%
\begin{center}
\includegraphics{slabs}
\end{center}
%
Therefore, we have:
%
\[
\text{\# blocks in $n$-th pyramid}
    = \sum_{k=1}^n \text{\# blocks in $k$-th slab}
\]
%
Similarly, we can slice each slab into columns:
%
\begin{center}
\includegraphics{columns}
\end{center}
%
So the number of blocks in the $k$-th slab is:
%
\[
1 + 3 + 5 + \ldots + (2k-1) + \ldots + 5 + 3 + 1 = (2k-1) + 2 \cdot \sum_{j=1}^{k-1} 2j-1
\]
%
Plugging this into the previous sum gives the total number of blocks
required by Pharaoh Aha-$n$:
%
\[
\text{\# blocks in $n$-th pyramid}
    = \sum_{k=1}^n \paren{(2k-1) + 2 \cdot \sum_{j=1}^{k-1} 2j-1}
\]
%
This sum is pretty nasty.  And the bad news is that similar sums arise
when analyzing the running time of a program with nested loops.

\subsection{Evaluating the Sum}

Sums of small powers are actually easy to handle, because there are
simple closed-form equivalents:
%
\begin{lemma}[Sums of Powers]
\label{lem:sums-of-powers}
\begin{align*}
1 + 2 + 3 + \ldots + m & = \frac{m(m+1)}{2} \\
1^2 + 2^2 + 3^2 + \ldots + m^2 & = \frac{m(m+\frac{1}{2})(m+1)}{3} \\
1^3 + 2^3 + 3^3 + \ldots + m^3 & = \frac{m^2(m+1)^2}{4}
\end{align*}
\end{lemma}
%
These formulas can all be proved by routine induction arguments.  For
now, let's apply them to to find a closed-form expression for the
number of blocks in a pyramid.  First, let's tackle the inner sum:
%
\begin{align*}
\sum_{j=1}^{k-1} 2j-1
    & = 2 \paren{\sum_{j=1}^{k-1} j} - \paren{\sum_{j=1}^{k-1}} 1 \\
    & = 2 \cdot \frac{(k-1)k}{2} - (k-1) \\
    & = (k-1)^2
\end{align*}
%
On the first line, we're using a standard maneuver: \textit{break up
the sum of a polynomial into one sum for each term}.  In this case, we
break the sum of $2j - 1$ into one sum involving $j$ and one sum for
the constant.  This allows us to apply the standard formulas above,
and the rest is simplification.  We'll use the same trick to finish
off the whole pyramid problem, though now we have to sum values of a
quadratic polynomial:
%
\begin{align*}
\text{\# blocks in $n$-th pyramid}
  & = \sum_{k=1}^n \paren{(2k-1) + 2 \cdot \sum_{j=1}^{k-1} 2j-1} \\
  & = \sum_{k=1}^n (2k-1) + 2 (k-1)^2 \\
  & = \sum_{k=1}^n 2k^2 - 2k + 1 \\
  & = 2 \sum_{k=1}^n k^2 - 2 \sum_{k=1}^n k + \sum_{k=1}^n 1 \\
  & = 2 \cdot \frac{n (n+\frac{1}{2})(n+1)}{3} - 2 \cdot \frac{n (n+1)}{2} + n \\
  & = \frac{2n^3+n}{3}
\end{align*}
%
%
We're done!  But let's check a couple easy cases to make sure we made
no algebra mistakes.  This formula says that a pyramid of size 1
contains $(2 \cdot 1^3 + 1) / 3 = 1$ block and a pyramid of size 2
contains $(2 \cdot 2^3 + 2) / 3 = 6$ blocks--- both of which are
correct.

\subsection{Where Do the Formulas Come From?}

Sure, we can prove all the summation formulas in
Lemma~\ref{lem:sums-of-powers} by induction, but where did the
expressions on the right come from?  How on earth would we even guess
an analogous summation formula for, say, fourth powers?

Here is systematic way to generate a good guess.  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.  Based on this observation, we might guess that
%
\[
\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$, so it is tempting
to conclude that:
%
\begin{align*}
\sum_{i=1}^n i^2
    & = \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6} \\
    & = \frac{n(n+\frac{1}{2})(n+1)}{3}
\end{align*}
%
\textit{But 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 this equation might not hold for any $n$ other than 0, 1,
2, and 3!  So be sure to verify that such guesses are correct by
giving an induction proof.

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

\section{Approximating Functions}

When you ask about the weather, you probably want to hear something
like ``hot'', ``cold'', or ``raining'', not a lengthly discourse on
convection currents, radiative heat transfer, and dew points.
Something similar is true about the analysis of computer algorithms
and systems: a simple, approximate answer is often more useful than an
exact, complicated answer.  So techniques for replacing complicated
expressions with simple approximations can be extremely useful.

\subsection{Taylor's Theorem}

A wonderful way to get approximations is to dredge up Taylor's Theorem
from the dark, murky regions of calculus.  Unfortuantely, the theorem
\textit{looks} like something dredged from a dark, murky place.  So
let's start with some intuition.

Suppose we want a simple approximation for the function $\ln(1 + x)$
that is fairly accurate when $x$ is a small number.  Here's what the
function actually looks like:
%
\begin{center}
\unitlength=1in
\begin{picture}(4,2)(-0.25,-0.25)
%\put(-0.25,-0.25){\framebox(4,2){}} % bounding box
\put(0,0){\vector(1,0){3.5}}
\put(0,0){\vector(0,1){1.75}}
\thicklines
\qbezier(0.000000,0.000000)(0.216395,0.216395)(0.500000,0.405465)
\qbezier(0.500000,0.405465)(0.726092,0.556193)(1.000000,0.693147)
\qbezier(1.000000,0.693147)(1.231436,0.808865)(1.500000,0.916291)
\qbezier(1.500000,0.916291)(1.734823,1.010220)(2.000000,1.098612)
\qbezier(2.000000,1.098612)(2.237164,1.177667)(2.500000,1.252763)
\qbezier(2.500000,1.252763)(2.738879,1.321014)(3.000000,1.386294)
\qbezier(3.000000,1.386294)(3.240189,1.446342)(3.500000,1.504077)
\put(3,1.15){\makebox(0,0){$y = \ln(1 + x$)}}
\put(0,-0.15){\makebox(0,0){$0$}}
\put(1,-0.15){\makebox(0,0){$1$}}
\put(2,-0.15){\makebox(0,0){$2$}}
\put(3,-0.15){\makebox(0,0){$3$}}
\put(-0.15,0){\makebox(0,0){$0$}}
\put(-0.15,0.5){\makebox(0,0){$0.5$}}
\put(-0.15,1){\makebox(0,0){$1$}}
\put(-0.15,1.5){\makebox(0,0){$1.5$}}
\end{picture}
\end{center}

The curve goes through the origin, so a trivial approximation is
$\ln(1 + x) \approx 0$ when $x$ is small.  In general:
%
\[
f(x) \approx f(0) \quad \text{when $x$ is small}
\]
%
Sometimes this crude approximation is good enough, but not often.

A line tangent to the curve at $x = 0$ provides a better
approximation.  The slope of the tangent is given by the derivative
%
\[
\frac{d}{dx}\ \ln(1 + x) = \frac{1}{1 + x}
\]
%
evaluated at $x = 0$, which is $1 / (1 + 0) = 1$.  This gives the
approximation $\ln(1 + x) \approx x$, which is a significant
improvement:
%
\begin{center}
\unitlength=1in
\begin{picture}(4,2)(-0.25,-0.25)
%\put(-0.25,-0.25){\framebox(4,2){}} % bounding box
\put(0,0){\vector(1,0){3.5}}
\put(0,0){\vector(0,1){1.75}}
\qbezier(0.000000,0.000000)(0.216395,0.216395)(0.500000,0.405465)
\qbezier(0.500000,0.405465)(0.726092,0.556193)(1.000000,0.693147)
\qbezier(1.000000,0.693147)(1.231436,0.808865)(1.500000,0.916291)
\qbezier(1.500000,0.916291)(1.734823,1.010220)(2.000000,1.098612)
\qbezier(2.000000,1.098612)(2.237164,1.177667)(2.500000,1.252763)
\qbezier(2.500000,1.252763)(2.738879,1.321014)(3.000000,1.386294)
\qbezier(3.000000,1.386294)(3.240189,1.446342)(3.500000,1.504077)
\put(3,1.15){\makebox(0,0){$y = \ln(1 + x$)}}
\thicklines
\qbezier(0,0)(0.25,0.25)(0.5,0.5)
\qbezier(0.5,0.5)(0.75,0.75)(1,1)
\qbezier(1,1)(1.25,1.25)(1.5,1.5)
\put(1.8,1.5){\makebox(0,0){$y=x$}}
\put(0,-0.15){\makebox(0,0){$0$}}
\put(1,-0.15){\makebox(0,0){$1$}}
\put(2,-0.15){\makebox(0,0){$2$}}
\put(3,-0.15){\makebox(0,0){$3$}}
\put(-0.15,0){\makebox(0,0){$0$}}
\put(-0.15,0.5){\makebox(0,0){$0.5$}}
\put(-0.15,1){\makebox(0,0){$1$}}
\put(-0.15,1.5){\makebox(0,0){$1.5$}}
\end{picture}
\end{center}
%
In general:
%
\[
f(x) \approx f(0) + x f'(0) \quad \text{when $x$ is small}
\]
%
This approximation is accurate enough in many situations.  This is
great, because linear functions are very simple and easy to
manipulate.

This linear approximation has both the correct value at $x = 0$ and
the correct first derivative.  We can go one more step and get an
approximation with the correct second derivative:
%
\[
f(x) \approx f(0) + x f'(0) + \frac{x^2}{2} f''(0) \quad \text{when $x$ is small}
\]
%
In our example, where $f(x) = \ln(1 + x)$, we have $f''(x) = - 1 / (1
+ x)^2$, which means $f''(0) = - 1$.  This gives the quadratic
approximation $\ln(1 + x) \approx x - x^2/2$.  Lets add this
to our plot:
%
\begin{center}
\unitlength=1in
\begin{picture}(4,2)(-0.25,-0.25)
%\put(-0.25,-0.25){\framebox(4,2){}} % bounding box
\put(0,0){\vector(1,0){3.5}}
\put(0,0){\vector(0,1){1.75}}
\qbezier(0.000000,0.000000)(0.216395,0.216395)(0.500000,0.405465)
\qbezier(0.500000,0.405465)(0.726092,0.556193)(1.000000,0.693147)
\qbezier(1.000000,0.693147)(1.231436,0.808865)(1.500000,0.916291)
\qbezier(1.500000,0.916291)(1.734823,1.010220)(2.000000,1.098612)
\qbezier(2.000000,1.098612)(2.237164,1.177667)(2.500000,1.252763)
\qbezier(2.500000,1.252763)(2.738879,1.321014)(3.000000,1.386294)
\qbezier(3.000000,1.386294)(3.240189,1.446342)(3.500000,1.504077)
\put(3,1.15){\makebox(0,0){$y = \ln(1 + x$)}}
\qbezier(0,0)(0.25,0.25)(0.5,0.5)
\qbezier(0.5,0.5)(0.75,0.75)(1,1)
\qbezier(1,1)(1.25,1.25)(1.5,1.5)
\put(1.8,1.5){\makebox(0,0){$y=x$}}
\put(0,-0.15){\makebox(0,0){$0$}}
\put(1,-0.15){\makebox(0,0){$1$}}
\put(2,-0.15){\makebox(0,0){$2$}}
\put(3,-0.15){\makebox(0,0){$3$}}
\put(-0.15,0){\makebox(0,0){$0$}}
\put(-0.15,0.5){\makebox(0,0){$0.5$}}
\put(-0.15,1){\makebox(0,0){$1$}}
\put(-0.15,1.5){\makebox(0,0){$1.5$}}
\thicklines
\qbezier(0.000000,0.000000)(0.250000,0.250000)(0.500000,0.375000)
\qbezier(0.500000,0.375000)(0.750000,0.500000)(1.000000,0.500000)
\qbezier(1.000000,0.500000)(1.250000,0.500000)(1.500000,0.375000)
\qbezier(1.500000,0.375000)(1.750000,0.250000)(2.000000,0.000000)
\put(2.5,0.25){\makebox(0,0){$y = x - x^2/2$}}
\end{picture}
\end{center}

Taylor's Theorem says that one can continue in this way, getting
progressively better approximations by incorporating higher-order
derivatives.

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

The final term describes the ``error'' in an $n$-term Taylor
approximation; we'll return to that later.  Here are the leading terms
in the Taylor series for some functions that often arise:
%
\begin{align*}
e^x & = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \ldots \\
\ln(1 + x) & = x - \frac{x^2}{2} + \frac{x^3}{3}
                 - \frac{x^4}{4} + \frac{x^5}{5} - \ldots \\
\sqrt{1 + x} & = 1 + \frac{x}{2} - \frac{x^2}{8}
                   + \frac{x^3}{16} - \frac{5x^4}{128} + \ldots 
\end{align*}

\subsection{Rule of 72}

Suppose you want to double your money in $n$ years.  What annual rate
of return would you need?  Here are the answers for various numbers of
years:
%
\[
\begin{array}{c@{\hspace{0.25in}}c}
\text{$n$ = \# of Years} & \text{Rate Needed to Double Money} \\ \hline
\\
4 & 18.9\% \\
6 & 12.2\% \\
8 & 9.0\% \\
12 & 6.0\% \\
24 & 2.9\% \\
36 & 1.9\%
\end{array}
\]
%
There's a curious pattern here: the product of the numbers on each
line is always around 70 or 72 or so.

This observation is the basis for an old investing rule that says you
can double your money by investing it for $n$ years at $72 / n$
percent interest.  For example, you could double your money by
investing it for 24 years at $72 / 24 = 3$ percent interest.  This
rule isn't exactly right, but it's almost mysteriously close.  For
example, a dollar invested for 24 years at 3\% becomes \$2.03.

In general, a dollar invested for $n$ years at $72 / n$ percent
interest becomes
%
\[
m = \left(1 +  \frac{72 / n}{100}\right)^n
\]
%
dollars.  This complicated expression doesn't look much like the
number 2, but let's try an approximation.  One standard trick when the
relevant variable ($n$ in this case) appears in the exponent is to
analyze the \textit{logarithm} of the expression.
%
\begin{align*}
\ln m & = \ln \left(1 +  \frac{72 / n}{100}\right)^n \\
      & = n \ln \left(1 + \frac{72}{100n}\right)
\end{align*}
%
Here we're taking a logarithm of 1 plus something small ($72/100n$),
so we can use the approximation $\ln(1 + x) \approx x - x^2 / 2$.
%
\begin{align*}
\ln m & \approx n \paren{\frac{72}{100n} - \frac{72^2}{2 \cdot 100^2 n^2}} \\
      & = \frac{72}{100} - \frac{162}{625n}
\end{align*}
%
Now let's exponentiate to undo the earlier logarithm:
%
\[
m \approx e^{72/100 - 162/(625n)}
\]
%
This explains the Rule of 72: if you invest a dollar for $n$ years at
$72 / n$ percent interest, then the value of your dollar approaches
$e^{72/100} = 2.05443$ dollars from below as $n$ goes to infinity.  So
the Rule overestimates your return for small $n$, slightly
underestimates for large $n$, and is fairly accurate for typical
values of $n$.  A ``Rule for 71'' might be even more accurate, but 72
has lots of convenient divisors, while 71 is inconveniently prime.

\subsection{Upper and Lower Bounds}

Sometime an upper or lower bound on a function is needed instead of a
simple approximation.  For example, if you're computing the
probability that a critical system fails, an upper bound would give
you a reassuring, conservative answer.  We can get good upper and
lower bounds on many functions by looking at the error term in
Taylor's Theorem.

Taylor's Theorem with one ordinary term and the error term says:
%
\[
f(x) = f(0) + x f(z) \quad \text{for some $z \in [0,x]$}
\]
%
This is actually an equation, not an approximation.  The problem is
that we don't know the value of $z$ in the error term.  However, we do
have some bounds on $z$, and those bounds imply upper and lower bounds
on the function $f(x)$.

For example, suppose $f(x) = \ln(1 + x)$.  Then Taylor's Theorem says:
%
\[
\ln(1 + x) = 0 + x \cdot \frac{1}{1 + z} = \frac{x}{1 + z}
\]
%
for some $z \in [0,x]$.  If we assume $x$ is positive, then the
expression on the right is \textit{maximized} when $z = 0$ and
\textit{minimized} when $z = x$.  Therefore, we have the bounds:
%
\[
\frac{x}{1 + x} \leq \ln(1 + x) \leq x
\]
%
The upper bound is the same as the linear Taylor approximation.  Let's
add the lower bound to our plot:
%
\begin{center}
\unitlength=1in
\begin{picture}(4,2)(-0.25,-0.25)
%\put(-0.25,-0.25){\framebox(4,2){}} % bounding box
\put(0,0){\vector(1,0){3.5}}
\put(0,0){\vector(0,1){1.75}}
\qbezier(0.000000,0.000000)(0.216395,0.216395)(0.500000,0.405465)
\qbezier(0.500000,0.405465)(0.726092,0.556193)(1.000000,0.693147)
\qbezier(1.000000,0.693147)(1.231436,0.808865)(1.500000,0.916291)
\qbezier(1.500000,0.916291)(1.734823,1.010220)(2.000000,1.098612)
\qbezier(2.000000,1.098612)(2.237164,1.177667)(2.500000,1.252763)
\qbezier(2.500000,1.252763)(2.738879,1.321014)(3.000000,1.386294)
\qbezier(3.000000,1.386294)(3.240189,1.446342)(3.500000,1.504077)
\put(3,1.15){\makebox(0,0){$y = \ln(1 + x$)}}
\qbezier(0,0)(0.25,0.25)(0.5,0.5)
\qbezier(0.5,0.5)(0.75,0.75)(1,1)
\qbezier(1,1)(1.25,1.25)(1.5,1.5)
\put(1.8,1.5){\makebox(0,0){$y=x$}}
\put(0,-0.15){\makebox(0,0){$0$}}
\put(1,-0.15){\makebox(0,0){$1$}}
\put(2,-0.15){\makebox(0,0){$2$}}
\put(3,-0.15){\makebox(0,0){$3$}}
\put(-0.15,0){\makebox(0,0){$0$}}
\put(-0.15,0.5){\makebox(0,0){$0.5$}}
\put(-0.15,1){\makebox(0,0){$1$}}
\put(-0.15,1.5){\makebox(0,0){$1.5$}}
\qbezier(0.000000,0.000000)(0.250000,0.250000)(0.500000,0.375000)
\qbezier(0.500000,0.375000)(0.750000,0.500000)(1.000000,0.500000)
\qbezier(1.000000,0.500000)(1.250000,0.500000)(1.500000,0.375000)
\qbezier(1.500000,0.375000)(1.750000,0.250000)(2.000000,0.000000)
\put(2.5,0.25){\makebox(0,0){$y = x - x^2/2$}}
%
\thicklines
\qbezier(0.000000,0.000000)(0.200000,0.200000)(0.500000,0.333333)
\qbezier(0.500000,0.333333)(0.714286,0.428571)(1.000000,0.500000)
\qbezier(1.000000,0.500000)(1.222222,0.555556)(1.500000,0.600000)
\qbezier(1.500000,0.600000)(1.727273,0.636364)(2.000000,0.666667)
\qbezier(2.000000,0.666667)(2.230769,0.692308)(2.500000,0.714286)
\qbezier(2.500000,0.714286)(2.733333,0.733333)(3.000000,0.750000)
%\qbezier(3.000000,0.750000)(3.235294,0.764706)(3.500000,0.777778)
\put(3.6,0.75){\makebox(0,0){$y = x / (1 + x)$}}
%
\end{picture}
\end{center}
%
This lower bound is fairly accurate for small $x$.  However, for large
$x$, the lower bound $x / (1 + x)$ asymptotically approaches 1 while
the actual function $\ln(1 + x)$ diverges to infinity.

\subsection{Approximating $1 + x$}

We can get upper and lower bounds on the function $1 + x$ by
exponentiating our bounds on $\ln(1 + x)$:
%
\[
e^{x/(1+x)} \leq 1 + x \leq e^x
\]
%
What a profoundly stupid thing to do!  The function $1 + x$ is
\textit{really simple}, while the function $e^{x/(1+x)}$ is
\textit{complicated}.  Why would one ever want to bound a simple
function with a complicated function?  Why not just work with the
original, simple function?

The reason is that $x$ appears at ``ground level'' in the function $1
+ x$, but ``upstairs'' in the functions $e^x$ and $e^{x/(1+x)}$.  This
difference allows one to switch back and forth between sums and
products.  As a result, $1 + x \approx e^x$ is probably the most
widely-used approximation in computer science!

For example, let's take the nasty product that we tried to scare you
with earlier:
%
\[
\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}}
\]
%
Our upper bound on $1 + x$ gives:
%
\begin{align*}
\paren{1 + \frac{1}{n^2}}
\paren{1 + \frac{2}{n^2}}
\cdots
\paren{1 + \frac{n}{n^2}}
  & \leq e^{1/n^2} \cdot e^{2/n^2} \cdots e^{n/n^2} \\
  & = e^{(1 + 2 + \ldots + n)/n^2} \\
  & = e^{n(n+1)/2n^2} \\
  & = \sqrt{e} \cdot e^{1/2n}
\end{align*}
%
The second line follows from the rule $e^A \cdot e^B = e^{A+B}$.
We've now translated the nasty product into an easy sum in the
exponent!  The rest is simplification.  Note that $e^{1/2n}$ is very
close to 1 when $n$ is large.

Similarly, the lower bound on $1 + x$ gives:
%
\begin{align*}
\paren{1 + \frac{1}{n^2}}
\paren{1 + \frac{2}{n^2}}
\cdots
\paren{1 + \frac{n}{n^2}}
  & \geq e^\frac{1/n^2}{1+1/n^2} \cdot
         e^\frac{2/n^2}{1+2/n^2} \cdots
         e^\frac{n/n^2}{1+n/n^2} \\
  & = e^{\textstyle \frac{1}{n^2+1} +
                    \frac{2}{n^2+2} + \ldots +
                    \frac{n}{n^2+n}}
\end{align*}
%
This sum is outside our repetoire.  But we can get a lower bound by
making some of the denominators a little bigger.  In particular, if we
make all the denominators as big as the largest one, then we have:
%
\begin{align*}
\paren{1 + \frac{1}{n^2}}
\paren{1 + \frac{2}{n^2}}
\cdots
\paren{1 + \frac{n}{n^2}}
  & \geq e^{\textstyle \frac{1}{n^2+n} +
                      \frac{2}{n^2+n} + \ldots +
                      \frac{n}{n^2+n}} \\
  & = e^{(1 + 2 + \ldots + n)/n(n+1)} \\
  & = \sqrt{e}
\end{align*}
%
So the very scary product rapidly descends to nothing more than
$\sqrt{e}$.

\subsection{A Large-$x$ Approximation}

So far, we've focused on the problem of approximating a function
$f(x)$ when $x$ is small.  But what if we need to approximate a
function $f(x)$ when $x$ is \textit{large}?

Here's a simple trick that often works.  As an example, let's take our
old friend $f(x) = \ln(1 + x)$.  When $x$ is a big number, there is
little difference between $\ln x$ and $\ln(1 + x)$.  So let's first
write $\ln(1 + x)$ in terms of $\ln x$:
%
\begin{align*}
\ln(1 + x)
  & = \ln\paren{x \cdot \paren{1 + \frac{1}{x}}} \\
  & = \ln x + \ln\paren{1 + \frac{1}{x}} \\
\end{align*}
%
The general idea is to express $f(x)$ in terms of a fairly similar
function and then use Taylor's Theorem just to analyze the leftover
bit, which is $\ln(1 + 1/x)$ in this case.  Notice that when $x$ is
large, $1/x$ is small.  So our earlier methods should now give
excellent results.  Specifically, suppose we set $z = 1 / x$ and use
the bounds that we derived earlier:
%
\[
\frac{z}{1 + z} \leq \ln(1 + z) \leq z
\]
%
Then we get the upper bound
%
\begin{align*}
\ln(1 + x) & \leq \ln x + \frac{1}{x}
\end{align*}
%
and the lower bound:
%
\begin{align*}
\ln(1 + x)
  & \geq \ln x + \frac{1/x}{1+1/x} \\
  & \geq \ln x + \frac{1}{x+1}
\end{align*}

For example, suppose we wanted to evaluate $\ln(e^{10} + 1)$.  Then
these bounds say:
%
\[
10 + \frac{1}{e^{10}+1} \leq \ln(e^{10} + 1) \leq 10 + \frac{1}{e^{10}}
\]
%
The difference between the upper and lower bounds is only about
$e^{-20}$.  Not bad!
\end{document}
