\documentstyle[12pt,twoside,amsfonts, amstex, amssymb, epic]{article}
\input{macros-course}

\parskip1.5ex
\parindent0pt

\begin{document}
\handout{notes10}{Notes 10}{September 18, 1995}

For the next eight lectures, we are going to be talking about methods
for counting. Today we'll begin by covering methods for evaluating
sums and products. Then, next week we'll show you how to solve
recurrences. Later we'll cover combinatorics and generating functions.
This material is useful in several areas and will be particularly
useful when you study the running time of programs in 6.046.

\section{Annuities}

We'll start with an example many of you encountered when you got a
student loan, the problem of annuity pricing. An annuity is a
financial instrument which pays a fixed amount at the beginning of
every year for some specified length of time. In particular,

\begin{defin}
  An {\bf $n$-year, \$$m$-payment annuity} pays \$$m$ at the start of
  each year for $n$ years.
\end{defin}

In some cases $n$ is finite, but it doesn't have to be. Examples
include student loans, home mortgages (pay every month for 30 years),
``Megabucks'' (\$50,000 a year for 20 years), and retirement/life
insurance benefits. Folks on Wall Street specialize in these things.

Key question is what an annuity is worth.  It is clearly better to
have \$1 million today than \$50K a year for 20 years, because there is
inflation and interest and you get to use the money right away. But is
it better to have \$500K today?

In order to answer the question, we need to know what one dollar paid
in a year is worth today. This is usually tied to some interest rate.

Assume that there is a fixed interest rate $p$. So \$1 today is worth
\$$(1+p)$ after 1 year, and \$$(1+p)^2$ after 2 years. (interest
compounds).

Today $p$ is about 8\%.

Now we can see what the Megabucks payment is worth.

The first payment of $m$ is worth $m$. \\
The second payment of $m$ is only worth $\frac{m}{1+p}$. (Its value
goes up by $(1+p)$ over the year before it is paid, so it is worth $m$
when paid.) \\
Generalizing, the $n$-th payment payment is worth only
$\frac{m}{(1+p)^{n-1}}$.

The total value is the sum of all the payments, which we write as
$$ V= \sum_{i=1}^{n} \frac{m}{(1+p)^{i-1}} $$

So now to answer the question we need to evaluate this sum. With
values for $m,n,p$ we could do this by actually adding the terms, but
this sum has a special closed form which makes the job
easier. That is, we can rewrite the expression for $V$ as a simple
expression without the $\sum$ notation.

First we rewrite the sum a little:
$$V = \sum_{i=0}^{n-1} \frac{m}{(1+p)^i} $$
It is easy to see that we are still adding the same terms, so this sum
is the same as the previous, just written differently. Now, 
$$ V = m \sum_{i=0}^{n-1} x^i \: {\rm where}\: x = \frac{1}{1+p}$$

\begin{theorem}
  $$\forall n \geq 1, x\neq1, \sum_{i=0}^{n-1}x^i = \frac{1-x^n}{1-x} $$
\end{theorem}

\begin{proof}
  By induction on $n$.

  Base case: $n=1$
  $$\sum_{i=0}^0x^i = x^0 = 1 = \frac{1-x^1}{1-x} $$

  Inductive step:
  \begin{align*}
    \sum_{i=0}^{n-1}x^i &= \sum_{i=0}^{n-2}x^i + x^{n-1} \\
    &= \frac{1-x^{n-1}}{1-x} + x^{n-1} \:\:\: \text{(by inductive hypothesis)} \\
    &= \frac{1-x^{n-1}+x^{n-1}(1-x)}{1-x} \\
    &= \frac{1-x^n}{1-x}
  \end{align*}
\end{proof}

This proof is fine, but it gives no intuition for how we got the
answer. An alternate proof with better intuituion:

\begin{align*}
  S &= 1+x+x^2+\cdots +x^{n-1} \\
+ \: \:  -xS &= \: -x-x^2-\cdots -x^{n-1}-x^n \\
\hline \\
(1-x)S &= 1-x^n
\end{align*}

So now we can solve the annuity pricing problem:

\begin{align*}
  V &= m\frac{1-x^n}{1-x} \\
  &= m \frac{1-\left( \frac{1}{1+p}\right)^n}{1-\left(
      \frac{1}{1+p}\right)} \\
  &= m \frac{1+p-\frac{1}{(1+p)^{n-1}}}{p}
\end{align*}

For Megabucks, $m=\$50,000, n=20, p=.08 \Rightarrow V = \$
530,180$. So million dollar prize is really only worth a half million!

Notice that if it were paid forever it wouldn't make much difference. 
$$ \lim_{n \rightarrow \infty} V = m \frac{1+p}{p}$$
$$ m= \$50,000, p=.08 \Rightarrow V = \$675,000 $$

You should remember the formula for this sum (or how to derive it),
because it comes up in all sorts of applications.

\begin{theorem}
  $$|x| < 1 \Rightarrow \sum_{i=0}^{\infty}x^i = \frac{1}{1-x}$$
\end{theorem}

Some examples of these sums, finite and infinite:
 $$1+1/2+1/4+1/8+\cdots = \frac{1}{1-1/2} = 2$$
$$1+2+4+8+\cdots+2^{n-1} = \frac{1-2^n}{1-2} = 2^n-1 $$
$$1+3+9+27+\cdots+3^{n-1} = \frac{1-3^n}{1-3} = \frac{3^n-1}{2} $$

These are called geometric series. In general, the sum of a geometric
series is about the same as the largest term. (Notice that whether
this is the first or last term depends on whether $|x|<1$)

\section{Related sums}

Sometimes we get sums that aren't geometric, but are close. For example
$$ \sum_{i=1}^t ix^i = x+2x^2+3x^3+\cdots+tx^t $$

It turns out that there is a nice trick for evaluating this sum that
is fairly useful. The idea is to take the formula for a geometric
series and differentiate with respect to $x$.

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

But we wanted $x^i$, not $x^{i-1}$, so multiply by $x$.
 $$ \sum_{i=0}^{n-1} ix^i = \frac{x-nx^n + (n-1)x^{n+1}}{(1-x)^2} $$

And we wanted the sum to $t$, not $n-1$, so set $t=n-1$ and
substitute.
 $$ \sum_{i=0}^{t} ix^i = \frac{x-(t+1)x^{t+1} + tx^{t+2}}{(1-x)^2} $$

And we wanted the sum from $i=1$, not 0, but the $i=0$ term $=0$, so
just delete it. Now finally,

 $$ \sum_{i=1}^{t} ix^i = \frac{x-(t+1)x^{t+1} + tx^{t+2}}{(1-x)^2} $$

Now to make sure that we didn't make a mistake we really ought to go
verify this by induction. For homework you'll do $\sum i^2x^i$ by
taking another derivative.

Notice that if $|x|<1$, then this sum converges even if $t$ is
infinite.

\begin{theorem}
  $$ |x| <1 \Rightarrow \sum_{i=1}^\infty ix^i = \frac{x}{(1-x)^2} $$
\end{theorem}

For example, an annuity that pays $ \$im $ at the end of year $i$ is
worth $$ \frac{m\frac{1}{1+p}}{\left( 1 - \frac{1}{1+p} \right) ^2} =
\frac{m(1+p)}{p^2} $$
$m= \$50K, p=.08 \Rightarrow V= \$8,437,500$

So even though you get paid more and more each year, total current
value is finite. Eventually, value of payments far into the future
aren't worth enough to matter, even though they are increasing.

Another example:
$$ \sum_{i=1}^\infty i2^{-i} = \frac{1/2}{(1/2)^2} = 2 $$

\section{Book Stacking}

We're now going to look at a completely different type of sum that
raises from a physics problem. The problem is to make a stack of $n$
books on the edge of a table (that won't fall over) where the top book
hangs out completely off the table.

\setlength{\unitlength}{0.00083333in}
\begin{picture}(6009,2214)(0,-10)
\thicklines
\drawline(12,912)(2412,912)(2412,12)
        (12,12)(12,912)
\drawline(1812,912)(2637,912)(2637,1062)
        (1812,1062)(1812,912)
\drawline(2112,1062)(2937,1062)(2937,1212)
        (2112,1212)(2112,1062)
\drawline(2262,1212)(3087,1212)(3087,1362)
        (2262,1362)(2262,1212)
\drawline(2487,1362)(3312,1362)(3312,1512)
        (2487,1512)(2487,1362)
\drawline(3687,2037)(4512,2037)(4512,2187)
        (3687,2187)(3687,2037)
\drawline(3462,1887)(4287,1887)(4287,2037)
        (3462,2037)(3462,1887)
\drawline(1482.000,1032.000)(1512.000,912.000)(1542.000,1032.000)
\drawline(1512,912)(1512,2112)
\drawline(1542.000,1992.000)(1512.000,2112.000)(1482.000,1992.000)
\put(3087,1587){.}
\put(3237,1662){.}
\put(3387,1737){.}
\put(800,1512){$n$ books}
\put(3687,1362){top book hanging out off edge!}
\put(837,387){table}
\end{picture}

Is this even possible? Yes! The demo worked in class.

The trick is to put the top book so that its center of mass is at the
edge of the second book, and then place the second book so that the
center of mass of the top two is at the edge of the third book, and so
on. So in general, we place the $k$th book such that the center of mass of the
top $k$ books is at the edge of the $(k+1)$st book.

Assuming the book size is 2, how far do we place the right edge of the
$k$th book out from the right edge of the $(k+1)$st book?

Clearly we place the top book out 1.

Let $x$ be the distance from the edge of the third book to the edge of
the second. Then the center of mass $m$ of the top two is given by $2m
= (x+1-1)+(x-1)=2x-1$. To be stable we need this over the third book,
$m \leq 0$, so $2x-1 \leq 0$, which means $x \leq 1/2$. We'll put it
right at the edge.

If we do this again for the top 3, we get that the center of mass $m$
is given by $3m = (x+1/2+1-1)+(x+1/2-1)+(x-1) = 3x -1$, so we place
the third book $1/3$ from the fourth.

Now it looks like a pattern. so let's guess that we can place the
$k$th book $1/k$ from the $(k+1)$st book.

Center of mass for $k$ books with respect to $(k+1)$st book is then:

$$  (1+1/2+\cdots +1/k-1)+(1/2+1/3+\cdots +1/k-1)+\cdots +(1/k-1) $$
\begin{align*}
  &= \sum_{i=1}^{k} m_i \: \text{where} \: m_i = \left( \sum_{j=i}^k
    1/j \right) -1 \\
  &= \sum_{i=1}^{k}  \left[ \left( \sum_{j=i}^k 1/j \right) -1 \right]
  \\
  &= \left( \sum_{i=1}^{k}  \sum_{j=i}^k 1/j \right) -k \\
  &= \left( \sum_{j=1}^k \sum_{i=1}^j 1/j \right)  - k \\
 &= \left( \sum_{j=1}^k 1 \right ) -k \\
 &= k-k \\
 &= 0
\end{align*}

So the center of mass is at the edge of the $(k+)1$st book, which
means that it balances, as it is supposed to.

A bit more should be said about how we reversed $i$ and $j$ in the
double sum. The idea is to write the double sum out in a table, and then it
is clear that summing the columns first instead of the rows is
helpful, and it is also clear what $i$ and $j$ should range over so
that the sum is correct. So with $j$ going across and $i$ going down
we write:

\begin{alignat*}{3}
  1 + &1/2 + &1/3 + \cdots + &1/k \\
      &1/2 + &1/3 + \cdots + &1/k \\
      &      &1/3 + \cdots + &1/k \\
      &&\cdots & \\
      &&& 1/k \\
\end{alignat*}

It is easy to see that the columns each add up to 1, so the right
thing to sum is $i$ from 1 to $j$, and then sum that over all $j$
(which is what we did).

So we know now that we have a stable scheme, but how far out is the
top book? It is shifted out
$$H_n = \sum_{i=1}^n \frac{1}{i} $$

How big is this?
\begin{align*}
  H_1 &= 1 \\
H_2 &= 1+1/2=3/2 \\
H_3 &= 11/6 \\
h_4 &= 25/12 >2 
\end{align*}

So 4 books is enough to get one out over edge!

The $H_n$ are actually well studied sums called the Harmonic Numbers.
They grow to infinity. Let's try to get a handle on how fast. That is,
how many books do we need to reach a given distance as a function of
the distance?

We use what is known as the integral method for bounding a sum. We
bound it above and below by an integral:

\setlength{\unitlength}{0.0125in}
\begin{picture}(335,190)(0,-10)
\drawline(75,175)(75,15)(335,15)
\drawline(95,135)(95,15)(75,15)
        (75,135)(95,135)
\drawline(115,15)(115,75)(95,75)
        (95,15)(115,15)
\drawline(135,15)(135,55)(115,55)
        (115,15)(135,15)
\drawline(155,15)(155,45)(135,45)
        (135,15)(155,15)
\drawline(175,15)(175,40)(155,40)
        (155,15)(175,15)
\drawline(195,15)(195,35)(175,35)
        (175,15)(195,15)
\drawline(215,15)(215,30)(195,30)
        (195,15)(215,15)
\drawline(315,20)(315,15)(295,15)
        (295,20)(315,20)
\drawline(40,85)(85,90)
\drawline(77.270,87.129)(85.000,90.000)(76.828,91.104)
\drawline(145,135)(105,110)
\drawline(110.724,115.936)(105.000,110.000)(112.844,112.544)
\drawline(75,135)       (75.828,131.757)
        (76.633,128.631)
        (77.418,125.617)
        (78.182,122.713)
        (78.926,119.917)
        (79.652,117.225)
        (80.360,114.636)
        (81.051,112.145)
        (82.387,107.451)
        (83.667,103.121)
        (84.899,99.133)
        (86.089,95.465)
        (87.245,92.094)
        (88.374,89.000)
        (89.484,86.160)
        (90.582,83.552)
        (92.771,78.943)
        (95.000,75.000)

\drawline(95,75)        (96.674,72.625)
        (98.888,69.960)
        (101.492,67.132)
        (104.331,64.269)
        (107.254,61.497)
        (110.108,58.943)
        (115.000,55.000)

\drawline(115,55)       (119.241,52.394)
        (121.923,50.959)
        (124.781,49.521)
        (127.666,48.142)
        (130.430,46.887)
        (135.000,45.000)

\drawline(135,45)       (139.369,43.682)
        (142.090,42.992)
        (144.967,42.307)
        (147.848,41.647)
        (150.581,41.029)
        (155.000,40.000)

\drawline(155,40)       (159.406,38.898)
        (162.129,38.218)
        (165.000,37.500)
        (167.871,36.782)
        (170.594,36.102)
        (175.000,35.000)

\drawline(175,35)       (179.392,33.852)
        (182.103,33.131)
        (184.962,32.377)
        (187.827,31.638)
        (190.551,30.963)
        (195.000,30.000)

\drawline(195,30)       (198.292,29.449)
        (201.807,28.906)
        (205.582,28.366)
        (209.654,27.826)
        (214.060,27.282)
        (218.835,26.730)
        (221.373,26.450)
        (224.017,26.168)
        (226.773,25.881)
        (229.643,25.590)
        (232.633,25.295)
        (235.748,24.994)
        (238.993,24.689)
        (242.370,24.377)
        (245.887,24.058)
        (249.545,23.733)
        (253.352,23.400)
        (257.310,23.060)
        (261.425,22.711)
        (265.702,22.354)
        (270.144,21.987)
        (274.756,21.611)
        (279.543,21.224)
        (284.510,20.827)
        (287.062,20.625)
        (289.661,20.419)
        (292.306,20.211)
        (295.000,20.000)

\drawline(95,135)       (95.828,131.757)
        (96.633,128.631)
        (97.418,125.617)
        (98.182,122.713)
        (98.926,119.917)
        (99.652,117.225)
        (100.360,114.636)
        (101.051,112.145)
        (102.387,107.451)
        (103.667,103.121)
        (104.899,99.133)
        (106.089,95.465)
        (107.245,92.094)
        (108.374,89.000)
        (109.484,86.160)
        (110.582,83.552)
        (112.771,78.943)
        (115.000,75.000)

\drawline(115,75)       (116.674,72.625)
        (118.888,69.960)
        (121.492,67.132)
        (124.331,64.269)
        (127.254,61.497)
        (130.108,58.943)
        (135.000,55.000)

\drawline(135,55)       (139.241,52.394)
        (141.923,50.959)
        (144.781,49.521)
        (147.666,48.142)
        (150.430,46.887)
        (155.000,45.000)

\drawline(155,45)       (159.369,43.682)
        (162.090,42.992)
        (164.967,42.307)
        (167.848,41.647)
        (170.581,41.029)
        (175.000,40.000)

\drawline(175,40)       (179.406,38.898)
        (182.129,38.218)
        (185.000,37.500)
        (187.871,36.782)
        (190.594,36.102)
        (195.000,35.000)

\drawline(195,35)       (199.392,33.852)
        (202.103,33.131)
        (204.962,32.377)
        (207.827,31.638)
        (210.551,30.963)
        (215.000,30.000)

\drawline(215,30)       (218.292,29.449)
        (221.807,28.906)
        (225.582,28.366)
        (229.654,27.826)
        (234.060,27.282)
        (238.835,26.730)
        (241.373,26.450)
        (244.017,26.168)
        (246.773,25.881)
        (249.643,25.590)
        (252.633,25.295)
        (255.748,24.994)
        (258.993,24.689)
        (262.370,24.377)
        (265.887,24.058)
        (269.545,23.733)
        (273.352,23.400)
        (277.310,23.060)
        (281.425,22.711)
        (285.702,22.354)
        (290.144,21.987)
        (294.756,21.611)
        (299.543,21.224)
        (304.510,20.827)
        (307.062,20.625)
        (309.661,20.419)
        (312.306,20.211)
        (315.000,20.000)

\put(245,20){.}
\put(255,20){.}
\put(265,20){.}
\put(115,0){2}
\put(135,0){3}
\put(155,0){4}
\put(175,0){5}
\put(195,0){6}
\put(215,0){7}
\put(285,0){$n-1$}
\put(315,0){$n$}
\put(95,0){1}
\put(145,130){$\frac{1}{x}$}
\put(0,80){$\frac{1}{x+1}$}
\end{picture}

$$ \text{Area in boxes} = H_n = \sum_{i=1}^n \frac{1}{i}$$

\begin{align*}
  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) \\
  \ln (n+1) &\leq H_n \leq \ln (n) +1
\end{align*}

So to get top book out 100 beyond desk we need about $e^{99}$ to
$e^{100}$ books. (That would take a while to build...)

Actually, there is a better approximation, but it is beyond what we
will do in this course, so we'll just state it as a fact:

$$ H_n = \ln (n) + \gamma + \frac{1}{2n} - \frac{1}{12n^2}+
\frac{\epsilon (n)}{120n^4} $$
$$ \text{where} \: 0<\epsilon (n) < 1 \: \text{and} \: \gamma =
\text{Euler's Constant} \approx 0.577215664 $$

Not all that much is known about $\gamma$, not even whether is is
irrational. 

Note that it is usually good enough to get close to answer. We write 
$$ H_n \sim \ln (n)$$
to indicate that the leading term in series is $\ln (n)$.

In general, 
$$ f(n) \sim g(n) \Rightarrow \lim_{n \rightarrow \infty}
\frac{f(n)}{g(n)} \rightarrow 1 $$

Some people write $H_n \sim \ln (n) + \gamma$, meaning that the next
term is $\gamma$, but it really should be $H_n - \ln (n) \sim \gamma$.
There is some more related notation that will be covered in
recitation.

\section{Products}

Now we'll look at what happens if we have a product instead of a sum.
In particular, about how big is $n! = \prod_{i=1}^n i$?

We don't know much about products, so the best thing to do is to
convert them to sums by taking logarithms of both sides. So,
\begin{align*}
  \ln (n!) &= \ln (1 \cdot 2 \cdot 3 \cdot \cdots \cdot n) \\
  &= \ln (1) + \ln (2) + \ln (3) + \cdots + \ln (n) \\
  &= \sum_{i=1}^n \ln (i)
\end{align*}

So we can get an expression for $n!$ by evaluating this sum.
Approximate it with the integral method as before, and we get 
$$ \int_1^n \ln x dx \leq \ln n! \leq \int_0^n \ln (x+1)dx $$

\begin{align*}
  \int_1^n \ln x dx &= x \ln x -x |_1^n \\
  &= n \ln n -n +1 \\
  &= n \ln \left(\frac{n}{e}\right) + 1 
\end{align*}
and, 
\begin{align*}
  \int_0^n \ln (x+1) dx &=   \int_1^{n+1} \ln x dx  \\
&= x \ln x -x |_1^{n+1} \\
  &= (n+1) \ln (n+1) -(n+1) +1 \\
  &= (n+1) \ln \left(\frac{n+1}{e}\right) + 1
\end{align*}
so,
$$ n\ln \left(\frac{n}{e}\right)+1 \leq ln (n!) \leq
(n+1)\ln\left(\frac{n+1}{e}\right) + 1 $$ 
$$ \left(\frac{n}{e}\right)^ne \leq n! \leq
\left(\frac{n+1}{e}\right)^{n+1}e $$ 

So now we know that $n!$ grows like $\left(\frac{n}{e}\right)^n$.

We can go back an compute error terms, getting a better bound for
$n!$:

$$ \left(\frac{n}{e}\right)^n \sqrt{2\pi n}e^{\frac{1}{12n+1}} \leq n! \leq
\left(\frac{n}{e}\right)^n \sqrt{2\pi n}e^{\frac{1}{12n}} $$
$$ \Rightarrow n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n
\:\:\:\text{(Stirling's Formula)} $$

There is no closed form expression for $n!$, but from Stirling's
formula we can get nearly tight bounds on $n!$ that are in closed
form.

For example, if $n=100$, then
$$ \left(\frac{100}{e}\right)^{100} \sqrt{200 \pi}e^{\frac{1}{1201}} \leq n! \leq
  \left(\frac{100}{e}\right)^{100} \sqrt{200 \pi}e^{\frac{1}{1200}} $$
$ e^{\frac{1}{1201}} = 1.00083299$ and $e^{\frac{1}{1200}} = 1.00083368$,
so the upper bound is $\leq (1+10^{-6})$lower bound, which means the
approximation is correct to six digits! This is good enough for many
practical purposes. If needed, the bounds can be made tighter with
further error calculations.

Note that it is pretty neat that we were able to get such tight bounds
on $n!$. It is clear that $n! >2^n$ and $n!<n^n$, but who would 
guess that $n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$?

Remember Stirling's Formula because it is important and will come up again.

\section{Some Additional Summations}

\subsection{Sums of Squares}
You remember from an earlier problem set that we asked you to 
prove by induction that 
$$\sum_{i=0}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6} n.$$
Now we're in a part of the course where the idea is to {\em derive} formulas
for summations.  So it's natural to ask --- how might you be able to
come up with a formula like this?

First, note that using the integral method, we can roughly approximate
$\sum_{i=0}^n i^2$ by $$\int_0^n x^2 dx = \frac{1}{3} n^3.$$
So it's reasonable to guess that the answer is approximately 
$\frac{1}{3} n^3$.  Based on this, let's guess that the sum has
the form $a n^3 + b n^2 + c n + d$, for some values of $a, b, c, d$
that we haven't yet figured out.  

Since $\sum_{i=0}^0 i^2 = 0 = d$, we know $d = 0$.  Now, plugging
in the sums for $n = 1, 2, 3$, we get the following three equations
in the three unknowns $a, b, c$.  
$$a + b + c = 1$$
$$8a + 4b + 2c = 5$$
$$27a + 9b + 3c = 14$$
Solving this system, we get (surprise, surprise), 
$$a = \frac{1}{3}$$
$$b = \frac{1}{2}$$
$$c = \frac{1}{6}$$
Now --- and this is very important --- we have not {\em proved} that
this is the correct formula for $\sum_{i=0}^n i^2$.  We've only established
that it is consistent with the first four values of $n$.  But now we
can go and verify that it works for all $n$ by induction.

Another possible way to approach this problem is to notice that 
$$\sum_{i=1}^n i^2 = \sum_{i=1}^n i^2 x^{i-1} \:: \text{for} \:\: x=1$$

We saw before that
$$\forall x \neq 1, \: \sum_{i=1}^n i x^i =
\frac{x-(n+1)x^{n+1}+nx^{n+2}}{(1-x)^2} $$

So
$$\sum_{i=1}^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} $$

We want to evaluate at $x=0$, but of course there is a problem because
this is $0/0$. So take the limit as $x \rightarrow 1$ and use
L'H\^opital's rule. We're not going to write it all out here. Take
three derivatives on top and bottom and simplify and the right answer
comes out. This is such a mess that checking by induction would be a
good idea.

A third possible way is to use a trick to squeeze the exact answer out
of the integral method. We know that 
$$\sum_{i=1}^n i^2 \sim \frac{n^3}{3}$$

So we write an expression for how much this is wrong:
$$E_n = \sum_{i=1}^n i^2 - \frac{n^3}{3}$$
Then
$$E_{n-1} = \sum_{i=1}^{n-1} i^2 - \frac{(n-1)^3}{3}$$
So
\begin{align*}
E_n-E_{n-1} &= n^2 -\frac{n^3}{3} +\frac{(n-1)^3}{3} \\
&= n^2 -
\frac{n^3}{3}+\frac{n^3}{3}-\frac{3n^2}{3}+\frac{3n}{3}-\frac{1}{3} \\
&= n-\frac{1}{3} \\
\Rightarrow E_n &= \left(n-\frac{1}{3}\right)+E_{n-1} \\
&= \left(n-\frac{1}{3}\right)+\overbrace{\left(n-1-\frac{1}{3}\right)+E_{n-2}} \\
&=
\left(n-\frac{1}{3}\right)+\left(n-1-\frac{1}{3}\right)\overbrace{\left(n-2-\frac{1}{3}\right)+E_{n-3}}
\\
&\cdots \\ 
&= \left(n-\frac{1}{3}\right) +
\left(n-1-\frac{1}{3}\right) + \cdots + \left(2-\frac{1}{3}\right) +
  \left(1-\frac{1}{3}\right) + E_0 \\ 
&= \sum_{i=1}^n  \left(i-\frac{1}{3}\right) 
\\ &= \sum_{i=1}^n i-\sum_{i=1}^n \frac{1}{3} \\ 
&= \frac{n(n+1)}{2}-\frac{n}{3} \\ 
\Rightarrow  E_n &= \frac{n^2}{2}+\frac{n}{6} \\ 
\Rightarrow \sum_{i=1}^n i^2 &= \frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}
\end{align*}

\subsection{Some Infinite Sums}

Let's see how the integral method proves that the sum
$$\sum_{i=1}^{\infty} \frac{1}{i^2}$$
converges.  (Many of you may have seen this in calculus.)
Using the technique from earlier in lecture, we know that
this sum, minus its first term, is less than the area under the curve
$y = 1/x^2$ from $1$ to $\infty$.  That it,
\begin{eqnarray*}
\sum_{i=1}^{\infty} \frac{1}{i^2} & = & 1 + \sum_{i=2}^{\infty} 
\frac{1}{i^2} \\
& \leq & 1 + \int_1^{\infty} x^{-2} dx \\
& = & 2.
\end{eqnarray*}
Thus, our infinite sum is at most $2$, and in particular it converges.
In fact, one can prove (using complex analysis) that the exact value
of the sum is $\pi^2 / 6$; we won't prove this here.

Next let's look at the following {\em doubly infinite} sum
$$\sum_{i=0}^{\infty} \sum_{j=1}^{\infty} x^i y^j,$$
where (critically) $$0 < x, y < 1.$$
We can therefore re-write this as
\begin{eqnarray*}
\sum_{i=0}^{\infty} \sum_{j=1}^{\infty} x^i y^j & = &
\sum_{i=0}^{\infty} x^i \left( \sum_{j=1}^{\infty} y^j \right) \\
& = & \sum_{i=0}^{\infty} x^i \left( \frac{1}{1 - y} \right) \\
& = & \left( \frac{1}{1 - y} \right) \sum_{i=0}^{\infty} x^i \\
& = & \frac{1}{(1 - x) (1 - y)}.
\end{eqnarray*}
Note that these manipulations were justified because we had a
series of positive real numbers whose sum converged.

Just to reinforce this, here's a case in which re-arrangements
of the sum are clearly not allowed.
Let 
$$S = \sum_{i=0}^{\infty} (-1)^i = 1 + (-1) + 1 + (-1) + \cdots.$$
Consider the following:
$$S = [ 1 + (-1) ] + [ 1 + (-1) ] + \cdots = 0 + 0 + \cdots = 0.$$
$$S = 1 + [(-1) + 1] + [(-1) + 1] + \cdots = 1 + 0 + 0 + \cdots = 1.$$
What's the problem here?  

The point is that $S$ is not well-defined,
since it does not converge.

\section{Asymptotic Notation}

Above we wrote the fuzzy statement that the sum $\sum_{i=0}^n i^2$
``is approximately $\frac{1}{3} n^3$.''  Here, let's talk about some
ways to make statements like this more precise.

\subsection{Big-Oh Notation}

\begin{defin}
Given functions $f$ and $g$, we say that $f(x)$ is $O(g(x))$ if there
exist constants $c$ and $x_0$ (independent of $x$) so that 
$$\forall x \geq x_0 ~ : ~ 0 \leq f(x) \leq c \cdot g(x).$$
\end{defin}

So big-Oh notation is a way of saying that $f(x)$ is bounded from
above by $g(x)$, ignoring (i) constant factors, and (ii) small
values of $x$.  

Just to make sure we have the definition straight, here are some
examples:

$x^2$ is $O(x^3)$.

$100x$ is $O(x)$.

$x + \sqrt{x}$ is $O(x)$.

$2^x$ is $O(4^x)$.

$4^x$ is not $O(2^x)$.

$\log_2 (x)$ is $O(\log_{10}(x))$.

Just to show how to prove that a function $f$ is {\em not} $O(g)$ for some
function $g$, let's prove the fifth statement on the above list.

\begin{theorem}
$4^x$ is not $2^x$.
\end{theorem}
\begin{proof}
By contradiction.  Suppose that $4^x$ is $O(2^x)$; then 
there are constants $c$ and $x_0$ so that for all $x \geq x_0$, 
we have $4^x \leq c \cdot 2^x$.  But then, dividing both sides
by $2^x$, we get that $2^x \leq c$ for all $x \geq x_0$.  But
when $x > \log_2 (c)$, this is not true --- a contradiction.
\end{proof}

The final statement on our list follows because
$$\log_2(x) = \log_2 (10) \cdot \log_{10}(x)$$
for all $x$.

\subsection{Big-Omega Notation}

Big-Omega notation works exactly the same way as Big-Oh notation,
except that it provides {\em lower} bounds on the growth of a
function.

\begin{defin}
Given functions $f$ and $g$, we say that $f(x)$ is $\Omega(g(x))$ if there
exist constants $c$ and $x_0$ (independent of $x$) so that 
$$\forall x \geq x_0 ~ : ~ 0 \leq f(x) \geq c \cdot g(x).$$
\end{defin}

Let's go through the same five examples from above.

$x^2$ is not $\Omega(x^3)$.

$100x$ is $\Omega(x)$.

$x + \sqrt{x}$ is $\Omega(x)$.

$2^x$ is not $\Omega(4^x)$.

$4^x$ is $\Omega(2^x)$.

$\log_2 (x)$ is $\Omega(\log_{10}(x))$.

\subsection{Big-Theta Notation}

Finally, you'll notice that in some of our examples above we
had functions $f$ and $g$ so that $f$ was $O(g)$ and also 
$f$ was $\Omega(g)$ --- this corresponds to the notion that
$f(x)$ and $g(x)$ are always within a constant factor of one another
(for large enough $x$).

This is captured by Big-Theta notation.

\begin{defin}
Given functions $f$ and $g$, we say that $f(x)$ is $\Theta(g(x))$ if 
$f(x)$ is $O(g(x))$ and $f(x)$ is $\Omega(g(x))$.  That is, if and
only if there
exist constants $c_1, c_2$ and $x_0$ (independent of $x$) so that 
$$\forall x \geq x_0 ~ : ~ 0 \leq c_1 g(x) \leq f(x) \leq c_2 \cdot g(x).$$
\end{defin}

In this case, we can say that $g$ is a {\em tight asymptotic bound} for
$f$.  Going through our examples again, we have

$x^2$ is not $\Theta(x^3)$.

$100x$ is $\Theta(x)$.

$x + \sqrt{x}$ is $\Theta(x)$.

$2^x$ is not $\Theta(4^x)$.

$4^x$ is not $\Theta(2^x)$.

$\log_2 (x)$ is $\Theta(\log_{10}(x))$.

Note that the third example shows that $f$ can be $\Theta(g)$ even 
when $f$ is not a {\em fixed} constant multiple of $g$.

\subsection{Little-oh notation}

Finally, we want to capture the notion that a function $f$ grows
strictly more slowly than a function $g$.  That is, we want to
model the case in which
$$\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = 0,$$
but we want our definition to make sense independent of the
notion of taking a limit.

So we write
\begin{defin}
Given functions $f$ and $g$, we say that $f(x)$ is $o(g(x))$ if \\
\hspace*{0.3in}
{\em for all} constants $c > 0$, \\
\hspace*{0.3in}
there exists an $x_0$ such 
that \\
\hspace*{0.3in}
for all $x \geq x_0$ we have \\
\hspace*{0.3in}
$0 \leq f(x) \leq c \cdot g(x).$
\end{defin}

Going through our six examples again,

$x^2$ is $o(x^3)$.

$100x$ is not $o(x)$.

$x + \sqrt{x}$ is not $o(x)$.

$2^x$ is $o(4^x)$.

$4^x$ is not $o(2^x)$.

$\log_2 (x)$ is not $o(\log_{10}(x))$.


\end{document}
