\documentclass[11pt,twoside]{article}
\usepackage{macros-course-lectures}
\usepackage{graphics}

\textwidth=6.5in
%\topmargin=-.15in
%\evensidemargin=0.75in
%\oddsidemargin=0.7pt
%\newcommand {\pindent} {\hspace*{20pt}}
\textheight=9.5in
\parskip=12pt plus 2pt minus 2pt
\pagestyle{empty}
\setlength{\parindent}{0in}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\newcommand{\pagetitle}[1]{\newpage {\bf #1} \hfill
L11$-$P. \thepage \\ \vspace{-0.5cm} \hrule \vspace{12mm}}
\newcommand{\doublespace}{\addtolength{\baselineskip}{.35\baselineskip}}
%\newcommand{\remove}[1]{}

\begin{document}

\renewcommand{\thepage}{\arabic{page}}


\Huge
\pagetitle{Lecture Overview}
Series and Summations\\
\\
Examples:\\

\hspace{1cm} Annuities\\

\hspace{1cm} Book Stacking\\

\pagetitle{Evaluating Sums}

Important for algorithms and systems\\
\\
We would like to have {\it closed form}\\
\\
At least approximate its value well enough\\


\pagetitle{Annuities}

Would you prefer a million dollars today or \$50,000 a year for the
rest of your life?

An $n$-year, $m$-payment annuity pays
$m$ dollars at the start of each year for $n$ years.

We estimate the fixed annual interest rate $p$ around 8\%

Ten dollars will be\\
$(1+p) = \$10.80$ in a year,\\
$(1+p)^2 \approx \$11.66$ in two years,\\
and so forth.

Looked at another way, ten
dollars paid out a year from now are only really worth $1/(1+p)
\approx \$9.26$ today.  

The reason is that if we had the $\$9.26$ today, we
could invest it and would have $\$10.00$ in a year anyway.  

Therefore,
$~p~$ determines the value of money paid out in the future.

\pagetitle{The Value of an Annuity}

First payment of $m$ dollars is truly worth $m$ dollars.

Second payment a year later is worth only\\
$m/(1+p)$,

Third payment is worth $m/(1+p)^2$,

$n$-th payment is only $m/(1+p)^{n-1}$,

The total value $V$ is: 

\hspace{2cm} $V = \sum_{i=1}^n \frac{m}{(1+p)^{i-1}}$

\pagetitle{The Value of an Annuity}
``Closed form'' mathematical expression without any summation or product.

Summation of a {\em geometric series} is:

{\bf Theorem:} For all $n \geq 1$ and all $x \neq 0$,\\
$\sum_{i=0}^{n-1} x^i = \frac{1- x^n}{1 - x}$.

We have:

\vspace{-1cm}
\begin{eqnarray*}
V & = & \sum_{i=1}^n \frac{m}{(1+p)^{i-1}} \\
  & = & \sum_{j=0}^{n-1} \frac{m}{(1+p)^j} \quad (\mbox{substitute} \ j = i-1)\\  & = & m \sum_{j=0}^{n-1} x^j \quad (\mbox{substitute} \ x = \frac{1}{1+p})
\end{eqnarray*}
Thus we have $\frac{m- m x^n}{1 - x}$ where $x$ is $\frac{1}{1+p}$.

So for $m=$\$50,000, $n=$20, and $p=0.8$ we have
$V \approx \$530,180$.  Better have \$550,000 now!

\pagetitle{The Sum of a Geometric Series}

So we need to prove the {\bf Theorem:}\\
$\forall n \geq 1$ and all $\forall x \neq 0$,
$\sum_{i=0}^{n-1} x^i = \frac{1- x^n}{1 - x}.$

We prove by induction on $n$.\\
$P(n)$ $\forall x \neq 1$ $\sum_{i=0}^{n-1} x^i = \frac{1 - x^n}{1 - x}$.

Base: $P(1)$ holds, since\\
$\sum_{i=0}^{0} x^i = x^0 = 1$ and $\frac{1 - x^1}{1 - x} = 1$.

Step:\\
Assume $\forall x \neq 1$, $\sum_{i=0}^{n-1} x^i = \frac{1 - x^n}{1 - x}$,
and prove $\forall x \neq 1$, $\sum_{i=0}^{n} x^i = \frac{1 -
x^{n+1}}{1 - x}$.

\begin{eqnarray*}
\sum_{i=0}^{n} x^i & = & x^n + \sum_{i=0}^{n-1} x^i \\
                   & = & x^n + \frac{1 - x^n}{1 - x} \\
                   & = & \frac{x^n (1-x) + 1 - x^n}{1 - x} \\
                   & = & \frac{1 - x^{n+1}}{1 - x} 
\end{eqnarray*}

\pagetitle{The Sum of a Geometric Series}

How the formula was found??

The trick is to let $S$ be the value of the sum:

\begin{eqnarray*}
S & = & 1 + x + x^2 + \ldots + x^{n-1} \\
-xS & = & -x - x^2 - x^3 - \ldots - x^n
\end{eqnarray*}

Adding these two equations gives:

\begin{eqnarray*}
(1-x)S & = & 1 - x^n \\
S & = & \frac{1 - x^n}{1 - x}
\end{eqnarray*}

\pagetitle{Infinite Geometric Series}

Assume you will live forever ... \\
(always in a good shape of course)

Would you prefer a million dollars today or \$50,000 a year?
(Yes! infinite money)

The limit of our geometric sum as $n$ tends to infinity is

{\bf Theorem} If $|x| < 1$, then $\sum_{i=0}^\infty x^i = \frac{1}{1-x}.$

\begin{eqnarray*}
\sum_{i=0}^\infty x^i & = & \lim_{n \rightarrow \infty} \sum_{i=0}^{n-1} x^i \\
                      & = & \lim_{n \rightarrow \infty} \frac{1 - x^n}{1-x} \\
                      & = & \frac{1}{1-x}
\end{eqnarray*}

Note that in evaluating the limit the $x^n$ term vanishes \\
since we assumed that $|x| < 1$.

\pagetitle{Infinite Geometric Series}

$x=1/(1+p) < 1$, so the theorem applies.\\
Substituting for $x$, we get an annuity value of 
\begin{align*}      
V &= m\cdot\frac{1}{1-x} \\
&= m\cdot \frac{1}{1-1/(1+p)}\\
&= m\cdot \frac{1+p}{(1+p)-1}\\
&= m\cdot \frac{1 + p}{p} 
\end{align*}              

Plugging in $m = \$50,000$ and $p = 0.8$ gives only $V=\$675,000$. \\
Amazingly, a million dollars today is worth much more than $\$50,000$
paid every year forever!  

Because with a million dollars
today in the bank earning 8\% interest,\\
We could spend $\$80,000$ a year forever.  

\pagetitle{Sums of Decreasing\\ Geometric Series}
\begin{eqnarray*}
1 + 1/2 + 1/4 + 1/8 + \ldots & = & \sum_{i=0}^\infty (1/2)^i \\
                             & = & \frac{1}{1-(1/2)} \\
                             & = & 2 \\
0.999999999\ldots             &= & 0.9\sum_{i=0}^{\infty} (1/10)^i\\
                             &= & 0.9\frac{1}{1-1/10}\\
                             &= & 0.9\frac{10}{9}\\
                             &= & 1\\
1 - 1/2 + 1/4 - 1/8 + \ldots & = & \sum_{i=0}^\infty (-1/2)^i \\
                             & = & \frac{1}{1-(-1/2)} \\
                             & = & 2/3 \\
\end{eqnarray*}

\pagetitle{Sums of Increasing\\ Geometric Series}
\begin{eqnarray*}
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{eqnarray*}

Rule of thumb: approximately equal to the greatest term value

\pagetitle{Related Sums}

there are cases in which we need to work harder...

$\sum_{i=1}^n i x^i = x + 2 x^2 + 3 x^3 + \ldots + n x^n$

$\frac{d}{dx} \ \sum_{i=0}^{n} x^i
  =  \frac{d}{dx} \ \frac{1 - x^{n+1}}{1 - x}$

$\sum_{i=0}^{n} i x^{i-1} = \frac{-(n+1)x^n (1-x) - (-1)(1-x^{n+1})}{(1 - x)^2}$ \\
$~~~~~~~~~~~~~~~~~ = \frac{-(n+1)x^n + (n+1)x^{n+1} + 1 - x^{n+1}}{(1 - x)^2}$ \\
$~~~~~~~~~~~~~~~~~ =  \frac{1 - (n+1)x^n + n x^{n+1}}{(1 - x)^2}$\\


Now we multiply be $x$ to have:

$\sum_{i=0}^{n} i x^i = \frac{x - (n+1)x^{n+1} + n x^{n+2}}{(1 - x)^2}$

Good practice to verify by induction, at least examples...

In case $n=\infty$, we may conclude:

Theorem: If $|x| < 1$, then
$\sum_{i=0}^\infty i x^i = \frac{x}{(1-x)^2}$.

\pagetitle{Book Stacking Example}

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/stack.eps,height=2.5in}}
\end{figure}

If $n$ books are stacked on a table,\\
how far can the top book overhang the edge\\
without the whole stack falling over?


\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/dstack.eps,height=2.5in}}
\end{figure}

Book length = 2, book mass identical.\\
$1 \leq i \leq n$, $d_i$ is the distance
that book $0$ extends beyond the right end of book $i$.  \\
The table is regarded as book $n+1$

\pagetitle{Book Stacking Example}
A stack of books is {\em stable} iff for $1 \leq k \leq n$,\\
the center of mass for the top $k$ books lies above
the $(k+1)$-st book.\\

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/stable.eps,height=2.5in}}
\end{figure}

Greedy strategy:\\
The book 1 as far as possible on the book 2\\
The two top books as far as possible on book 3\\
And so on...\\

\pagetitle{Book Stacking Example}

$d_k$ is the center of the mass of the top $k$ books\\

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/stable.eps,height=2.5in}}
\end{figure}

The center of mass of book $i$ is at distance $d_i+1$ to the left
of the top book.

The center of mass of the top $k$ books ($0,\ldots,k-1)$
is the average of this values:

$\frac{(d_{k-1}+1)+(d_{k-2}+1)+\cdots+(d_0+1)}{k}$

By our greedy choice:\\
$d_{k} =\frac{(d_{k-1}+1)+(d_{k-2}+1)+\cdots+(d_0+1)}{k}$\\

Or: $kd_{k} =d_{k-1}+d_{k-2}+\cdots+d_0 + k$ \\

\pagetitle{Book Stacking Example}

Now algebra:\\
$(k-1)d_{k-1} =d_{k-2}+d_{k-3}+\cdots+d_0 + k-1$

Substraction of the above formulas:\\
$kd_k-(k-1)d_{k-1} =d_{k-1}+1$\\
or, $d_k = d_{k-1}+1/k$\\
$d_k=d_{k-2}+1/(k-1)+1/k$\\
...\\
$d_k=1+1/2+\cdots+1/(k-1)+1/k$

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/optstack.eps,height=2.5in}}
\end{figure}

We cannot do better since we mast have the centers located such that

$d_{k} \le \frac{(d_{k-1}+1)+(d_{k-2}+1)+\cdots+(d_0+1)}{k}$

using induction we can prove that $d_k$ is largest possible.

\pagetitle{Evaluating the Sum ---\\ The Integral Method}

{\em $n$-th Harmonic number} $H_n$ is:\\
$\sum_{i=1}^n \frac{1}{i}$ 

$H_1=1$, $H_2=1+\frac{1}{2} = \frac{3}{2}$, $H_3 = 1 + \frac{1}{2} +
\frac{1}{3} = \frac{11}{16}$, $H_4 = 1 + \frac{1}{2} + \frac{1}{3} +
\frac{1}{4} = \frac{25}{12}$.  

$H_4 > 2$ thus --- the total extension of a 4-book
stack is greater than one full book! 

What about extension of 100 books?\\
Look for $H_l \geq 200$,\\
Can we have a ``closed form''?\\
No close form is known

\pagetitle{Evaluating the Sum ---\\ The Integral Method}

\begin{figure}[htbp]
\centerline{\psfig{figure=/a/class/6.042/spring00/archive/lectures/figures/integral.eps,height=2.5in}}
\end{figure}

The area under the ``stairstep'' curve over the interval
$[0, n]$ is equal to $H_n = \sum_{i=1}^n 1/i$.  

$1/x$ $\geq$ the stairstep function\\
$1/(x+1)$ $\leq$ the stairstep function\\

\noindent
$H_n \leq  1 + \int_1^n \frac{1}{x} \ dx = 1 + \ln n$ \\
$H_n \geq  \int_0^n \frac{1}{x+1} \ dx = \int_1^{n+1} \frac{1}{x} \ dx = \ln(n+1)$

We need approximately $e^200$ books, which is a 86 digits number!.

\pagetitle{Harmonic Numbers, Cont.}

Better approximation ---

$H_n = \ln n + \gamma + \frac{1}{2n} + \frac{1}{12n^2} +
        \frac{\epsilon(n)}{120n^4}$

$\gamma = 0.577215664\ldots$ called Euler's constant\\
$\epsilon(n)$ is between 0 and 1 for all $n$.  

Shorthand $H_n \sim \ln n$ indicates that the leading
term of $H_n$ is $\ln n$.

$f(n) \sim g(n)$ means that $\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}
\rightarrow 1$.

$\sim$ notation is useful when we do not
care about lower order terms.  

For example, if $n = 100$, then we can
compute $H(n)$ to great precision using only the two leading terms:

$|H_n - \ln n - \gamma| \leq | \frac{1}{200} - \frac{1}{120000} +
\frac{1}{120 \cdot 100^4} | < \frac{1}{200}$


\end{document}





