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}$$ EOP
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$. EOP

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$,

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$,

EOP

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$,

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$,

EOP

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}$.

EOP

Lemma 3.28

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

Proof:

(a)

(b)

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

EOP

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

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

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.

EOP