Prev Next

Michael Oberguggenberger and Alexander OstermannAnalysis for Computer ScientistsUndergraduate Topics in Computer Sciencehttps://doi.org/10.1007/978-3-319-91155-7_5

5. Sequences and Series

Michael Oberguggenberger¹ and Alexander Ostermann¹

(1)

University of Innsbruck, Innsbruck, Austria

Michael Oberguggenberger (Corresponding author)

Email: michael.oberguggenberger@uibk.ac.at

Alexander Ostermann

Email: alexander.ostermann@uibk.ac.at

The concept of a limiting process at infinity is one of the central ideas of mathematical analysis. It forms the basis for all its essential concepts, like continuity, differentiability, series expansions of functions, integration, etc. The transition from a discrete to a continuous setting constitutes the modelling strength of mathematical analysis. Discrete models of physical, technical or economic processes can often be better and more easily understood, provided that the number of their atoms—their discrete building blocks—is sufficiently big, if they are approximated by a continuous model with the help of a limiting process. The transition from difference equations for biological growth processes in discrete time to differential equations in continuous time are examples for that, as is the description of share prices by stochastic processes in continuous time. The majority of models in physics are field models, that is, they are expressed in a continuous space and time structure. Even though the models are discretised again in numerical approximations, the continuous model is still helpful as a background, for example for the derivation of error estimates.

The following sections are dedicated to the specification of the idea of limiting processes. This chapter starts by studying infinite sequences and series, gives some applications and covers the corresponding notion of a limit. One of the achievements which we especially emphasise is the completeness of the real numbers. It guarantees the existence of limits for arbitrary monotonically increasing bounded sequences of numbers, the existence of zeros of continuous functions, of maxima and minima of differentiable functions, of integrals, etc. It is an indispensable building block of mathematical analysis.

5.1 The Notion of an Infinite Sequence

Definition 5.1

Let X be a set. An (infinite) sequence with values in X is a mapping from $\mathbb N$ to X.

Thus each natural number n (the index) is mapped to an element $$a_n$$

of X (the nth term of the sequence). We express this by using the notation

$(a_n)_{n \ge 1} = (a_1, a_2, a_3,\ldots ).$

In the case of $X = \mathbb R$ one speaks of real-valued sequences, if $X = \mathbb {C}$ of complex-valued sequences, if $X = \mathbb R^m$ of vector-valued sequences. In this section we only discuss real-valued sequences.

Sequences can be added

$(a_n)_{n \ge 1} + (b_n)_{n \ge 1} = (a_n + b_n)_{n \ge 1}$

and multiplied by a scalar factor

$\lambda (a_n)_{n \ge 1} = (\lambda a_n)_{n \ge 1}.$

These operations are performed componentwise and endow the set of all real-valued sequences with the structure of a vector space. The graph of a sequence is visualised by plotting the points $(n, a_n), n = 1,2,3,\ldots$ in a coordinate system, see Fig. 5.1.

images/215236_2_En_5_Chapter/215236_2_En_5_Fig1_HTML.gif — Fig. 5.1
Graph of a sequence

Experiment 5.2

The M-file mat05_1a.m offers the possibility to study various examples of sequences which are increasing/decreasing, bounded/unbounded, oscillating, convergent. For a better visualisation the discrete points of the graph of the sequence are often connected by line segments (exclusively for graphical purpose)—this is implemented in the M-file mat05_1b.m. Open the applet Sequences and use it to illustrate the sequences given in the M-file mat05_1a.m.

Sequences can either be defined explicitly by a formula, for instance

or recursively by giving a starting value and a rule how to calculate a term from the preceding one,

$a_1 = 1,\quad a_{n+1} = 2a_n.$

The recursion can also involve several previous terms at a time.

Example 5.3

A discrete population model which goes back to Verhulst¹ (limited growth) describes the population $$x_n$$

at the point in time n (using time intervals of length 1) by the recursive relation

$x_{n+1} = x_n + \beta x_n (L - x_n).$

Here $\beta$ is a growth factor and L the limiting population, i.e. the population which is not exceeded in the long-term (short-term overruns are possible, however, lead to immediate decay of the population). Additionally one has to prescribe the initial population $$x_1 = A$$

. According to the model the population increase $x_{n+1} - x_n$ during one time interval is proportional to the existing population and to the difference to the population limit. The M-file mat05_2.m contains a MATLAB function, called as

${\texttt {x = mat05\_2(A,beta, N)}}$

which computes and plots the first N terms of the sequence $x = (x_1,\ldots , x_N)$ . The initial value is A, the growth rate $\beta$ ; L was set to $$L = 1$$

. Experiments with $$A = 0.1$$

and $\beta = 0.5$ , $\beta = 1$ , $\beta = 2$ , $\beta = 2.5$ , $\beta = 3$ show convergent, oscillating and chaotic behaviour of the sequence, respectively.

Below we develop some concepts which help to describe the behaviour of sequences.

Definition 5.4

A sequence $(a_n)_{n \ge 1}$ is called monotonically increasing, if

$n \le m \quad \Rightarrow \quad a_n \le a_m;$

$(a_n)_{n \ge 1}$ is called monotonically decreasing , if

$n \le m \quad \Rightarrow \quad a_n \ge a_m;$

$(a_n)_{n \ge 1}$ is called bounded from above , if

$\exists T \in \mathbb R\ \; \forall n \in \mathbb N\, :\, a_n \le T.$

We will show in Proposition 5.13 below that the set of upper bounds of a bounded sequence has a smallest element. This least upper bound $$T_0$$

is called the supremum of the sequence and denoted by

$T_0 = \sup _{n \in \mathbb N} a_n.$

The supremum is characterised by the following two conditions:

(a)

$a_n \le T_0$ for all $n \in \mathbb N$ ;
(b)

if T is a real number and $a_n \le T$ for all $n \in \mathbb N$ , then $T \ge T_0$ .

Note that the supremum itself does not have to be a term of the sequence. However, if this is the case, it is called maximum of the sequence and denoted by

$T_0 = \max _{n \in \mathbb N} a_n.$

A sequence has a maximum $$T_0$$

if the following two conditions are fulfilled:

(a)

$a_n \le T_0$ for all $n \in \mathbb N$ ;
(b)

there exists at least one $m \in \mathbb N$ such that .

In the same way, a sequence $(a_n)_{n \ge 1}$ is called bounded from below, if

$\exists S \in \mathbb R\ \;\forall n \in \mathbb N\,: \, S \le a_n.$

The greatest lower bound is called infimum (or minimum , if it is attained by a term of the sequence).

Experiment 5.5

Investigate the sequences produced by the M-file mat05_1a.m with regard to the concepts developed above.

images/215236_2_En_5_Chapter/215236_2_En_5_Fig2_HTML.gif — Fig. 5.2
Convergence of a sequence

As mentioned in the introduction to this chapter, the concept of convergence is a central concept of mathematical analysis. Intuitively it states that the terms of the sequence $(a_n)_{n\ge 1}$ approach a limit a with growing index n. For example, in Fig. 5.2 with $$a = 0.8$$

one has

$|a - a_n|< 0.2 \ \;\text {from}\ \; n = 6, \quad |a - a_n| < 0.05 \ \; \text {from} \ \;n = 21.$

For a precise definition of the concept of convergence we first introduce the notion of an $\varepsilon$ -neighbourhood of a point $a \in \mathbb R$ ( $\varepsilon > 0$ ):

$U_{\varepsilon } (a) = \{x \in \mathbb R\;;\; |a - x| < \varepsilon \} = (a-\varepsilon , a+\varepsilon ).$

We say that a sequence $(a_n)_{n \ge 1}$ settles in a neighbourhood $U_{\varepsilon } (a)$ , if from a certain index $n(\varepsilon )$ on all subsequent terms $$a_n$$

of the sequence lie in $U_{\varepsilon } (a)$ .

Definition 5.6

The sequence $(a_n)_{n \ge 1}$ converges to a limit a if it settles in each $\varepsilon$ -neighbourhood of a.

These facts can be expressed in quantifier notation as follows:

$\forall \varepsilon > 0 \ \ \exists n(\varepsilon ) \in \mathbb N\ \ \forall n \ge n (\varepsilon )\,: \ |a - a_n| < \varepsilon .$

If a sequence $(a_n)_{n \ge 1}$ converges to a limit a, one writes

$a = \lim _{n\rightarrow \infty } a_n \qquad \text{ or } \qquad a_n \rightarrow a\ \;\text{ as }\ \; n \rightarrow \infty .$

In the example of Fig. 5.2 the limit a is indicated as a dotted line, the neighbourhood $U_{0.2} (a)$ as a strip with a dashed boundary line and the neighbourhood $U_{0.05} (a)$ as a strip with a solid boundary line.

In the case of convergence the limit can be interchanged with addition, multiplication and division (with the exception of zero), as expected.

Proposition 5.7

(Rules of calculation for limits) If the sequences $(a_n)_{n \ge 1}$ and $(b_n)_{n \ge 1}$ are convergent then the following rules hold:

$\begin{aligned} \lim _{n \rightarrow \infty } (a_n + b_n)= & {} \lim _{n \rightarrow \infty } a_n + \lim _{n \rightarrow \infty } b_n\\ \lim _{n \rightarrow \infty } (\lambda a_n)= & {} \lambda \lim _{n \rightarrow \infty } a_n \qquad (\text {for } \lambda \in \mathbb R)\\ \lim _{n \rightarrow \infty } (a_n b_n)= & {} (\lim _{n \rightarrow \infty } a_n) (\lim _{n \rightarrow \infty } b_n)\\ \lim _{n \rightarrow \infty } (a_n/b_n)= & {} (\lim _{n \rightarrow \infty } a_n)/(\lim _{n \rightarrow \infty } b_n) \qquad ({ if } \lim _{n \rightarrow \infty } b_n \ne 0) \end{aligned}$

Proof

The verification of these trivialities is left to the reader as an exercise. The proofs are not deep, but one has to carefully pick the right approach in order to verify the conditions of Definition 5.6. In order to illustrate at least once how such proofs are done, we will show the statement about multiplication. Assume that

$\lim _{n \rightarrow \infty } a_n = a \quad \text{ and } \quad \lim _{n \rightarrow \infty } b_n = b.$

Let $\varepsilon > 0$ . According to Definition 5.6 we have to find an index $n(\varepsilon ) \in \mathbb N$ satisfying

$\begin{aligned} |ab - a_nb_n| < \varepsilon \end{aligned}$

for all $n \ge n(\varepsilon )$ . Due to the convergence of the sequence $(a_n)_{n \ge 1}$ we can first find an $n_1(\varepsilon ) \in \mathbb N$ so that $|a - a_n| \le 1$ for all $n \ge n_1(\varepsilon )$ . For these n it also applies that

$|a_n| = |a_n - a + a| \le 1 + |a|.$

Furthermore, we can find $n_2(\varepsilon ) \in \mathbb N$ and $n_3(\varepsilon ) \in \mathbb N$ which guarantee that

$|a - a_n|< \frac{\varepsilon }{2\max (|b|, 1)} \quad \text{ and } \quad |b - b_n| < \frac{\varepsilon }{2(1+|a|)}$

for all $n \ge n_2(\varepsilon )$ and $n \ge n_3(\varepsilon )$ , respectively. It thus follows that

$\begin{aligned} |ab - a_nb_n|= & {} |(a-a_n)b + a_n(b-b_n)| \le |a-a_n||b| + |a_n||b-b_n|\\\le & {} |a-a_n||b| + (|a|+1)|b-b_n| \le \frac{\varepsilon }{2} + \frac{\varepsilon }{2} \le \varepsilon \end{aligned}$

for all $n \ge n(\varepsilon )$ with $n(\varepsilon ) = \max (n_1(\varepsilon ), n_2(\varepsilon ), n_3(\varepsilon ))$ . This is the statement that was to be proven. $\square$

The important ideas of the proof were: Splitting in two summands with the help of the triangle inequality (see Exercise 2 of Chap. 1); bounding $$|a_n|$$ by $$1+|a|$$ using the assumed convergence; upper bounds for the terms $$|a-a_n|$$ and $$|b-b_n|$$ by fractions of $\varepsilon$ (again possible due to the convergence) so that the summands together stay less than $\varepsilon$ . All elementary proofs of convergence in mathematical analysis proceed in a similar way.

Real-valued sequences with terms that increase to infinity with growing index n have no limit in the sense of the definition given above. However, it is practical to assign them the symbol $\infty$ as an improper limit.

Definition 5.8

A sequence $(a_n)_{n \ge 1}$ has the improper limit $\infty$ if it has the property of unlimited increase

$\forall T \in \mathbb R\ \ \exists n(T) \in \mathbb N\ \ \forall n \ge n(T)\,: \ a_n \ge T.$

In this case one writes

$\lim _{n \rightarrow \infty } a_n = \infty .$

In the same way one defines

$\lim _{n \rightarrow \infty } b_n = - \infty , \quad \text {if}\quad \lim _{n \rightarrow \infty }(-b_n) = \infty .$

Example 5.9

We consider the geometric sequence $(q^n)_{n \ge 1}$ . It obviously holds that

$\begin{aligned} \lim _{n \rightarrow \infty } q^n&= \ 0,&\quad \text {if} \ |q| < 1,\\ \lim _{n \rightarrow \infty } q^n&\ \,= \ \infty ,&\quad \text {if} \ q > 1,\\ \lim _{n \rightarrow \infty } q^n&= \ 1,&\quad \text {if} \ q = 1. \end{aligned}$

For $q \le - 1$ the sequence has no limit (neither proper nor improper).

5.2 The Completeness of the Set of Real Numbers

As remarked in the introduction to this chapter, the completeness of the set of real numbers is one of the pillars of real analysis. The property of completeness can be expressed in different ways. We will use a simple formulation which is particularly helpful in many applications.

Proposition 5.10

(Completeness of the set of real numbers) Each monotonically increasing sequence of real numbers that is bounded from above has a limit (in $\mathbb R$ ).

Proof

Let $(a_n)_{n \ge 1}$ be a monotonically increasing, bounded sequence. First we prove the theorem in the case that all terms $$a_n$$

are non-negative. We write the terms as decimal numbers

$a_n = A^{(n)}. \alpha _1^{(n)} \alpha _2^{(n)} \alpha _3^{(n)}\ldots$

with $A^{(n)}\! \in \mathbb N_0$ , $\alpha _j^{(n)}\! \in \{0,1,\ldots , 9\}$ . By assumption there is a bound $T \ge 0$ so that $a_n \le T$ for all n. Therefore, also $A^{(n)} \le T$ for all n. But the sequence $(A^{(n)})_{n \ge 1}$ is a monotonically increasing, bounded sequence of integers and therefore must eventually reach its least upper bound A (and stay there). In other words, there exists $n_0\in \mathbb N$ such that

$A^{(n)} = A \quad \text {for all}\ n \ge n_0.$

Thus we have found the integer part of the limit a to be constructed:

$a = A.\;\ldots$

Let now $\alpha _1 \in \{0,\ldots , 9\}$ be the least upper bound for $\alpha _1^{(n)}$ . As the sequence is monotonically increasing there is again an $n_1 \in \mathbb N$ with

$\alpha _1^{(n)} = \alpha _1 \quad \text {for all} \ n \ge n_1$

and consequently

$a = A. \alpha _1\ldots$

Let now $\alpha _2 \in \{0,\ldots , 9\}$ be the least upper bound for $\alpha _2^{(n)}$ . There is an $n_2 \in \mathbb N$ with

$\alpha _2^{(n)} = \alpha _2 \quad \text {for all}\ n \ge n_2$

and consequently

$a = A. \alpha _1 \alpha _2\ldots$

Successively one defines a real number

$a = A. \alpha _1 \alpha _2 \alpha _3 \alpha _4\ldots$

in that way. It remains to show that $a = \lim _{n \rightarrow \infty } a_n$ . Let $\varepsilon > 0$ . We first choose $j \in \mathbb N$ so that $10^{-j} < \varepsilon$ . For $n \ge n_j$

$a - a_n = 0.000 \ldots 0 \,\alpha _{j + 1}^{(n)} \ \alpha _{j + 2}^{(n)}\ldots ,$

since the first j digits after the decimal point in a coincide with those of $$a_n$$

provided $n \ge n_j$ . Therefore,

$|a - a_n| \le 10^{-j} < \varepsilon \quad \text {for} \quad n \ge n_j.$

With $n(\varepsilon ) = n_j$ the condition required in Definition 5.6 is fulfilled.

If the sequence $(a_n)_{n \ge 1}$ also has negative terms, it can be transformed to a sequence with non-negative terms by adding the absolute value of the first term which results in the sequence $(|a_1|+a_n)_{n \ge 1}$ . Using the obvious rule $\lim (c+a_n) = c + \lim a_n$ allows one to apply the first part of the proof. $\square$

Remark 5.11

The set of rational numbers is not complete. For example, the decimal expansion of $\sqrt{2}$ ,

$(1, 1.4, 1.41, 1.414, 1.4142,\ldots )$

is a monotonically increasing, bounded sequence of rational numbers (an upper bound is, e.g. $$T = 1.5$$

, since

), but the limit $\sqrt{2}$ does not belong to $\mathbb Q$ (as it is an irrational number).

Example 5.12

(Arithmetic of real numbers) Due to Proposition 5.10 the arithmetical operations on the real numbers introduced in Sect. 1.2 can be legitimised a posteriori. Let us look, for instance, at the addition of two non-negative real numbers $a=A.\alpha _1\alpha _2\ldots$ and $b=B.\beta _1\beta _2\ldots$ with $A, B \in \mathbb N_0$ , $\alpha _j,\beta _j \in \{0,1,\ldots , 9\}$ . By truncating them after the nth decimal place we obtain two approximating sequences of rational numbers $a_n= A.\alpha _1\alpha _2\ldots \alpha _n$ and $b_n = B.\beta _1\beta _2\ldots \beta _n$ with

$a = \lim _{n\rightarrow \infty }a_n,\quad b = \lim _{n\rightarrow \infty }b_n.$

The sum of two approximations $$a_n + b_n$$

is defined by the addition of rational numbers in an elementary way. The sequence $(a_n + b_n)_{n\ge 1}$ is evidently monotonically increasing and bounded from above, for instance, by $$A + B + 2$$

. According to Proposition 5.10 this sequence has a limit and this limit defines the sum of the real numbers

$a + b = \lim _{n\rightarrow \infty }(a_n + b_n).$

In this way the addition of real numbers is rigorously justified. In a similar way one can proceed with multiplication. Finally, Proposition 5.7 allows one to prove the usual rules for addition and multiplication.

Consider a sequence with upper bound T. Each real number $$T_1 > T$$ is also an upper bound. We can now show that there always exists a smallest upper bound. A bounded sequence thus actually has a supremum as claimed earlier.

Proposition 5.13

Each sequence $(a_n)_{n \ge 1}$ of real numbers which is bounded from above has a supremum.

Proof

Let $T_n = \max \{a_1,\ldots , a_n\}$ be the maximum of the first n terms of the sequence. These maxima on their part define a sequence $(T_n)_{n \ge 1}$ which is bounded from above by the same bounds as $(a_n)_{n \ge 1}$ but is additionally monotonically increasing. According to the previous proposition it has a limit $$T_0$$ . We are going to show that this limit is the supremum of the original sequence. Indeed, as $T_n \le T_0$ for all n, we have $a_n \le T_0$ for all n as well. Assume that the sequence $(a_n)_{n \ge 1}$ had a smaller upper bound $$T < T_0$$ , i.e. $a_n\le T$ for all n. This in turn implies $T_n\le T$ for all n and contradicts the fact that $T_0 = \lim T_n$ . Therefore, $$T_0$$ is the least upper bound. $\square$

Application 5.14

We are now in a position to show that the construction of the exponential function for real exponents given informally in Sect. 2.2 is justified. Let $$a > 0$$ be a basis for the power $$a^r$$ to be defined with real exponent $r\in \mathbb R$ . It is sufficient to treat the case $$r>0$$ (for negative r, the expression $$a^r$$ is defined by the reciprocal of $a^{|r|}$ ). We write r as the limit of a monotonically increasing sequence $(r_n)_{n\ge 1}$ of rational numbers by choosing for $$r_n$$ the decimal representation of r, truncated at the nth digit. The rules of calculation for rational exponents imply the inequality $a^{r_{n+1}} - a^{r_n} = a^{r_n}\left( a^{r_{n+1}-r_n} - 1\right) \ge 0$ . This shows that the sequence $(a^{r_n})_{n\ge 1}$ is monotonically increasing. It is also bounded from above, for instance, by $$a^q$$ , if q is a rational number bigger than r. According to Proposition 5.10 this sequence has a limit. It defines $$a^r$$ .

Application 5.15

Let $$a > 0$$ . Then $\lim _{n\rightarrow \infty } \!\root n \of {a} = 1$ .

In the proof we can restrict ourselves to the case $$0< a < 1$$ since otherwise the argument can be used for 1 / a. One can easily see that the sequence $(\!\root n \of {a}\,)_{n\ge 1}$ is monotonically increasing; it is also bounded from above by 1. Therefore, it has a limit b. Suppose that $$b < 1$$ . From $\root n \of {a} \le b$ we infer that $a\le b^n \rightarrow 0$ for $n\rightarrow \infty$ , which contradicts the assumption $$a > 0$$ . Consequently $$b = 1$$ .

5.3 Infinite Series

Sums of the form

$\sum ^\infty _{k = 1} a_k = a_1 + a_2 + a_3 + \cdots$

with infinitely many summands can be given a meaning under certain conditions. The starting point of our considerations is a sequence of coefficients $(a_k)_{k \ge 1}$ of real numbers. The nth partial sum is defined as

$S_n = \sum ^n_{k = 1} a_k = a_1 + a_2 + \cdots + a_n,$

thus

$\begin{aligned} S_1= & {} a_1,\\ S_2= & {} a_1 + a_2,\\ S_3= & {} a_1 + a_2 + a_3, \quad \text {etc.} \end{aligned}$

As needed we also use the notation $S_n = \sum ^n_{k = 0} a_k$ without further comment if the sequence $a_0, a_1, a_2, a_3,\ldots$ starts with the index $$k = 0$$

Definition 5.16

The sequence of the partial sums $(S_n)_{n \ge 1}$ is called a series. If the limit $S = \lim _{n \rightarrow \infty } S_n$ exists, then the series is called convergent, otherwise divergent.

In the case of convergence one writes

$S = \sum ^\infty _{k = 1} a_k = \lim _{n \rightarrow \infty } \left( \sum ^n_{k = 1} a_k \right) .$

In this way the summation problem is reduced to the question of convergence of the sequence of the partial sums.

Experiment 5.17

The M-file mat05_3.m, when called as mat05_3(N, Z), generates the first N partial sums with time delay Z [seconds] of five series, i.e. it computes $$S_n$$

for $1 \le n \le N$ in each case:

$\begin{aligned} \text {Series 1} : \quad S_n = \displaystyle \sum ^n_{k = 1} k^{-0.99}&\qquad \qquad \text {Series 2} : \quad S_n = \displaystyle \sum ^n_{k = 1} k^{-1}\\ \text {Series 3} : \quad S_n = \displaystyle \sum ^n_{k = 1} k^{-1.01}&\qquad \qquad \text {Series 4} : \quad S_n = \displaystyle \sum ^n_{k = 1} k^{-2}\\ \text {Series 5} : \quad S_n = \displaystyle \sum ^n_{k = 1} \frac{1}{k!}\quad \end{aligned}$

Experiment with increasing values of N and try to see which series shows convergence or divergence.

In the experiment the convergence of Series 5 seems obvious, while the observations for the other series are rather not as conclusive. Actually, Series 1 and 2 are divergent while the others are convergent. This shows the need for analytical tools in order to be able to decide the question of convergence. However, we first look at a few examples.

Example 5.18

(Geometric series) In this example we are concerned with the series $\sum ^\infty _{k=0} q^k$ with real factor $q \in \mathbb R$ . For the partial sums we deduce that

$S_n = \sum ^n_{k=0} q^k = \frac{1 - q^{n+1}}{1 - q}.$

Indeed, by subtraction of the two lines

$\begin{array}{rclllllllllll} S_n &{} = &{} 1 &{} + &{} q &{} + &{} q^2 &{} + &{} \cdots &{} + &{} q^n\,, &{} &{} \\ qS_n &{} = &{} &{} &{} q &{} + &{} q^2 &{} + &{} q^3 &{} + &{} \cdots &{} + &{} q^{n+1}\, \end{array}$

one obtains the formula $(1-q)S_n = 1 - q^{n+1}$ from which the result follows.

The case $$|q| < 1$$

: As $q^{n+1} \rightarrow 0$ the series converges with value

$S = \lim _{n \rightarrow \infty } \frac{1 - q^{n+1}}{1-q} = \frac{1}{1-q}.$

The case $$|q| > 1$$

: For

the partial sum $S_n = (q^{n+1}-1)/(q-1) \rightarrow \infty$ and the series diverges. In the case of $$q < - 1$$

the partial sums $S_n = (1-(-1)^{n+1}|q|^{n+1})/(1-q)$ are unbounded and oscillate. They thus diverge as well.

The case $$|q| =1$$ : For $$q = 1$$ we have $S_n = 1 + 1 + \cdots + 1 = n + 1$ which tends to infinity; for $$q = -1$$ , the partial sums $$S_n$$ oscillate between 1 and 0. In both cases the series diverges.

Example 5.19

The nth partial sum of the series $\sum ^\infty _{k=1} \frac{1}{k(k+1)}$ is

$\begin{aligned} S_n= & {} \sum ^n_{k = 1} \ \frac{1}{k(k+1)} = \sum ^n_{k=1} \left( \frac{1}{k} - \frac{1}{k + 1}\right) \\= & {} 1 - \frac{1}{2} + \frac{1}{2} - \frac{1}{3} + \frac{1}{3} - \frac{1}{4} + \cdots - \frac{1}{n} + \frac{1}{n} - \frac{1}{n+1} = 1 - \frac{1}{n+1}. \end{aligned}$

It is called a telescopic sum. The series converges to

$S = \sum ^\infty _{k=1} \ \frac{1}{k(k+1)} = \lim _{n \rightarrow \infty } \left( 1 - \frac{1}{n+1}\right) = 1.$

Example 5.20

(Harmonic series) We consider the series $\sum ^\infty _{k = 1} \frac{1}{k}$ . By combining blocks of two, four, eight, sixteen, etc., elements, one obtains the grouping

$\begin{aligned} 1 \!+ & {} \tfrac{1}{2} + \big (\tfrac{1}{3} + \tfrac{1}{4}\big ) + \big (\tfrac{1}{5} + \tfrac{1}{6} + \tfrac{1}{7} + \tfrac{1}{8}\big ) + \big (\tfrac{1}{9} + \cdots + \tfrac{1}{16}\big ) + \big (\tfrac{1}{17} + \cdots \big ) + \cdots \\\ge & {} 1 + \tfrac{1}{2} + \big (\tfrac{1}{4} + \tfrac{1}{4}\big ) + \big (\tfrac{1}{8} + \tfrac{1}{8} + \tfrac{1}{8} + \tfrac{1}{8}\big ) + \big (\tfrac{1}{16} + \cdots + \tfrac{1}{16} \big ) + \big (\tfrac{1}{32} + \cdots \big ) + \cdots \\&=1 + \tfrac{1}{2} + \tfrac{1}{2} + \tfrac{1}{2} + \tfrac{1}{2} + \tfrac{1}{2} + \cdots \ \rightarrow \ \infty . \end{aligned}$

The partial sums tend to infinity, therefore, the series diverges.

There are a number of criteria which allow one to decide whether a series converges or diverges. Here we only discuss two simple comparison criteria, which suffice for our purpose. For further considerations we refer to the literature, for instance [3, Chap. 9.2].

Proposition 5.21

(Comparison criteria) Let $0 \le a_k \le b_k$ for all $k \in \mathbb N$ or at least for all k greater than or equal to a certain $$k_0$$

. Then we have:

(a)

If the series $\sum ^\infty _{k =1} b_k$ is convergent then the series $\sum ^\infty _{k =1} a_k$ converges, too.
(b)

If the series $\sum ^\infty _{k=1} a_k$ is divergent then the series $\sum ^\infty _{k=1} b_k$ diverges, too.

Proof

(a) The partial sums fulfill $S_n = \sum ^n_{k =1} a_k \le \sum ^\infty _{k =1} b_k = T$ and $S_n \le S_{n+1}$ , hence are bounded and monotonically increasing. According to Proposition 5.10 the limit of the partial sums exists.

(b) This time, we have for the partial sums

$T_n = \sum ^n_{k=1} b_k \ge \sum ^n_{k=1} a_k \rightarrow \infty ,$

since the latter are positive and divergent. $\square$

Under the condition $0 \le a_k \le b_k$ of the proposition one says that $\sum ^\infty _{k =1} b_k$ dominates $\sum ^\infty _{k=1} a_k$ . A series thus converges if it is dominated by a convergent series; it diverges if it dominates a divergent series.

Example 5.22

The series $\sum ^\infty _{k = 1} \frac{1}{k^2}$ is convergent. For the proof we use that

$\sum ^n_{k = 1} \frac{1}{k^2} = 1 + \sum ^{n-1}_{j = 1} \frac{1}{(j + 1)^2}\quad \text{ and }\quad a_j = \frac{1}{(j+1)^2} \le \frac{1}{j(j+1)} = b_j.$

Example 5.19 shows that $\sum ^\infty _{j=1} b_j$ converges. Proposition 5.21 then implies convergence of the original series.

Example 5.23

The series $\sum ^\infty _{k=1} k ^{-0.99}$ diverges. This follows from the fact that $k^{-1} \le k^{-0.99}$ . Therefore, the series $\sum ^\infty _{k=1} k ^{-0.99}$ dominates the harmonic series which itself is divergent, see Example 5.20.

Example 5.24

In Chap. 2 Euler’s number

${\text {e}}= \sum ^\infty _{j=0} \frac{1}{j!} = 1 + 1+ \frac{1}{2}+ \frac{1}{6} + \frac{1}{24} + \frac{1}{120} + \cdots$

was introduced. We can now show that this definition makes sense, i.e. the series converges. For $j \ge 4$ it is obvious that

$j! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot \cdots \cdot j \ge 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot \cdots \cdot 2 = 2^j.$

Thus the geometric series $\sum ^\infty _{j=0} (\frac{1}{2})^j$ is a dominating convergent series.

Example 5.25

The decimal notation of a positive real number

$a = A. \alpha _1 \alpha _2 \alpha _3\ldots$

with $A \in \mathbb N_0, \alpha _k \in \{0,\ldots , 9\}$ can be understood as a representation by the series

$a = A + \sum ^\infty _{k=1} \alpha _k 10^{-k}.$

The series converges since $A +\, 9 \sum ^\infty _{k=1} 10^{-k}$ is a dominating convergent series.

5.4 Supplement: Accumulation Points of Sequences

Occasionally we need sequences which themselves do not converge but have convergent subsequences. The notions of accumulation points, limit superior and limit inferior are connected with this concept.

Definition 5.26

A number b is called accumulation point of a sequence $(a_n)_{n \ge 1}$ if each neighbourhood $U_\varepsilon (b)$ of b contains infinitely many terms of the sequence:

$\forall \varepsilon > 0 \ \forall n \in \mathbb N\ \exists m = m(n,\varepsilon ) \ge n: \ |b - a_m| < \varepsilon .$

Figure 5.3 displays the sequence

$a_n = \mathrm{{arctan}}\, n + \cos (n\pi /2) + {\displaystyle \frac{1}{n}}\sin (n\pi /2).$

It has three accumulation points, namely $b_1 = \pi /2 + 1\approx 2.57$ , $b_2 = \pi /2\approx 1.57$ and $b_3= \pi /2-1\approx 0.57$ .

images/215236_2_En_5_Chapter/215236_2_En_5_Fig3_HTML.gif — Fig. 5.3
Accumulation points of a sequence

If a sequence is convergent with limit a then a is the unique accumulation point. Accumulation points of a sequence can also be characterised with the help of the concept of subsequences.

Definition 5.27

If $1 \le n_1< n_2< n_3 < \cdots$ is a strictly monotonically increasing sequence of integers (indices) then

$(a_{n_j})_{j \ge 1}$

is called a subsequence of the sequence $(a_n)_{n \ge 1}$ .

Example 5.28

We start with the sequence $a_n = \frac{1}{n}$ . If we take, for instance, $$n_j = j^2$$

then we obtain the sequence $a_{n_j} = \frac{1}{j^2}$ as subsequence:

$\begin{aligned} (a_n)_{n \ge 1}= & {} (1, \tfrac{1}{2}, \tfrac{1}{3}, \tfrac{1}{4}, \tfrac{1}{5}, \tfrac{1}{6}, \tfrac{1}{7}, \tfrac{1}{8},\tfrac{1}{9},\tfrac{1}{10}, \dots ),\\ (a_{n_j})_{j \ge 1}= & {} (1, \tfrac{1}{4}, \tfrac{1}{9}, \dots ). \end{aligned}$

Proposition 5.29

A number b is an accumulation point of the sequence $(a_n)_{n \ge 0}$ if and only if b is the limit of a convergent subsequence $(a_{n_j})_{j \ge 1}$ .

Proof

Let b be an accumulation point of the sequence $(a_n)_{n \ge 0}$ . Step by step we will construct a strictly monotonically increasing sequence of indices $(n_j)_{j\ge 1}$ so that

$\begin{aligned} |b - a_{n_j}| < {\displaystyle \frac{1}{j}} \end{aligned}$

is fulfilled for all $j\in \mathbb N$ . According to Definition 5.26 for $\varepsilon _1 = 1$ we have

$\forall n \in \mathbb N\ \exists m \ge n\,: \ |b - a_m| < \varepsilon _1.$

We choose

and denote the smallest $m\ge n$ which fulfills this condition by $$n_1$$

. Thus

$|b - a_{n_1}| < \varepsilon _1 = 1.$

For $\varepsilon _2 = \frac{1}{2}$ one again obtains according to Definition 5.26:

$\forall n \in \mathbb N\ \exists m \ge n\,: \ |b - a_m| < \varepsilon _2.$

This time we choose $$n = n_1+1$$

and denote the smallest $m\ge n_1+1$ which fulfills this condition by $$n_2$$

. Thus

$|b - a_{n_2}| < \varepsilon _2 = \frac{1}{2}.$

It is clear how one has to proceed. Once $$n_j$$

is constructed one sets $\varepsilon _{j+1} = 1/(j+1)$ and uses Definition 5.26 according to which

$\forall n \in \mathbb N\ \exists m \ge n\,: \ |b - a_m| < \varepsilon _{j+1}.$

We choose

and denote the smallest $m\ge n_j+1$ which fulfills this condition by $n_{j+1}$ . Thus

$|b - a_{n_{j+1}}| < \varepsilon _{j+1} = \frac{1}{j+1}.$

This procedure guarantees on the one hand that the sequence of indices $(n_j)_{j\ge 1}$ is strictly monotonically increasing and on the other hand that the desired inequality is fulfilled for all $j\in \mathbb N$ . In particular, $(a_{n_j})_{j \ge 1}$ is a subsequence that converges to b.

Conversely, it is obvious that the limit of a convergent subsequence is an accumulation point of the original sequence. $\square$

In the proof of the proposition we have used the method of recursive definition of a sequence, namely the subsequence $(a_{n_j})_{j \ge 1}$ .

We next want to show that each bounded sequence has at least one accumulation point—or equivalently—a convergent subsequence. This result bears the names of Bolzano² and Weierstrass³ and is an important technical tool for proofs in many areas of analysis.

Proposition 5.30

(Theorem of Bolzano–Weierstrass) Every bounded sequence $(a_n)_{n \ge 1}$ has (at least) one accumulation point.

Proof

Due to the boundedness of the sequence there are bounds $$b < c$$ so that all terms of the sequence $$a_n$$ lie between b and c. We bisect the interval [b, c]. Then in at least one of the two half-intervals $$[b, (b+c)/2]$$ or $$[(b+c)/2, c]$$ there have to be infinitely many terms of the sequence. We choose such a half-interval and call it $$[b_1, c_1]$$ . This interval is also bisected; in one of the two halves again there have to be infinitely many terms of the sequence. We call this quarter-interval $$[b_2, c_2]$$ . Continuing this way we obtain a sequence of intervals $$[b_n, c_n]$$ of length $2^{-n}(c-b)$ each of which contains infinitely many terms of the sequence. Obviously the $$b_n$$ are monotonically increasing and bounded, therefore converge to a limit b. Since each interval $[b-2^{-n}, b+2^{-n}]$ by construction contains infinitely many terms of the sequence, b is an accumulation point of the sequence. $\square$

If the sequence $(a_n)_{n \ge 1}$ is bounded then the set of its accumulation points is also bounded and hence has a supremum. This supremum is itself an accumulation point of the sequence (which can be shown by constructing a suitable convergent subsequence) and thus forms the largest accumulation point.

Definition 5.31

The largest accumulation point of a bounded sequence is called limit superior and is denoted by $\overline{\lim }_{\, n\rightarrow \infty } a_n$ or $\limsup _{n\rightarrow \infty } a_n$ . The smallest accumulation point is called limit inferior with the corresponding notation $\underline{\lim }_{\;n\rightarrow \infty } a_n$ or $\liminf _{n\rightarrow \infty } a_n$ .

The relationships

$\begin{aligned} \limsup _{n\rightarrow \infty } a_n = \lim _{n\rightarrow \infty }\Big (\sup _{m\ge n} a_m\Big ),\qquad \liminf _{n\rightarrow \infty } a_n = \lim _{n\rightarrow \infty }\Big (\inf _{m\ge n} a_m\Big ) \end{aligned}$

follow easily from the definition and justify the notation.

For example, the sequence $(a_n)_{n\ge 1}$ from Fig. 5.3 has $\limsup _{n\rightarrow \infty } a_n = \pi /2 + 1$ and $\liminf _{n\rightarrow \infty } a_n = \pi /2 - 1.$

5.5 Exercises

1.

Find a law of formation for the sequences below and check for monotonicity, boundedness and convergence:

$\begin{aligned}&-3,\,-2, \, -1, \, 0, \, \tfrac{1}{4}, \, \tfrac{3}{9}, \,\tfrac{5}{16}, \,\tfrac{7}{25}, \,\tfrac{9}{36}, \ldots ; \\&0, \, -1, \, \tfrac{1}{2}, \, -2, \, \tfrac{1}{4},\, -3, \, \tfrac{1}{8},\, -4, \, \tfrac{1}{16}, \ldots . \end{aligned}$

2.

Verify that the sequence $a_n = \frac{n^2}{1 + n^2}$ converges to 1.

Hint. Given $\varepsilon > 0$ , find $n(\varepsilon )$ such that

$\left| \frac{n^2}{1+n^2} \, -1 \right| < \varepsilon$

for all $n \ge n(\varepsilon )$ .

3.

Determine a recursion formula that provides the terms of the geometric sequence $$a_n = q^n$$ , $n\ge 0$ successively. Write a MATLAB program that calculates the first N terms of the geometric sequence for an arbitrary $q\in \mathbb R$ . Check the convergence behaviour for different values of q and plot the results. Do the same with the help of the applet Sequences.

4.

Investigate whether the following sequences converge and, in case of convergence, compute the limit:

$\begin{aligned} a_{n}&= \frac{n}{n+1} - \frac{n + 1}{n}, \quad&b_{n}&= -n + \frac{1}{n}, \quad&c_n&= \left( -\frac{1}{n} \right) ^{n}, \\ d_n&= n - \frac{n^{2} + 3n + 1}{n}, \quad&e_n&= \frac{1}{2} \left( {\text {e}}^{n} + {\text {e}}^{-n} \right) , \quad&f_n&= \cos (n\pi ). \end{aligned}$

5.

Investigate whether the following sequences have a limit or an accumulation point. Compute, if existent, $\lim , \liminf , \limsup , \inf , \sup$ :

$\begin{aligned} a_n&= \frac{n+7}{n^3+n+1}, \quad&b_n&= \frac{1-3n^2}{7n+5}, \quad&c_n&= \frac{{\text {e}}^n - {\text {e}}^{-n}}{{\text {e}}^n+{\text {e}}^{-n}},\\ d_n&= 1+ (-1)^n, \quad&e_n&= \frac{1+(-1)^n}{n}, \quad&f_n&= \big ( 1+ (-1)^n \big ) (-1)^{n/2}. \end{aligned}$

6.

Open the applet Sequences, visualise the sequences from Exercises 4 and 5 and discuss their behaviour by means of their graphs.

7.

The population model of Verhulst from Example 5.3 can be described in appropriate units in simplified form by the recursive relationship

$x_{n+1} = r x_n (1 - x_n), \quad n = 0,1,2,3,\ldots$

with an initial value $$x_0$$

and a parameter r. We presume in this sequence that $0\le x_0 \le 1$ and $0 \le r \le 4$ (since all $$x_n$$

then stay in the interval [0, 1]). Write a MATLAB program which calculates for given $$r, x_0, N$$

the first N terms of the sequence $(x_n)_{n \ge 1}$ . With the help of your program (and some numerical values for $$r, x_0, N$$

) check the following statements:

(a): For $0 \le r \le 1$ the sequence converges to 0.
(b): For $1< r < 2 \sqrt{2}$ the sequence tends to a positive limit.
(c): For $3< r < 1 + \sqrt{6}$ the sequence eventually oscillates between two different positive values.
(d): For $3.75 < r \le 4$ the sequence behaves chaotically.

Illustrate these assertions also with the applet Sequences.

8.

The sequence $(a_n)_{n \ge 1}$ is given recursively by

$\begin{aligned} a_1 = A, \quad a_{n+1} = \frac{1}{2} \, a_n^2 - \frac{1}{2}\, . \end{aligned}$

Which starting values $A \in \mathbb {R}$ are fixed points of the recursion, i.e. it holds $A = a_1 = a_2 = \dots ?$ Investigate for which starting values $A \in \mathbb R$ the sequence converges or diverges, respectively. You can use the applet Sequences for that. Try to locate the regions of convergence and divergence as precisely as possible.

9.

Write a MATLAB program which, for given $\alpha \in [0,1]$ and $N \in \mathbb N$ , calculates the first N terms of the sequence

$x_n = n \alpha - \lfloor n \alpha \rfloor , \quad n = 1,2,3,\ldots , N$

( $\lfloor n\alpha \rfloor$ denotes the largest integer smaller than $n \alpha$ ). With the help of your program, investigate the behaviour of the sequence for a rational $\alpha = \frac{p}{q}$ and for an irrational $\alpha$ (or at least a very precise rational approximation to an irrational $\alpha$ ) by plotting the terms of the sequence and by visualising their distribution in a histogram. Use the MATLAB commands floor and hist.

10.

Give formal proofs for the remaining rules of calculation of Proposition 5.7, i.e. for addition and division by modifying the proof for the multiplication rule.

11.

Check the following series for convergence with the help of the comparison criteria:

$\sum _{k =1}^{\infty }\frac{1}{k(k+2)},\qquad \sum ^\infty _{k=1} \frac{1}{\sqrt{k}}, \qquad \sum ^\infty _{k=1}\frac{1}{k^3}.$

12.

Check the following series for convergence:

$\begin{aligned} \sum _{k = 1}^{\infty }\frac{2 + k^2}{k^4}, \qquad \sum _{k = 1}^{\infty }\left( \frac{1}{2}\right) ^{2k}, \qquad \sum _{k = 1}^{\infty }\frac{2}{k!}. \end{aligned}$

13.

Try to find out how the partial sums $$S_n$$ of the series in Exercises 11 and 12 can be calculated with the help of a recursion and then study their behaviour with the applet Sequences.

14.

Prove the convergence of the series

$\sum _{k =0}^{\infty } \frac{2^k}{k!}.$

Hint. Use the fact that $j! \ge 4^j$ is fulfilled for $j \ge 9$ (why)? From this it follows that $2^j/j! \le 1/2^j$ . Now apply the appropriate comparison criterion.

15.

Prove the ratio test for series with positive terms $$a_k > 0$$

: If there exists a number q, $$0< q < 1$$

such that the quotients satisfy

$\frac{a_{k+1}}{a_k} \le q$

for all $k \in \mathbb N_0$ , then the series $\sum _{k=0}^\infty a_k$ converges.

Hint. From the assumption it follows that $a_1 \le a_0q$ , $a_2 \le a_1q \le a_0q^2$ and thus successively $a_k \le a_0q^k$ for all k. Now use the comparison criteria and the convergence of the geometric series with $$q <1$$ .

Prev Next