195 lines
6.0 KiB
Markdown
195 lines
6.0 KiB
Markdown
# 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
|