\documentclass[12pt,a4paper]{amsart}
%%%%%%%%%%% Here is where you tell LaTeX to use packages. Each
%%%%%%%%%%% package gives you access to different commands and
%%%%%%%%%%% functionality. Most of them are unnecessary for the
%%%%%%%%%%% mathematics in this document.

%%%%%%%%%%% If you hadn't figured out, the % symbol automatically
%%%%%%%%%%% nulls out all subsequent characters on that line. So
%%%%%%%%%%% it's used for commenting code.
\usepackage{hyperref}
\usepackage{tikz}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{multicol}
\usepackage[OT2,T1]{fontenc}
\usepackage{graphicx}
\usepackage[all]{xy}
\usepackage{color}
\usepackage{mathrsfs}
\usepackage{mathtools}

%%%%%%%%%%% Determining margins and spacing.
\setlength\topmargin{-0.3in}
\addtolength{\oddsidemargin}{-.625in}
	\addtolength{\evensidemargin}{-.625in}
	\addtolength{\textwidth}{1.25in}
\setlength\footskip{1in}

%%%%%%%%%%% I think this command enables `sections'
\numberwithin{equation}{section}

%%%%%%%%%%% This command allows you to label things as `theorem',
%%%%%%%%%%% `conjecture', etc.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}{Question}[theorem]
\newtheorem{example}{Example}[theorem]

\newcommand{\R}{\mathcal{R}}

\usepackage[utf8]{inputenc}
\title{Math 220.201 Class 24 Notes}
\begin{document}
\maketitle
\section{Recall from last time: convergence}
Recall the following definition from last time.
\begin{definition}
Let $a_1, a_2, a_3, \ldots$ be a sequence of real numbers. We say that $\{a_n\}$ {\bf converges} to the real number $L$ if\footnote{Here I've omitted the stipulation that $N$ be a natural number. Whether $N$ is or isn't a natural number isn't really relevant, as long as $n$ is required to be one.}
$$\forall \epsilon>0, \exists N>0, \forall n>N, |a_n-L|<\epsilon$$
If a sequence does not converge, we say it diverges.
\end{definition}
As an example, consider the sequence defined by $a_1=1$ and
$$a_{n+1}=a_n+\frac{1}{a_n}$$
for every $n\ge 1$. So this sequence goes $1, 2, 2.5, 2.9, ...$. It is increasing, but the rate of increase slows.
\begin{proposition}
This sequence diverges.
\end{proposition}
\begin{proof}
Since $a_n$ is positive for every $n$, it follows that $a_{n+1}>a_n$ for every $n$. Suppose for a contradiction that this sequence converges to some limit $L$.

First, we'll prove that $a_n<L$ for every $n$. Let us suppose there is some $m$ such that $a_m\ge L$. Write $a_m=L+d$ for some $d\ge 0$. Then $a_n\ge L+d$ for every $n\ge m$. If $d>0$, then it becomes impossible to have $|a_n-L|<\epsilon$ when $\epsilon=d$, giving a contradiction. If $d=0$, i.e. $a_m=L$, then $a_{m+1}=L+\frac{1}{L}$, and we have the same contradiction as the case $d>0$. Thus, for every $n$, $a_n<L$. Consequently, $\frac{1}{a_n}>\frac{1}{L}$, and so
$$a_{n+1}=a_n+\frac{1}{a_n}>a_n+\frac{1}{L}$$

Now pick $\epsilon=\frac{1}{2L}$. Then there is some $N$ such that for every $n>N$, $|a_n-L|<\frac{1}{2L}$. In particular, this implies $a_n>L-\frac{1}{2L}$. Then
$$a_{n+1}>\left(L-\frac{1}{2L}\right)+\frac{1}{L}=L+\frac{1}{2L}$$
But this contradicts the fact that $a_{n+1}<L$! Therefore, no such $L$ can exist.

\end{proof}


\section{Infinite series}
An \emph{infinite series} encodes the idea of summing an infinite number of terms.
\begin{definition}
Let $x_1, x_2, x_3, \ldots$ be real numbers. Then the {\bf series}
$$\sum\limits_{k=1}^{\infty}x_k=x_1+x_2+x_3+\ldots$$
is defined as the limit $\lim\limits_{n\to\infty}\sum\limits_{k=1}^{n}x_k$. Written another way, this is
$$x_1+x_2+x_3+\ldots=\lim\limits_{n\to\infty}s_n$$
where $s_n=x_1+x_2+\ldots+x_n=\sum\limits_{k=1}^{n}s_k$. $s_n$ is called the $n$-th {\bf partial sum.} $x_k$ is called the $k$-th {\bf term} of the series.
\end{definition}

Note that there is an important difference between the terms $x_k$ and the partial sums $s_n$. Consider the following example:
$$x_k=\frac{1}{k(k+1)}$$
Here, the terms of the series are $\frac{1}{2}, \frac{1}{6}, \frac{1}{12}, \frac{1}{20}, \ldots$. The sequence $\{x_k\}$ converges to $0$. However, the series $\frac{1}{2}+\frac{1}{6}+\frac{1}{12}+\frac{1}{20}$ converges to $1$.
\begin{proposition}
The series $\sum\limits_{k=1}^{\infty}\frac{1}{k(k+1)}$ converges to $1$.
\end{proposition}
\begin{proof}
In the worksheet from Class 10, we proved by induction that
$$\sum\limits_{k=1}^{n}\frac{1}{k(k+1)}=\frac{n}{n+1}$$
In other words, the $n$-th partial sum is $s_n=\frac{n}{n+1}$. We must therefore prove that $\lim\limits_{n\to\infty}\frac{n}{n+1}=1$. For any $\epsilon$, as long as $n>N=\frac{1}{\epsilon}$ we have that
$$|s_n-1|=\frac{1}{n+1}<\epsilon$$
We have thus shown that for every $\epsilon$ there exists an $N$, and so $s_n\to 1$.
\end{proof}

\section{Two examples}
Suppose that $x_1+x_2+x_3+\ldots$ is a series whose terms are all positive real numbers. What conditions are required in order for this series to converge? It's rather intuitive (and you should try proving!) that if $\sum\limits_{k=1}^{\infty}x_k$ converges, then $\lim\limits_{k\to\infty}x_k=0$. But as the example on page 1 shows, this isn't necessarily enough. So now the question is, how \emph{quickly} must $x_k$ decrease in order for the series to converge? Here are two examples
\begin{proposition}
Let $x_k=\frac{1}{k}$. Then the series\footnote{This is called the \emph{harmonic series}.}
$$\sum\limits_{k=1}^{\infty}x_k=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\ldots$$
diverges.
\end{proposition}
\begin{proof}
We can bound the $2^m$-th partial sum from below
$$\begin{aligned}
\sum\limits_{k=1}^{2^m}\frac{1}{k}&=1+\frac{1}{2}+\sum\limits_{k=2^1+1}^{2^2}\frac{1}{k}+\sum\limits_{k=2^2+1}^{2^3}\frac{1}{k}+\ldots+\sum\limits_{k=2^{m-1}+1}^{2^m}\frac{1}{k}\\
 &> 1+\frac{1}{2}+\sum\limits_{k=2^1+1}^{2^2}\frac{1}{4}+\sum\limits_{k=2^2+1}^{2^3}\frac{1}{8}+\ldots+\sum\limits_{k=2^{m-1}+1}^{2^m}\frac{1}{2^m}\\
 &= 1+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\ldots+\frac{1}{2}\\
 &= 1+\frac{m}{2}
\end{aligned}$$
Thus, $s_{2^m}>1+\frac{m}{2}$. Because $s_n$ is increasing as $n\to \infty$, it follows that for any $n\ge 2^m$, $s_n>1+\frac{m}{2}$. Thus, $s_n\to \infty$.\footnote{You can use an argument similar to that above to show that $s_{2^m}<m+\frac{1}{2}$. This gives you a pretty good estimate of how quickly the partial sums grow, as $s_{2^m}$ is somewhere between $\frac{m}{2}$ and $m$ for large values of $m$.}
\end{proof}
\begin{proposition}
Let $x_k=\frac{1}{k^2}$. Then the series
$$\sum\limits_{k=1}^{\infty}x_k=1+\frac{1}{4}+\frac{1}{9}+\frac{1}{16}+\ldots$$
converges.\footnote{It turns out this series converges to $\frac{\pi^2}{6}$. The question of how to prove this is called the \emph{Basel problem}.}
\end{proposition}
\begin{proof}
We have that
$$\begin{aligned}
s_n &= 1+\frac{1}{2\cdot 2}+\frac{1}{3\cdot 3}+\ldots+\frac{1}{n\cdot n}\\
&> 1+\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\ldots+\frac{1}{(n-1)\cdot n}\\
&= 1+\frac{n-1}{n}=2-\frac{1}{n}
\end{aligned}$$
Thus, for every $n$, $s_n<2-\frac{1}{n}$, so the $s_n$'s are bounded above. Therefore, the series converges.
\end{proof}
\section{Geometric series and the ratio test}
You may also be familiar with \emph{geometric series}. These show up in a variety of places in nature.
\begin{definition}
A geometric series has the form
$$a+ar+ar^2+ar^3+\ldots$$
for some real numbers $a$ and $r$. That is, $x_n=ar^{n-1}$. $a$ is the {\bf first term} and $r$ is the {\bf ratio}.
\end{definition}
\begin{proposition}
The geometric series above converges to $\frac{a}{1-r}$ when $|r|<1$ and to $0$ when $a=0$. If $|r|\ge 1$ and $a\neq 0$, it diverges.
\end{proposition}
\begin{proof}
Clearly if $a=0$, the geometric series converges. So let us now assume $a\neq 0$.

Consider the equation
$$(1+r+r^2+\ldots+r^{n-1})(1-r)=1-r^n$$
If $r\neq 1$, we can divide both sides by $1-r$ to get
$$1+r+r^2+\ldots+r^{n-1}=\frac{1-r^n}{1-r}$$
Thus, the $n$-th partial sum, $s_n=\sum\limits_{k=1}^{n}ar^{k-1}$ is equal to $a\cdot \frac{1-r^n}{1-r}$ as long as $r\neq 1$. So
$$\lim\limits_{n\to\infty}s_n=\lim\limits_{n\to\infty}a\cdot \frac{1-r^n}{1-r}=a\cdot \frac{1-\lim\limits_{n\to\infty}(r^n)}{1-r}$$
If $|r|<1$, $\lim\limits_{n\to\infty}(r^n)=0$ and so the above equals $\frac{a}{1-r}$. If $|r|\ge 1$, $\lim\limits_{n\to\infty}(r^n)$ diverges, and the above diverges.

The last case we did not address is when $r=1$. In this case, the geometric series is
$$a+a+a+a+\ldots$$
which clearly diverges.
\end{proof}
Okay, here's how we can use geometric series to prove the convergence of series that aren't quite geometric series.
\begin{proposition}
Let $x_k=\frac{k(k-1)}{3^k}$. The series $\sum\limits_{k=1}^{\infty}x_k$ converges.
\end{proposition}
The idea here is that once we get to very big $k$, $x_{k+1}$ is only slightly larger than $x_k/3$. The denominator always gets multiplied by $3$ from each term to the next, but the numerator does not increase very much. So if $x_{k+1}$ is only slightly larger than $x_k/3$, it must be smaller than $x_k/2$. We then can use this face to bound the tail of the series by a geometric series of ratio 2.
\begin{proof}
We first claim that for $k\ge 5$, $\frac{x_{k+1}}{x_k}\le \frac{1}{2}$. This is true because
$$\frac{x_{k+1}}{x_k}=\frac{\frac{k(k+1)}{3^{k+1}}}{\frac{k(k-1)}{3^k}}=\frac{k+1}{3(k-1)}$$
and
$$\frac{k+1}{3(k-1)}\le \frac{1}{2} \iff 2(k+1)\le 3(k-1) \iff 5\le k$$
Thus, it follows that
$$x_6\le \frac{1}{2}x_5$$
$$x_7\le \frac{1}{2}x_6\le \frac{1}{4}x_5$$
$$\vdots$$
$$x_{m+5}\le \frac{1}{2^m}x_5$$
$$\vdots$$
Thus, looking at the $(n+5)$-th partial sum for some $n$,
$$\begin{aligned}
s_{n+5}&=x_1+x_2+\ldots+x_{n+5}\\
&\le x_1+x_2+x_3+x_4+x_5+\frac{1}{2}x_5+\ldots+\frac{1}{2^n}x_5\\
&=x_1+x_2+x_3+x_4+\left(2-\frac{1}{2^n}\right)x_5\\
&\le x_1+x_2+x_3+x_4+2x_5\\
&= 0+\frac{2}{9}+\frac{2}{9}+\frac{4}{27}+\frac{40}{243}=\frac{184}{243}
\end{aligned}$$
So the $s_n$'s are bounded above and each is larger than the previous one. Therefore, they converge. (and in fact, converge to something less than $\frac{184}{243}$.)
\end{proof}
{\bf Just for fun:} If you would like to know how you'd compute the exact value of a series like this, there are some neat tricks for doing this. Consider the function $f(z)$ defined on the interval $-1\le z\le 1$:
$$f(z)=\frac{1}{1-z}=1+z+z^2+z^3+z^4+\ldots=\sum\limits_{k=0}^{\infty}z^k$$
The fact that these two expressions shown are equal holds because of the expression for the sum of a geometric series - which is valid whenever $-1\le z\le 1$. If you calculate $f(1/3)$, it gives you the value of $\sum\limits_{k=1}^{\infty}(1/3)^{k-1}$ to be equal to $\frac{1}{1-1/3}=3/2$. But you could instead look at $f'(z)$:
$$f'(z)=\frac{1}{(1-z)^2}=1+2z+3z^2+4z^3+5z^4+\ldots=\sum\limits_{k=0}^{\infty}kz^{k-1}$$
Take the derivative again to get
$$f''(z)=\frac{2}{(1-z)^3}=2+6z+12z^2+20z^3+\ldots=\sum\limits_{k=0}^{\infty}k(k-1)z^{k-2}$$
Now if you plug in $1/3$ you get
$$f''(1/3)=\frac{2}{(2/3)^3}=\sum\limits_{k=0}^{\infty}\frac{k(k-1)}{3^{k-2}}$$
This looks a whole lot like the sum we're trying to compute! The $k=0$ term is zero, so this is the same as $\sum\limits_{k=1}^{\infty}\frac{k(k-1)}{3^{k-2}}$. So if you take this and divide by $3^2$, you'll get the sum we're trying to actually calculate. Thus,
$$\sum\limits_{k=1}^{\infty}\frac{k(k-1)}{3^k}=\frac{1}{3^2}\cdot \frac{2}{(2/3)^3}=\frac{2\cdot 3^3}{3^2\cdot 2^3}=\boxed{\frac{3}{4}}$$

\section{Supremum, Infimum, Completeness Axiom}
We didn't get to the definition of the supremum, infimum, and a discussion of the Completeness Axiom in class today. See the notes posted on the main course website if you are curious. It has to do with how one axiomatically constructs the real numbers!

\end{document}