Series Convergence

26 Jan 2018

Prologue To The Series Convergence

Series is a collection of the data ordered by indices, maybe in a time sequence manner, pervasively by monotonic increasing numbers. This article will inspect the convergence versus divergence of a given series. The convergence of series could be a key factor in some topics in reinforcement learning, usually in a discounted representation of value function deduction.

Begin By Geometric Series

➀this is a geometric series, $1$,$x$,$x^2$,$x^3$,…, when you sum them up, then $1$+$x$+$x^2$+$x^3$+…=$\frac {1-x^{n+1}}{1-x}$, and why?
Since $1+x$=$\frac {1-x^2}{1-x}$,$1+x+x^2$=$\frac {1-x^3}{1-x}$,…,then, $1+x+x^2+…+x^{n-1}$=$\frac {1-x^n}{1-x}$

➁what $1$+$x$+$x^2$+$x^3$+…finally becomes?
This equates to the discussion of the case when n approaches infinity:
When $\left|x\right|<1$, it converges and $\lim_{n\rightarrow\infty}\frac {1-x^n}{1-x}$=$\lim_{n\rightarrow\infty}\frac {1}{1-x}$
When $\left|x\right|>1$, it divergence and $\lim_{n\rightarrow\infty}\frac {1-x^n}{1-x}$=$\lim_{n\rightarrow\infty}\frac {1-x^n}{1-x}$

➂by directly dividing, we have: This says $1+x+x^2+…+x^{n-1}$=$\frac {1}{1-x}$

What’s The Function Of $1$-$x$+$x^2$-$x^3$+$x^4$-$x^5$+…?

Let $f(x)$=$1$-$x$+$x^2$-$x^3$+$x^4$-$x^5$+…, then their first, second, third, forth order derivative are below:
$f^{(1)}(x)$=$-1$+$2\cdot x$-$3\cdot x^2$+$4\cdot x^3$-$5\cdot x^4$+…
$f^{(2)}(x)$=$2$-$6\cdot x$+$12\cdot x^2$-$20\cdot x^3$+…
$f^{(3)}(x)$=$-6$+$24\cdot x$-$60\cdot x^2$+…
$f^{(4)}(x)$=$24$-$120\cdot x$+…

Departure from $x$=$0$, where $\triangle x\rightarrow 0$, thus:
$\lim_{\triangle x\rightarrow 0}f(x+\triangle x)$
$\approx\lim_{\triangle x\rightarrow 0}f(\triangle x)$
$=f(0)$+$f^{(1)}(0)\cdot\triangle x$+$\frac {1}{2}\cdot f^{(2)}(0)\cdot(\triangle x)^2$+$\frac {1}{6}\cdot f^{(3)}(0)\cdot(\triangle x)^3$+…
$=1$-$\triangle x$+$(\triangle x)^2$-$(\triangle x)^3$+$(\triangle x)^4$-$(\triangle x)^5$+…

Replace $\triangle x$ by $x$, we finally have $f(x)$

, then:
➀let $f(x)$=$\frac {1}{x}$, then $f(0)$=$\infty$, boom!
➁let $f(x)$=$\frac {1}{x-1}$, then $f(0)$=$-1$, a contradiction!
➂let $f(x)$=$\frac {1}{1-x}$, then:
$f(0)$=$1$
$f^{(1)}(0)$=$-(1-x)^{-2}$=$-1$
$f^{(2)}(0)$=$-2\cdot(1-x)^{-3}$=$-2$, boom!
➃let $f(x)$=$\frac {1}{1+x}$, then:
$f(0)$=$1$
$f^{(1)}(0)$=$-(1+x)^{-2}$=$-1$
$f^{(2)}(0)$=$2\cdot(1+x)^{-3}$=$2$, looks good
$f^{(3)}(0)$=$-6\cdot(1+x)^{-4}$=$-6$, still holds
$f^{(4)}(0)$=$24\cdot(1+x)^{-5}$=$24$, wow, that’s it

Thus, $f(x)$=$\frac {1}{1+x}$ just satisfies this series.

The Integral Of Series

➀by given that $1+x+x^2+…+x^{n-1}$=$\frac {1}{1-x}$, as $n\rightarrow\infty$
Then, $\int 1+x+x^2+…\operatorname dx$=$\int\frac {1}{1-x}\operatorname dx$
$\Rightarrow x+\frac {1}{2}\cdot x^2+\frac {1}{3}\cdot x^3+…$=$-ln(1-x)$
➁by given that $1$-$x$+$x^2$-$x^3$+$x^4$-$x^5$+…+$(x)^{n-1}$=$\frac {1}{1+x}$, as $n\rightarrow\infty$
then, $\int 1-x+x^2-x^3+x^4-x^5+…\operatorname dx$=$\int\frac {1}{1+x}$
$\Rightarrow x-\frac {1}{2}\cdot x^2+\frac {1}{3}\cdot x^3-\frac {1}{4}\cdot x^4+\frac {1}{5}\cdot x^5…$=$ln(1+x)$
➂$\int 1+x+x^2+…\operatorname dx$+$\int 1-x+x^2-x^3+x^4-x^5+…\operatorname dx$
$\;\;$=$x+\frac {1}{2}\cdot x^2+\frac {1}{3}\cdot x^3+…$+$x-\frac {1}{2}\cdot x^2+\frac {1}{3}\cdot x^3…$
$\;\;$=$2\cdot(x+\frac {1}{3}\cdot x^3+\frac {1}{5}\cdot x^5…)$
$\;\;$=$-ln(1-x)$+$ln(1+x)$
$\;\;$=$ln(1+x)$-$ln(1-x)$
$\;\;$=$ln\frac {1+x}{1-x}$…magic

Convergence Test

[1]Definition of partial sum
The partial sum $S_n$ of the series $a_1$+$a_2$+$a_3$+… stops at $a_n$, then the sum of the first n tems is $S_n$=$a_1$+$a_2$+$a_3$+…+$a_n$.
Thus, $S_n$ is part of the total sum.

Ex. the series $\frac {1}{2}$+$\frac {1}{4}$+$\frac {1}{8}$+…has partial sums:
$S_1$=$\frac {1}{2}$,$S_2$=$\frac {3}{4}$,$S_3$=$\frac {7}{8}$,…,$S_n$=$1-\frac {1}{2^n}$
Hence, $\frac {1}{2}$+$\frac {1}{4}$+$\frac {1}{8}$+...converges to $1$, because $S_n\rightarrow 1$, as $a\rightarrow\infty$.

[2]The limit of partial sum
The sum of a series is the limit of its partial sum, for we can have a new idea that $\sum a_n$=$S$, where $S_n\rightarrow S$.

[3]Theorem: If a series converges($S_n\rightarrow S$), then its terms must approach zero($a_n\rightarrow 0$).

Proof:
By given that $S_n\rightarrow S$, it just converges,
then for $S_{n+1}$ of the $n+1$ terms, $S_{n+1}-S_n\rightarrow 0$ must hold to have $S_{n+1}\rightarrow S_n$, and $S_n\rightarrow S$ by given.
Therefore, the $(n+1)$th term must approaches zero!!

Comparison Test

[1]Comparison test: suppose that $0\le a_n\le b_n$ and $\sum b_n$ converges. Then, $\sum a_n$ converges. A series diverges, if it is above another diverged series.

[2]Comparison test on harmonic series: the harmonic series series $1$+$\frac {1}{2}$+$\frac {1}{3}$+$\frac {1}{4}$+...diverges to infinity.
This section illustrates why by comparing the series with the curve $y$=$\frac {1}{x}$.
➀for the rectangle above the curve, each rectangle area $a_n$=$\frac {1}{n}$, then:
$\sum a_n\ge\int_{1}^{n+1}\frac {1}{x}\operatorname dx$=$ln(n+1)$, where $\lim_{n\rightarrow\infty}ln(n+1)$=$\infty$
➁for the area below the curve, we have it that:
$\frac {1}{2}$+$\frac {1}{3}$+$\frac {1}{4}$+…$<\int_{1}^{n}\frac {1}{x}\operatorname dx$=$ln(n)$, $\lim_{n\rightarrow\infty}ln(n)$=$\infty$
The reason we integrate up to $n$ only is due to that each rectangle at $x$ under the curve counts its area in the reciprocal of its next adjacent $x+1$, totally, $n-1$ rectangles.
Then $1$+$\frac {1}{2}$+$\frac {1}{3}$+$\frac {1}{4}$+…$<(1+ln(n))\rightarrow\infty$, as $n\rightarrow\infty$

Put it all together:
$ln(n+1)$<$1$+$\frac {1}{2}$+$\frac {1}{3}$+$\frac {1}{4}$+…<$1+ln(n)$
$\Rightarrow\infty$<$1$+$\frac {1}{2}$+$\frac {1}{3}$+$\frac {1}{4}$+…<$\infty$, as $a\rightarrow\infty$

By squeeze theorem, $1$+$\frac {1}{2}$+$\frac {1}{3}$+$\frac {1}{4}$+…$\rightarrow\infty$, it diverges!!

Integral Test

[1]If $y(x)$ is decreasing, and $y(n)$ agrees with $a_n$, then $a_1$+$a_2$+$a_3$+… and $\int_{0}^{\infty}y(x)\operatorname dx$ both converge or both diverge.

[2]The p-series $\frac {1}{2^p}$+$\frac {1}{3^p}$+$\frac {1}{4^p}$+$\frac {1}{5^p}$+… converges, if $p>1$.
proof:
➀let $y$=$\frac {1}{x^p}$, then $\frac {1}{n^p}$<$\int_{n-1}^{n}\frac {1}{x^p}\operatorname dx$
➁sum it up, we get:
$\sum_{n=2}^{\infty}\frac {1}{n^p}$<$\int_{1}^{\infty}\frac {1}{x^p}\operatorname dx$
$\;\;\;\;$=$\int_{1}^{\infty}x^{-p}\operatorname dx$
$\;\;\;\;$=$\frac {1}{-p+1}\cdot x\vert_1^\infty$
$\;\;\;\;$=$\frac {1}{1-p}\cdot(\infty^{-p+1}-1)$
➂therefore, this series converges, if $p>1$,
hence, $1$+$\sum_{2}^{\infty}\frac {1}{n^p}$<$1$+$\frac {1}{1-p}\cdot(0-1)$=$\frac {p}{p-1}$

Ratio Test Theorem

If $\frac {a_{n+1}}{a_n}$ approaches a limit $L<1$, the series converges.

proof:
There is a hint that we can compare $a_1$+$a_2$+$a_3$+... with $1$+$x$+$x^2$+...
➀choose $L$<$x$<$1$, then we just have:
$\frac {a_{n+1}}{a_n}$<$x$,$\frac {a_{n+2}}{a_{n+1}}$<$x$,$\frac {a_{n+3}}{a_{n+2}}$<$x$,…
➁multiply each inequality, we have:
$\frac {a_{n+1}}{a_n}$<$x$,$\frac {a_{n+2}}{a_{n}}$<$x^2$,$\frac {a_{n+3}}{a_{n}}$<$^3x$,…
$\Rightarrow a_{n+1}<a_{n}\cdot x$,$a_{n+2}<a_{n}\cdot x^2$,$a_{n+3}<a_{n}\cdot x^{3}$,…
$\Rightarrow a_{n+1}$+$a_{n+2}$+$a_{n+3}$+…<$a_n\cdot(x+x^2+x^3+…)$
$\Rightarrow a_{n+1}$+$a_{n+2}$+$a_{n+3}$+…<$a_n\cdot x\cdot(1+x+x^2+…)$
➂since $x$<$1$, compare with the geometric series, $\sum a_n$ just converges.

Root Test Theorem

If the n term in root $(a_n)^{\frac {1}{n}}$ approaches $L$<$1$, the series just converges.

proof:
➀$\lim_{n\rightarrow\infty}(a_n)^{\frac {1}{n}}\rightarrow L<1$…by given
$\Rightarrow(\lim_{n\rightarrow\infty}(a_n)^{\frac {1}{n}})^{n}\rightarrow L^n<1^n$
$\Rightarrow\lim_{n\rightarrow\infty}(a_n)\rightarrow L^n<1$
➁then for the n+1 term, we just have it hold:
$\lim_{n\rightarrow\infty}(a_{n+1})\rightarrow L^{n+1}<1$
➂$\lim_{n\rightarrow\infty}\frac {a_{n+1}}{a_n}\rightarrow\frac {L^{n+1}}{L^{n}}=L<1$, therefore, this series just converges.

Theorem: Limit Comparison Test

If the ratio $\frac {a_n}{b_n}$ approaches a positive limit $L$, then $\sum a_n$,$\sum b_n$ either diverge or converge.

proof:
$\lim_{n\rightarrow\infty}\frac {a_n}{b_n}\rightarrow L>0$…by given
$\Rightarrow\lim_{n\rightarrow\infty}\frac {a_{n+1}}{b_{n+1}}\rightarrow L>0$, also holds
, which implies that $\sum a_n$,$\sum b_n$ are two very closed series, if one converges, another would surely does; for divergence, it is the same.

Convergence Tests: All Series

[1]Definition of absolute convergence:

The series $\sum a_n$ is absolutely convergent, if $\left|\sum a_n\right|$ converges.

Why? This is because changing from $a_n$ to $\left|a_n\right|$ increases the sum. Thus, the smaller $a_n$ is surely to converge, if $\left|\sum a_n\right|$ converges.

[2]Alternating series:
$a_1$-$a_2$+$a_3$-$a_4$+$a_5$-$a_6$+…, in which the signs alternate between plus and minus.
The series $1$-$\frac {1}{2}$+$\frac {1}{3}$-$\frac {1}{4}$+$\frac {1}{5}$-$\frac {1}{6}$+… converges, why?
➀the terms decreasing to zero
➁it decreasing to zero with alternating signs, that is $a_n\rightarrow 0^{+}$,$a_{n+1}\rightarrow 0^{-}$,
hence, $a_n+(-a_{n+1})\rightarrow 0$, where $a_n>a_{n+1}$, the series converges.

[3]An alternating series $a_1$-$a_2$+$a_3$-$a_4$+$a_5$-$a_6$+...converges, if every $a_{n+1}\le a_{n}$ and $a_{n}\rightarrow 0$.

proof::mjtsai1974

➀by given that $a_n\ge a_{n+1}$,$a_n\rightarrow 0$, as $a\rightarrow\infty$, we define $b_i$=$a_i-a_{i+1}$
➁then, $b_n\rightarrow 0$, as $a\rightarrow\infty$ also holds.
➂and $a_n\ge a_{n+1}$ implies that $\frac {a_{n+1}}{a_n}\rightarrow L_a\le 1$, as $n\rightarrow\infty$.
for $L_a=1$, we have $a_n$-$a_{n+1}$=$b_n$=$0$
for $L_a<1$, we have $b_n\rightarrow 0$ also holds.
➃thus, $b_n$ is either zero or decreasing to zero, and $\frac {b_{n+1}}{b_n}\rightarrow L_b$, as $n\rightarrow\infty$, where $L_b\rightarrow 1$ must hold, if $L_a<1$.

Addendum

➀MIT OCW Calculus On-line Textbook by Gilbert Strange
➁MIT OCW Calculus by Gilbert Strange