Intro to Probability

3. Sequences and Series

3.1 Real-valued Sequences

3.1.1 Introductory Terms

Definition 3.1 (Real-valued sequence): A real-valued sequence is a function f:N→Rf: \N \to \R. We use the notation f=(an)n∈Nf = \sequence a for a real-valued sequence and f(n)=anf(n) = a_n for the values of ff at nn.

In this section we treat only real-valued sequences. Thus, for now, a sequence is a real-valued sequence.

Definition 3.2 (Convergent sequence): Let (an)n∈N\sequence a be a sequence. (an)n∈N\sequence a is said to be convergent if there exists a number a∈Ra \in \R s.t. ∀ε>0  ∃N∈N  ∀n≥N:∣an−a∣<ε \forall \epsilon > 0 \sep \exists N \in \N \sep \forall n \geq N : \abs{a_n - a} < \epsilon
Note: The number aa is called the limit of (an)n∈N\sequence a. We write lim⁡n→∞=a\lim_{n\to\infty} = a or an→n→∞aa_n \convginfty a.
Example (Convergent sequence): Let an=1na_n = \frac{1}{n}. We show that (an)n∈N\sequence a is convergent with limit 00. Let ε>0\epsilon > 0 be an arbitrary strictly positive real number. As we know, for any x∈Rx \in \R there exists n∈Nn \in \N s.t. n>xn > x, we pick N∈NN \in \N s.t. N>1εN > \frac{1}{\epsilon}. Then, for any n≥Nn \geq N, ∣an−0∣=1n≤1N<ε\abs{a_n - 0} = \frac{1}{n} \leq \frac{1}{N} < \epsilon.
Proposition 3.3 (Uniqueness of limit): If (an)n∈N\sequence a is convergent, then its limit aa is unique.

3.1.2 Results on Real-valued Sequences

Definition 3.4 (Bounded sequence): A sequence (an)n∈N\sequence a is said to be
  • bounded if there exists a real number M>0M > 0 s.t. ∀n∈N:∣an∣≤M\forall n \in \N : \abs{a_n} \leq M.
  • bounded from below if there exists a real number MM s.t. ∀n∈N:an≥M\forall n \in \N : a_n \geq M.
  • bounded from above if there exists a real number MM s.t. ∀n∈N:an≤M\forall n \in \N : a_n \leq M.
Proposition 3.5 (Convergent implies bounded): If (an)n∈N\sequence a is convergent, then it is bounded.
Definition 3.6 (Increasing, decreasing sequence): A sequence (an)n∈N\sequence a is
  • increasing if ∀n∈N:an≤an+1\forall n \in \N : a_n \leq a_{n+1}.
  • decreasing if ∀n∈N:an≥an+1\forall n \in \N : a_n \geq a_{n+1}.
  • monotonic if it is either increasing or decreasing.
Note: If (an)n∈N\sequence a is increasing with limit aa we write an↑aa_n \uparrow a, if it is decreasing with limit aa we write an↓aa_n \downarrow a.
Proposition 3.7 (Bounded, monotonic implies convergent): A bounded and monotonic sequence (an)n∈N\sequence a is convergent.
Example (Bounded, decreasing implies convergent): Let ∣r∣<1\abs{r} < 1, and consider an=∣r∣na_n = \abs{r}^n, n∈Nn \in \N. For any n∈Nn \in \N, an<1a_n < 1 and ∣r∣n+1=∣r∣n∣r∣≤∣r∣n\abs{r}^{n+1} = \abs{r}^n \abs{r} \leq \abs{r}^n. Thus, (an)n∈N\sequence a is bounded and decreasing and hence there exists an LL s.t. lim⁡n→∞an=L\lim_{n\to\infty} a_n = L.
Proposition 3.8 (Arithmetic of limits): Let (an)n∈N\sequence a and (bn)n∈N\sequence b be two convergent sequences s.t. an→n→∞aa_n \convginfty a and bn→n→∞bb_n \convginfty b. The following properties hold:
  1. an+bn→n→∞a+ba_n + b_n \convginfty a+b
  2. anbn→n→∞aba_n b_n \convginfty ab
  3. anbn→n→∞ab\frac{a_n}{b_n} \convginfty \frac{a}{b} if b≠0b\neq 0
Proposition 3.9 (Order persists on converging limits): Let (an)n∈N\sequence a and (bn)n∈N\sequence b be two convergent sequences s.t. an→n→∞aa_n \convginfty a and bn→n→∞bb_n \convginfty b.
  • If ∀n∈N:an≤bn\forall n \in \N : a_n \leq b_n, then a≤ba \leq b.
  • If ∀n∈N:an≥bn\forall n \in \N : a_n \geq b_n, then a≥ba \geq b.
Proposition 3.10 (Limit of sandwiched sequence): Let (an)n∈N\sequence a and (bn)n∈N\sequence b be two convergent sequences that converge to the same limit, i.e., an→n→∞aa_n \convginfty a and bn→n→∞ab_n \convginfty a. Let (cn)n∈N\sequence c be another sequence which is s.t. ∀n∈N:an≤cn≤bn\forall n \in \N : a_n \leq c_n \leq b_n. Then, cn→n→∞ac_n \convginfty a.
Example (Limit of rnr^n in unit disk): TODO

3.1.3 On Diverging Sequences

Definition 3.11 (Diverging sequence): Let (an)n∈N\sequence a be a sequence. We write:
  • (an)n∈N→n→∞∞\sequence a \convginfty \infty if ∀M∈R  ∃N∈N  ∀n≥N:an≥M\forall M \in \R \sep \exists N \in \N \sep \forall n \geq N : a_n \geq M
  • (an)n∈N→n→∞−∞\sequence a \convginfty -\infty if ∀M∈R  ∃N∈N  ∀n≥N:an≤M\forall M \in \R \sep \exists N \in \N \sep \forall n \geq N : a_n \leq M
If (an)n∈N→n→∞∞\sequence a \convginfty \infty or (an)n∈N→n→∞−∞\sequence a \convginfty -\infty, we say that (an)n∈N\sequence a diverges.
Note: We refer to lim⁡n→∞an\liminfty a_n as well-defined if lim⁡n→∞an∈R‾\liminfty a_n \in \Rext, i.e. the sequnece converges or diverges. Notice that if lim⁡n→∞an\liminfty a_n exists it is unique.
Proposition 3.12 (Diverging monotonic sequences): Let (an)n∈N\sequence a be a monotonic sequence. If (an)n∈N\sequence a diverges
  • and is increasing, then it diverges to an↑∞a_n \uparrow \infty.
  • and is decreasing, then it diverges to an↓−∞a_n \downarrow -\infty.
Note: If (an)n∈N\sequence a is monotnoic, then lim⁡n→∞an\liminfty a_n always exists.

We can now formulate a more general proposition on the order of limits, not necessarily requiring convergence.

Proposition 3.13 (Order persists on limits): Let (an)n∈N\sequence a and (bn)n∈N\sequence b be two monotonic sequences, either both increasing or both decreasing, with ∀n∈N:an≤bn\forall n \in N : a_n \leq b_n, then lim⁡n→∞an≤lim⁡n→∞bn\liminfty a_n \leq \liminfty b_n.

3.2 Series

Definition 3.14 (Series): Let (an)n∈N\sequence a be a sequence. The series ∑n∈Nan=∑n=1∞an\sumN a_n = \sum_{n = 1}^\infty a_n is understood as the sequence (sn)n∈N\sequence s.
Note: If lim⁡n→∞sn\liminfty s_n exists we write lim⁡n→∞sn=∑n∈Nan\liminfty s_n = \sumN a_n for the limit.
Proposition 3.15 (Positive series): Let ∑n∈Nan\sumN a_n be a series where ∀i∈N:ai≥0\forall i \in \N : a_i \geq 0, then either ∑n∈Nan<∞\sumN a_n < \infty or ∑n∈Nan=∞\sumN a_n = \infty.
Example: TODO
Proposition 3.16 (Sandwiched converging series): Let ∑n∈Nan\sumN a_n be a series and ∑n∈Nbn\sumN b_n be a series s.t. bn≥0b_n \geq 0 for any n∈Nn \in \N and ∑n∈Nbn<∞\sumN b_n < \infty. Suppose that ∀n∈N:∣an∣≤bn\forall n \in \N : \abs{a_n} \leq b_n, then ∑n∈Nan<∞\sumN a_n < \infty.
Proposition 3.17 (Doubly indexed series): Let I,J⊆N\setI, \setJ \subset \N and f:I×J→Rf : \setI \times \setJ \to \R. Set ai,j=f(i,j)a_{i,j} = f(i,j). Suppose that either ∀i,j:ai,j≥0\forall i,j : a_{i,j} \geq 0 or ∑(i,j)∈I×J∣ai,j∣<∞\sum_{(i,j) \in \setI \times \setJ} \abs{a_{i,j}} < \infty. Then ∑(i,j)∈I×Jai,j=∑i∈I∑j∈Jai,j=∑j∈J∑i∈Iai,j \sum_{(i,j) \in \setI \times \setJ} a_{i,j} = \sum_{i \in \setI} \sum_{j \in \setJ} a_{i,j} = \sum_{j \in \setJ} \sum_{i \in \setI} a_{i,j} exists and we are allowed to change the order of summation.
Note: If I=J\setI = \setJ, we use the notation ∑(i,j)∈I2ai,j=∑i,j∈Iai,j\sum_{(i,j) \in \setI^2} a_{i,j} = \sum_{i,j \in \setI} a_{i,j} for the sum over all the pairs (i,j)∈I2(i,j) \in \setI^2.

3.3 Study of Convergence

3.3.1 Subsequences

We remain in the setting of the previous Section, i.e. any sequence (an)n∈N\sequence a is a real-valude sequence.

Definition 3.18 (Subsequence): Let f=(an)n∈Nf = \sequence a be a sequence. A subsequence of (an)n∈N\sequence a is a new sequence g=(bn)n∈Ng = \sequence b where g=f∘sg = f \circ s with s:N→Ns: \N \to \N s.t. s(n)<s(n+1)s(n) < s(n+1).
Note: For any n∈Nn \in \N we have bn=g(n)=f(s(n))=as(n)b_n = g(n) = f(s(n)) = a_{s(n)}.
Example (Subsequence): Let an=1na_n = \frac{1}{n}, then (bn)n∈N\sequence{b} with bn=a2nb_n = a_{2n} is a subsequence.
Theorem 3.19 (Bolzano-Weierstrass): Let (an)n∈N\sequence a be a sequence. If (an)n∈N\sequence a is bounded, then there exists a subsequence of (an)n∈N\sequence a which is convergent.
Example (Bolzano-Weierstrass): Let an=(−1)na_n = (-1)^n, n∈Nn \in \N. We have seen that (an)n∈N\sequence a is not convergent. However, (bn)n∈N\sequence b with bn=a2nb_n = a_{2n} is convergent with limit bn→n→∞1b_n \convginfty 1.
Definition 3.20 (Accumulation point): Let (an)n∈N\sequence a be a sequence and (bn)n∈N\sequence b be a subsequence s.t. lim⁡n→∞bn=b\liminfty b_n = b. Then bb is said to be an accumulation point of (an)n∈N\sequence a.
Example (Accumulation point): Let an=(−1)na_n = (-1)^n, then (an)n∈N\sequence a has two accumulation points, −1-1 and 11.
Proposition 3.21 (Points around accumulation): Let bb be an accumulation point (an)n∈N\sequence a, then for any ε>0\epsilon > 0 there are infintely many ana_n s.t. an∈(a−ε,a+ε)a_n \in (a - \epsilon, a + \epsilon).
Proposition 3.22 (Convergent series has one accumulation): Let (an)n∈N\sequence a be a convergent sequence with limit aa, then every subsequence of (an)n∈N\sequence a converges to a. That is, a convergent sequence has only one accumulation point.
Proposition 3.23 (Diverging subsequence): Let (an)n∈N\sequence a be a sequence.
  • If (an)n∈N\sequence a is increasing and there exists a subsequence (bn)n∈N\sequence b s.t. bn→n→∞∞b_n \convginfty \infty, then an→n→∞∞a_n \convginfty \infty.
  • If (an)n∈N\sequence a is decreasing and there exists a subsequence (bn)n∈N\sequence b s.t. bn→n→∞−∞b_n \convginfty -\infty, then an→n→∞−∞a_n \convginfty -\infty.
Example: TODO

3.3.2 Limit Inferior and Limit superior

Note: We use the notation inf⁡n∈Nan=inf⁡{an | n∈N}\infN a_n = \inf \set{a_n \mid n \in \N} and sup⁡n∈Nan=sup⁡{an | n∈N}\supN a_n = \sup \set{a_n \mid n \in \N}.
Proposition 3.24 (inf, sup of unbounded sequences): Let (an)n∈N\sequence a be a sequence.
  • If (an)n∈N\sequence a is not bounded from below, then inf⁡n∈Nan=−∞\infN a_n = -\infty.
  • If (an)n∈N\sequence a is not bounded from above, then sup⁡n∈Nan=∞\supN a_n = \infty.
Note: We use the notation inf⁡k≥nak=inf⁡{ak | k≥n}\infkn a_k = \inf \set{a_k \mid k \geq n} and sup⁡k≥nak=sup⁡{ak | k≥n}\supkn a_k = \sup \set{a_k \mid k \geq n}.
Proposition 3.25 (Limit of inf and sup sequences): Let (an)n∈N\sequence a be a sequence.
  • If (an)n∈N\sequence a is bounded from below, the sequence (mn)n∈N\sequence m with mn=inf⁡k≥nakm_n = \infkn a_k is increasing with lim⁡n→∞mn=sup⁡n∈Nmn=sup⁡n∈Ninf⁡k≥nak \liminfty m_n = \supN m_n = \supN \infkn a_k
  • If (an)n∈N\sequence a is bounded from above, the sequence (Mn)n∈N\sequence M with Mn=sup⁡k≥nakM_n = \supkn a_k is decreasing with lim⁡n→∞Mn=inf⁡n∈NMn=inf⁡n∈Nsup⁡k≥nak \liminfty M_n = \infN M_n = \infN \supkn a_k
Definition 3.26 (Limit inferior): The limit inferior of (an)n∈N\sequence a is lim inf⁡n→∞an=sup⁡n∈Ninf⁡k≥nak \liminfinfty a_n = \supN \infkn a_k if (an)n∈N\sequence a is bounded from below and lim inf⁡n→∞an=−∞\liminfinfty a_n = -\infty otherwise.
Definition 3.27 (Limit superior): The limit superior of (an)n∈N\sequence a is lim sup⁡n→∞an=inf⁡n∈Nsup⁡k≥nak \limsupinfty a_n = \infN \supkn a_k if (an)n∈N\sequence a is bounded from above and lim sup⁡n→∞an=∞\limsupinfty a_n = \infty otherwise.
Proposition 3.28 (Order of liminf and limsup): Let (an)n∈N\sequence a be a sequence. We have that lim inf⁡n→∞an≤lim sup⁡n→∞an\liminfinfty a_n \leq \limsupinfty a_n.

The following proposition gives another characterization of convergence.

Proposition 3.29 (Convergence with liminf and limsup): Let (an)n∈N\sequence a be a bounded sequence. Then (an)n∈N\sequence a is convergent with limit aa if and only if lim inf⁡n→∞an=a=lim sup⁡n→∞an \liminfinfty a_n = a = \limsupinfty a_n

This characterization is useful as lim inf⁡\liminf and lim sup⁡\limsup are defined without using limits and solely by using inf⁡\inf and sup⁡\sup which may be easier to work with. A more general statement that includes diverging sequences is the following.

Theorem 3.30 (Existence of limit): Let (an)n∈N\sequence a be a sequence. Then the limit of the sequence exists with lim⁡n→∞an=a∈R‾\liminfty a_n = a \in \Rext if and only if lim inf⁡n→∞an=a=lim sup⁡n→∞an \liminfinfty a_n = a = \limsupinfty a_n

3.4 Vector-valued Sequences

The previous section on real-valued sequences can easily be extended to the notion of vector-valued sequences.

Definition 3.31 (Vector-valued sequence): An Rk\R^k-values sequence is a function f:N→Rkf : \N \to \R^k, where we write f(n)=(a1,n,…,ak,n)=anf(n) = (a_{1,n}, \ldots, a_{k,n}) = \dvec a_n for ff evaluated at an instance n∈Nn \in \N.
Note: We rely on the notation f=(an)n∈Nf = \sequence{\dvec a} for a real vector-valued sequence.

We notice that the coordinate functions fi=(ai,n)i,n∈nf_i = \sequence*{a}{i,n}{n} of an Rk\R^k-valued sequence (an)n∈N\sequence{\dvec a} are real-valued sequences. If k=1k=1 then (an)n∈N\sequence a is a real-valued sequence. Upon the Euclidean metric ∥x−y∥\norm{\dvec x - \vy} we can introduce the notion of convergence for Rk\R^k-valued sequences.

Definition 3.32 (Convergence of vector-valued sequences): (an)n∈N\sequence{\dvec a} is said to be convergent if there exists an a∈Rk\dvec a \in \R^k s.t. for any ε>0\epsilon > 0 there exists N∈NN \in \N s.t. ∥an−a∥<ε\norm{\dvec a_n - \dvec a} < \epsilon for any n≥Nn \geq N.
Note: We write an→n→∞a\dvec a_n \convginfty \dvec a to indicate that (an)n∈N\sequence{\dvec a} converges to a\dvec a.

The following result shows that in order to prove that an Rk\R^k-valued sequence converges, it is enough to study the convergence of the individual coordinates.

Proposition 3.33 (Convergence of coordinates implies convergence): Let (an)n∈N\sequence{\dvec a} and a∈R\dvec a \in \R. Then an→n→∞a\dvec a_n \convginfty \dvec a if and only if ∀i∈{1,…,k}:ai,n→n→∞ai\forall i \in \set{1, \ldots, k} : a_{i,n} \convginfty a_i.

We point out that the notion of convergence enables a characterization of continuity known as the sequence criterion.

Proposition 3.34 (Sequence criterion for continuity): Let E⊆RmE \subset \R^m, f:E→Rkf : E \to \R^k and x∈E\dvec x \in E. Then ff is continuous in x\dvec x if and only if for any Rm\R^m-valued sequence (xn)n∈N\sequence{\dvec x}, xn∈E\dvec x_n \in E, it follows that xn→n→∞x\dvec x_n \convginfty \dvec x implies f(xn)→n→∞f(x)f(\dvec x_n) \convginfty f(\dvec x).

We recall some classical examples of continuos functions.

Example (Continuous functions): The following functions are continuous
  • f:Rk→Rf : \R^k \to \R, f(x)=∑i=1kxkf(\dvec x) = \sum_{i=1}^k x_k
  • g:Rk→Rg : \R^k \to \R, g(x)=∏i=1kxkg(\dvec x) = \prod_{i=1}^k x_k
  • h:R∖{0}→R∖{0}h : \R \setminus \set{0} \to \R \setminus \set{0}, h(x)=1xh(x) = \frac{1}{x}

3.5 Sequences in the Extended Real Numbers

Definition 3.35 (Extended real-valued sequence): A sequence (an)n∈N\sequence a with values in the extended real numbers is a sequence that can obtain any values in R‾\Rext.
Note: Let (an)n∈N\sequence a be a sequence with values in R‾\Rext, then the definitions of boundedness, monotony, limit inferior and limit superior also apply to (an)n∈N\sequence a.
Example (Extended real-valued sequence): Let an={1if n is odd∞if n is even a_n = \begin{cases} 1 & \text{if } n \text{ is odd} \\ \infty & \text{if } n \text{ is even} \end{cases}

Regarding convergence, we make the following definition.

Definition 3.36 (Convergence of extended real-valued sequences): Let (an)n∈N\sequence a be a sequence with values in R‾\Rext. Then (an)n∈N\sequence a is said to be convergent with lim⁡n→∞an=a\liminfty a_n = a if and only if lim inf⁡n→∞an=alim sup⁡n→∞an\liminfinfty a_n = a \limsupinfty a_n.
Note: Notice that in contrast to real-valued sequences, if lim⁡n→∞an=∞\liminfty a_n = \infty or lim⁡n→∞an=−∞\liminfty a_n = -\infty then (an)n∈N\sequence a is said to be convergent instead of divergent. In fact, divergence does not exist for sequences in the extended real numbers.
Example (Non-convergence): Let again an={1if n is odd∞if n is even a_n = \begin{cases} 1 & \text{if } n \text{ is odd} \\ \infty & \text{if } n \text{ is even} \end{cases} then lim inf⁡n→∞an=1\liminfinfty a_n = 1 and lim sup⁡n→∞an=∞\limsupinfty a_n = \infty, hence (an)n∈N\sequence a can not be convergent.

3.6 On Sequences of Functions

Definition 3.37 (Sequence of functions): Let A\setA and B\setB be sets. A sequence of functions is a collection of functions gn:A→Bg_n : \setA \to \setB for n∈Nn \in \N.

We primarily focus on the case where B=Rk\setB = \R^k for k≥1k \geq 1 or B=R‾\setB = \Rext.

Definition 3.38 (Pointwise inf and sup): Let gn:A→R‾g_n : \setA \to \Rext be a sequence of functions. Then, given I⊆N\setI \subset \N, we define the function inf⁡n∈Ign:A→R‾\inf_{n \in \setI} g_n : \setA \to \Rext as inf⁡n∈Ign(x)=inf⁡{y∈R‾ | ∃n∈I:gn(x)=y} \inf_{n \in \setI} g_n(x) = \inf \set{y \in \Rext \mid \exists n \in \setI : g_n(x) = y} and sup⁡n∈Ign:A→R‾\sup_{n \in \setI} g_n : \setA \to \Rext as sup⁡n∈Ign(x)=sup⁡{y∈R‾ | ∃n∈I:gn(x)=y} \sup_{n \in \setI} g_n(x) = \sup \set{y \in \Rext \mid \exists n \in \setI : g_n(x) = y}
Definition 3.39 (Pointwise limit): Let gn:A→R‾g_n : \setA \to \Rext be a sequence of functions. gng_n has the limit lim⁡n→∞gn(x)\liminfty g_n(x) in the point x∈Ax \in \setA if and only if lim inf⁡n→∞gn(x)=lim⁡n→∞gn(x)=lim sup⁡n→∞gn(x) \liminfinfty g_n(x) = \liminfty g_n(x) = \limsupinfty g_n(x)
Note: We say that the sequence of functions gn:A→R‾g_n : \setA \to \Rext converges pointwise on a set C⊆A\setC \subset \setA if ∀x∈C:lim⁡n→∞gn(x)∈R\forall x \in \setC : \liminfty g_n(x) \in \R.
Example (Pointwise non-convergence): Let gn:[0,π]→Rg_n : [0, \pi] \to \R with gn(x)=cos⁡(nx)g_n(x) = \cos(nx). We note lim inf⁡n→∞g(π)=−1\liminfinfty g(\pi) = -1 and lim sup⁡n→∞gn(π)=1\limsupinfty g_n(\pi) = 1. Hence, gng_n does not converge pointwise on [0,π][0,\pi].