# Lecture 19

## Review

> Binomial theorem: For $n\in\mathbb{N}$,
> $$(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k$$

1. Show that $2^n\geq \binom{n}{4}$ for all $n\geq 4$. (Hint: Expand $(1+1)^n$ using the binomial theorem)
    Proof: 
    $$
    \begin{aligned}
    (1+1)^n&=\sum_{k=0}^{n}\binom{n}{k}1^{n-k}1^k\\
    &=\sum_{k=0}^{n}\binom{n}{k}\\
    &=\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}\\
    &\geq\binom{n}{4}
    \end{aligned}
    $$
    QED
2. Using part 1, show that $\lim_{n\to\infty}\frac{n^3}{2^n}=0$.  
   Proof:
   $$
   \frac{n^3}{2^n}\leq\frac{n^3}{\binom{n}{4}}
   $$
   The value of $\frac{n^3}{\binom{n}{4}}$ is decreasing when $n\geq 4$.
   QED

## New materials

### Series

#### Definition 3.21

Let $(a_n)_{n=1}^{\infty}$ be a sequence in $\mathbb{C}$. Let $s_n=\sum_{k=1}^{n}a_k$ denotes the sequence of partial sums.

1. We say the series $\sum_{n=1}^{\infty}a_n$ converges if the sequence of partial sums $(s_n)_{n=1}^{\infty}$ converges.
2. We define the sum of the series $\sum_{n=1}^{\infty}a_n$ to be the limit of the sequence of partial sums, i.e., $$\sum_{n=1}^{\infty}a_n=\lim_{n\to\infty}s_n=\lim_{n\to\infty}\sum_{k=1}^{n}a_k.$$

#### Theorem 3.22 (Cauchy criterion for series)

The series $\sum_{n=1}^{\infty}a_n$ converges if and only if for every $\epsilon>0$, there exists $N\in\mathbb{N}$ such that for all $m,n\in\mathbb{N}$ with $m\geq n\geq N$,
$$
\left|\sum_{k=n}^{m}a_k\right|<\epsilon.
$$

Proof:

$\sum_{n=1}^{\infty}a_n$ converges if and only if $(s_n)_{n=1}^{\infty}$ converges.

Since $\mathbb{C}$ is complete, $(s_n)_{n=1}^{\infty}$ converges if and only if $(s_n)_{n=1}^{\infty}$ is Cauchy.

Since $(s_n)_{n=1}^{\infty}$ is Cauchy, for every $\epsilon>0$, there exists $N\in\mathbb{N}$ such that for all $m,n\in\mathbb{N}$ with $m\geq n\geq N$,
$$
|s_m-s_n|=\left|\sum_{k=n}^{m}a_k\right|<\epsilon.
$$

QED

Special case of this theorem.

#### Corollary 3.23

If $\sum_{n=1}^{\infty}a_n$ converges, then $\lim_{n\to\infty}a_n=0$.

Note: the converse is not true. Example: $\sum_{n=1}^{\infty}\frac{1}{n}$ diverges.

The contrapositive of this corollary is: If $\lim_{n\to\infty}a_n\neq 0$, then $\sum_{n=1}^{\infty}a_n$ diverges. It is useful naming as ``n-th term test for divergence''.

Observe:

$\forall n,a_n\geq 0$

$(a_n)$ is a non-negative sequence if and only if $(s_n)_{n=1}^{\infty}$ is increasing sequence.

So if $(a_n)$ is a non-negative sequence, then $\sum_{n=1}^{\infty}a_n$ converges if and only if $(s_n)_{n=1}^{\infty}$ is bounded above.

#### Theorem 3.25 (Comparison test)

Let $(a_n)$ be a sequence in $\mathbb{C}$ and $(c_n)$ be a non-negative sequence in $\mathbb{R}$. Suppose $\forall n, |a_n|\leq c_n$.

(a) If the series $\sum_{n=1}^{\infty}c_n$ converges, then the series $\sum_{n=1}^{\infty}a_n$ converges.  
(b) If the series $\sum_{n=1}^{\infty}a_n$ diverges, then the series $\sum_{n=1}^{\infty}c_n$ diverges.

Proof:

(a) By **Theorem 3.22**, it's enough to show that for every $\epsilon>0$, there exists $N\in\mathbb{N}$ such that for all $m,n\in\mathbb{N}$ with $m\geq n\geq N$,
$$
\left|\sum_{k=n}^{m}a_k\right|<\epsilon.
$$

Let $\epsilon>0$ be arbitrary.

Since $\sum_{n=1}^{\infty}c_n$ converges, by **Theorem 3.22**, for the above $\epsilon$, there exists $N\in\mathbb{N}$ such that for all $m,n\in\mathbb{N}$ with $m\geq n\geq N$,
$$
\left|\sum_{k=n}^{m}c_k\right|\leq \sum_{k=n}^{m}c_k<\epsilon.
$$

QED

#### Theorem 3.26 (Geometric series)

Let $x\in\mathbb{C}$.

(a) If $|x|<1$, then the series $\sum_{n=0}^{\infty}x^n$ converges and $\sum_{n=0}^{\infty}x^n=\frac{1}{1-x}$.  
(b) If $|x|\geq 1$, then the series $\sum_{n=0}^{\infty}x^n$ diverges.

Proof:

(b) If $|x|\geq 1$, then $x^n$ does not converge to 0. So the series $\sum_{n=0}^{\infty}x^n$ diverges.

(a) Let $s_n=\sum_{k=0}^{n}x^k=1+x+x^2+\cdots+x^n$.

$xs_n=x+x^2+x^3+\cdots+x^n+x^{n+1}=s_n+x^{n+1}$.

So $s_n=\frac{1-x^{n+1}}{1-x}$.

Since $|x|<1$, $x^{n+1}$ converges to 0. So $\lim_{n\to\infty}s_n=\frac{1}{1-x}$.

QED

#### Lemma 3.28 

(a) $\sum_{n=0}^{\infty}\frac{1}{n}$ diverges.  
(b) $\sum_{n=0}^{\infty}\frac{1}{n^2}$ converges.

Proof:

(a)
$$
\begin{aligned}
\sum_{n=0}^{\infty}\frac{1}{n}&=\frac{1}{1}+\frac{1}{2}+\left(\frac{1}{3}+\frac{1}{4}\right)+\left(\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}\right)+\cdots\\
&>\frac{1}{2}+\frac{1}{2}+\left(\frac{1}{4}+\frac{1}{4}\right)+\left(\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}\right)+\cdots\\
&=\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\cdots\\
&=\infty
\end{aligned}
$$

(b)
$$
\begin{aligned}
\sum_{n=0}^{\infty}\frac{1}{n^2}&=\frac{1}{1}+\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+\cdots\\
&<\frac{1}{1}+\left(\frac{1}{2^2}+\frac{1}{2^2}\right)+\left(\frac{1}{4^2}+\cdots+\frac{1}{4^2}\right)+\left(\frac{1}{8^2}+\cdots+\frac{1}{8^2}\right)+\cdots\\
&=\frac{1}{1}+\frac{2}{2^2}+\frac{4}{4^2}+\frac{8}{8^2}+\cdots\\
&=\frac{1}{1}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}+\cdots\\
&=\frac{1}{1-\frac{1}{2}}\\
&=\frac{1}{\frac{1}{2}}\\
&=2
\end{aligned}
$$

> Fun fact: $\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}$.

QED

#### Theorem 3.27 (Cauchy condensation test)

Suppose $(a_n)$ is a non-negative sequence. The series $\sum_{n=1}^{\infty}a_n$ converges if and only if the series $\sum_{k=0}^{\infty}2^ka_{2^k}$ converges.

Proof:

Let $s_n=\sum_{k=1}^{n}a_k$ and $t_k=\sum_{k=0}^{k}2^ka_{2^k}$.

If $n\leq 2^k$, then 

$$
\begin{aligned}
s_n&=a_1+a_2+\cdots+a_n\\
&\leq a_1+(a_2+a_3)+(a_4+a_5+\cdots+a_7)+\cdots+(a_{2^k}+a_{2^k+1}+\cdots+a_{2^{k+1}-1})\\
&\leq a_1+2a_2+4a_4+\cdots+2^ka_{2^k}\\
&=t_k.
\end{aligned}
$$

If $n\geq 2^{k+1}$, then

$$
\begin{aligned}
s_n&=a_1+a_2+\cdots+a_n\\
&\geq a_1+a_2+(a_3+a_4)+(a_5+a_6+\cdots+a_7)+\cdots+(a_{2^k}+a_{2^k+1}+\cdots+a_{2^{k+1}-1})\\
&\geq a_1+a_2+2a_4+\cdots+2^{k-1}a_{2^k}\\
&\geq \frac{1}{2}\left(a_1+2a_2+4a_4+\cdots+2^ka_{2^k}\right)\\
&=\frac{1}{2}t_k.
\end{aligned}
$$

We have shown that

- If $n\leq 2^k$, then $s_n\leq t_k$.
- If $n\geq 2^{k+1}$, then $s_n\geq \frac{1}{2}t_k$.

So $(s_n)_{n=1}^{\infty}$ is a bounded above.

By **Theorem 3.14**, $(s_n)_{n=1}^{\infty}$ converges if and only if $(t_k)_{k=0}^{\infty}$ converges.

QED