📖 Series

⏱ | words

References and additional materials

[Sydsæter, Hammond, Strøm, and Carvajal, 2016]

Chapters 10.4

Series

Definition

A infinite series is the sum of the infinite terms of a sequence \(\{ x_n \}_{n \in \mathbb{N}}\) and is denoted by

\[ \sum_{n \in \mathbb{N}} x_n = \sum_{n=1}^{\infty} x_n = x_1 + x_2 + x_3 + \dots \]

Definition

A partial sum of a series is the sum of the first \(N\) terms of the sequence,

\[s_N = \sum_{n=1}^{N} x_n = x_1 + x_2 + x_3 + \dots + x_N\]

Definition

The value of the series is equal to the limit of the sequence of its partial sums, when it exists

\[\sum_{n \in \mathbb{N}} x_n = \lim_{N \to \infty} s_N = \lim_{N \to \infty} \sum_{n=1}^{N} x_n\]

If the limit does not exist, the series is referred to as divergent.

We might sometimes want to start the summation at \(n = 0\). We can do this by employing a change of index.

• If we let \(k = n − 1\), the total sum of the sequence can be expressed as

\[ \sum_{n=1}^{\infty} x_n = \sum_{k=0}^{\infty−1} x_{k+1} = \sum_{k=0}^{\infty} x_{k+1}\]

(because \(\infty − 1 = \infty\)).

• If we let \(k = n − 1\), the partial sum of the first \(N\) terms of the sequence can be expressed as

\[\sum_{n=1}^{N} x_n = \sum_{k=0}^{N - 1} x_{k+1}\]

Example

Euler constant \(e\) can be expressed as a series

\[e = \sum_{n=0}^{\infty} \frac{1}{n!} = 1 + 1 + \frac{1}{2} + \frac{1}{6} + \frac{1}{24} + \dots\]

• See explanation and derivation in a video

Computing Euler’s constant as series

e0 = 2.71828182845904523536028747135266
print('Approximation of Euler constant with a series')
e = 0.
for n in range(0,21):
    term = term / n if n>0 else 1.
    e += term
    print('iter = {:3d}: e = {:17.15f} err = {:14.7e}'.format(n,e,e0-e))

Approximation of Euler constant with a series
iter =   0: e = 1.000000000000000 err =  1.7182818e+00
iter =   1: e = 2.000000000000000 err =  7.1828183e-01
iter =   2: e = 2.500000000000000 err =  2.1828183e-01
iter =   3: e = 2.666666666666667 err =  5.1615162e-02
iter =   4: e = 2.708333333333333 err =  9.9484951e-03
iter =   5: e = 2.716666666666666 err =  1.6151618e-03
iter =   6: e = 2.718055555555555 err =  2.2627290e-04
iter =   7: e = 2.718253968253968 err =  2.7860205e-05
iter =   8: e = 2.718278769841270 err =  3.0586178e-06
iter =   9: e = 2.718281525573192 err =  3.0288585e-07
iter =  10: e = 2.718281801146385 err =  2.7312661e-08
iter =  11: e = 2.718281826198493 err =  2.2605522e-09
iter =  12: e = 2.718281828286169 err =  1.7287638e-10
iter =  13: e = 2.718281828446759 err =  1.2285728e-11
iter =  14: e = 2.718281828458230 err =  8.1490370e-13
iter =  15: e = 2.718281828458995 err =  5.0182081e-14
iter =  16: e = 2.718281828459043 err =  2.2204460e-15
iter =  17: e = 2.718281828459046 err = -4.4408921e-16
iter =  18: e = 2.718281828459046 err = -4.4408921e-16
iter =  19: e = 2.718281828459046 err = -4.4408921e-16
iter =  20: e = 2.718281828459046 err = -4.4408921e-16

Example

Harmonic series given by

\[\sum_{n=0}^{\infty} \frac{1}{n} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dots\]

is divergent. The \(n\)-th partial sum is approximately equal \(\ln(n)+\gamma\), where \(\gamma = 0.577\) is called an Euler-Mascheroni constant.

Note

Recall the technique of proof by mathematical induction

Example

We want to show that \(\sum\limits_{x = 1}^n x = \frac{n(n+1)}{2}\) for all \(n \in \mathbb{N}\).

The proof proceeds as follows.

Note that \(\sum\limits_{x = 1}^{1} x = 1\) and \(\frac{1(1+1)}{2} = \frac{2}{2} = 1\). Thus the claim is true for \(n = 1\).

Assume that the claim is true for \(n = k\). In other words, assume that \(\sum\limits_{x = 1}^k x = \frac{k(k+1)}{2}\).

Consider the case of \(n = (k + 1)\).

• \(\sum\limits^{k+1}_{x =1} x = (\sum\limits^{k}_{x = 1} x ) + (k + 1) = \frac{k(k+1)}{2} + (k + 1)\) due to our inductive assumption

• \(\frac{k(k+1)}{2} + (k + 1) = \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{(k+2)(k+1)}{2}\)

• \(\frac{(k+2)(k+1)}{2} = \frac{((k+1)+1)(k+1)}{2} = \frac{(k+1)((k+1)+1)}{2}\)

Thus we have shown that, if the claim is true for \(n = k\), then it must also be true for \(n = (k + 1)\).

Since (a) the claim is true for \(n = 1\), and (b) if the claim is true for \(n = k\), then it is also true for \(n = (k + 1)\), we can conclude by the principle of mathematical induction that the claim is true for all \(n \in \mathbb{N}\).

This example comes from [Simon and Blume, 1994] (pp. 856-857).

Example

Claim: \(\sum\limits^{n}_{x = 1} x^2 = \frac{n(n+1)(2n+1)}{6}\).

We will prove this claim by induction.

Step one: \(P(1)\) is true.

Consider the case where \(n = 1\). Note that \(\sum\limits_{x = 1}^1 x^2 = 1^2 = 1\).

Note also that

\[\begin{split} \begin{align*} \frac{n (n + 1) (2n + 1)}{6} &= {1 (1 + 1) (2 (1) + 1)}{6} \\ &= \frac{1 (2) (2 + 1)}{6} \\ &= \frac{1 (2) (3)}{6} \\ &= \frac{6}{6} \\ &= 1 \end{align*} \end{split}\]

Thus the claim is true when \(n = 1\).

Step two: \(P(k)\) true implies \(P(k+1)\) true. Suppose that the claim is true when \(n = k\), so that

\[\sum_{x = 1}^k x^2 = \frac{k (k + 1) (2k + 1)}{6}\]

Consider the case where \(n = (k + 1)\). We have

\[\begin{split} \begin{align*} \sum_{x = 1}^{k + 1} x^2 &= \left( \sum_{x = 1}^{k} x^2 \right) + (k + 1)^2 \\ &= \frac{k (k + 1) (2k + 1)}{6} + (k + 1)^2 \text{ from the inductive assumption} \\ &= \frac{k (k + 1) (2k + 1)}{6} + \frac{6(k + 1)^2}{6} \\ &= \frac{k (k + 1) (2k + 1) + 6 (k + 1)^2}{6} \\ &= \frac{(k + 1) \{ k (2k + 1) + 6 (k + 1) \}}{6} \\ &= \frac{(k + 1) \{ 2k^2 + k + 6k + 6 \}}{6} \\ &= \frac{(k + 1) \{ 2k^2 + 7k + 6 \}}{6} \\ &= \frac{(k + 1) \{ (2k + 3) (k + 2) \}}{6} \\ &= \frac{(k + 1) (2k + 3) (k + 2)}{6} \\ &= \frac{(k + 1) (k + 2) (2k + 3)}{6} \\ &= \frac{(k + 1) ((k + 1) + 1) (2 (k + 1) + 1)}{6} \end{align*} \end{split}\]

Thus we have

\[ \sum_{x = 1}^{k + 1} x^2 = \frac{(k + 1) ((k + 1) + 1) (2 (k + 1) + 1)}{6} \]

As such, we know that \(P(k)\) implies \(P(k + 1)\).

Step three: Conclusion

We have shown that the claim is true for the case where \(n = (k + 1)\) if it is true for the case where \(n = k\). We have also shown that the claim is true for the case where \(n = 1\). Thus we know, from the principle of mathematical induction, that the claim is true for all \(n \in \mathbb{N}\).

Example

Claim: \(\sum\limits^{n}_{x = 1} x^3 = \frac{n^2(n+1)^2}{4}\). We will prove this claim by induction.

Step one: P(1) is true. Consider the case where \(n = 1\).

• Note that \(\sum\limits_{x = 1}^1 x^3 = 1^3 = 1\).

• Note also that

\[\begin{split} \begin{align*} \frac{n^2 (n + 1)^2}{4} &= \frac{1^2 (1 + 1)^2}{4} \\ &= \frac{1 (2)^2}{4} \\ &= \frac{1 (4)}{4} \\ &= \frac{4}{4} \\ &= 1 \end{align*} \end{split}\]

Thus the claim is true when \(n = 1\).

Step two: \(P(k)\) true implies \(P(k+1)\) true. Suppose that the claim is true when \(n = k\), so that

\[\sum_{x = 1}^k x^3 = \frac{k^2 (k + 1)^2}{4}\]

Consider the case where \(n = (k + 1)\). We have

\[\begin{split} \begin{align*} \sum_{x = 1}^{k + 1} x^3 &= \left( \sum_{x =1}^k x^3 \right) + (k + 1)^3 \\ &= \frac{k^2 (k + 1)^2}{4} + (k + 1)^3 \text{ from the inductive assumption } \\ &= \frac{k^2 (k + 1)^2}{4} + \frac{4 (k + 1)^3}{4} \\ &= \frac{k^2 (k + 1)^2 + 4 (k + 1)^3}{4} \\ &= \frac{(k + 1)^2 \{ k^2 + 4 (k + 1) \}}{4} \\ &= \frac{(k + 1)^2 \{ k^2 + 4k + 4 \}}{4} \\ &= \frac{(k + 1)^2 (k + 2)^2}{4} \\ &= \frac{(k + 1)^2 ((k + 1) + 1)^2}{4} \end{align*} \end{split}\]

Thus we have

\[\sum_{ x = 1}^n x^3 = \frac{n^2 (n + 1)^2}{4}\]

As such, we know that \(P(k)\) implies \(P(k + 1)\).

Step three: Conclusion

We have shown that the claim is true for the case where \(n = (k + 1)\) if it is true for the case where \(n = k\). We have also shown that the claim is true for the case where \(n = 1\). Thus we know, from the principle of mathematical induction, that the claim is true for all \(n \in \mathbb{N}\).

Example

Claim: \(\sum^n_{x = 1} (2x − 1) = n^2\)

We will prove this claim by induction.

Step one: P(1) is true. Consider the case where \(n = 1\).

Note that \(\sum_{x = 1}^{1} (2x − 1) = 2 (1) − 1 = 2 − 1 = 1\)

and \(1^2 = 1\). Thus the claim is true when \(n = 1\).

Step two: \(P(k)\) true implies \(P(k+1)\) true. Suppose that the claim is true when \(n = k\), so that

\[\sum^k_{x = 1} (2x − 1) = k^2\]

Consider the case where \(n = (k + 1)\). We have

\[\begin{split} \begin{align*} \sum_{x = 1}^{k + 1} (2x − 1) \\ &= \left( \sum_{x =1}^k (2x − 1) \right) + (2 (k + 1) − 1) \\ &= k^2 + (2 (k + 1) − 1) \text{ from the inductive assumption } \\ &= k^2 + (2k + 2 − 1) \\ &= k^2 + (2k + 1) \\ &= k2 + 2k + 1 \\ &= (k + 1)^2 \end{align*} \end{split}\]

Thus we have

\[\sum_{x = 1}^{k + 1} (2x − 1) = (k + 1)^2\]

As such, we know that \(P(k)\) implies \(P(k + 1)\).

Step three: Conclusion

We have shown that the claim is true for the case where \(n = (k + 1)\) if it is true for the case where \(n = k\). We have also shown that the claim is true for the case where \(n = 1\). Thus we know, from the principle of mathematical induction, that the claim is true for all \(n \in \mathbb{N}\).

Example

We want to show that \(n < 2^n\) for all \(n \in \mathbb{N}\). The proof proceeds as follows:

• Note that \(1 < 2^1 = 2\), so the claim is true when \(n = 1\).

• Assume that the claim is true when \(n = k\). This means that \(k < 2^k\).

• Consider the case of \(n = (k + 1)\).

• If we add \(1\) to both sides of the inequality in our inductive assumption, we obtain \(k + 1 < 2^k + 1\).

• Since \(k \geqslant 1\), we know that \(1 < 2 = 2^1 \leqslant 2^k\).

• This means that \(1 \leqslant 2^k\).

• This means that \(2^k + 1 < 2^k + 2^k\).

• Note that \(2^k + 2^k = 2(2^k ) = 2^{k+1}\).

• This means that \(2^k + 1 < 2^{k+1}\).

• Since \(k + 1 < 2^k + 1\) and \(2^k + 1 < 2^{k+1}\), we know that \((k + 1) < 2^{k+1}\).

• Thus, if the proposition is true when \(n = k\), then it must also be true when \(n = (k + 1)\).

• Since (a) the claim is true for \(n = 1\), and (b) the claim is true for \(n = k\), then it is also true for \(n = (k + 1)\), we can conclude, by the principle of mathematical induction, that the claim is true for all \(n \in \mathbb{N}\).

This example comes from Exercise A.1.7 in [Simon and Blume, 1994] (p. 858).

Arithmetic progressions

Consider a real sequence \(\{ x_n \}_{n \in \mathbb{N}}\) in which \(x_n = a + (n − 1) d\).

This sequence is known as an arithmetic progression because the difference between any two consecutive terms of the sequence (with the highest index first: \(x_{m+1} − x_m\)) is equal to \(d\).

The infinite series associated with this sequence is

\[ \sum_{n=1}^\infty (a + (n − 1) d ) = \sum_{k=0}^\infty (a + kd)\]

The partial sum of the first (N + 1) terms of this series is given by

\[\begin{split} \begin{align*} S_{(N+1)} &= \sum_{n=1}^{N + 1} (a + (n − 1) d ) \\ &= \sum_{k=0}^{N} (a + kd ) \\ &= \frac{(2a + Nd ) (N + 1)}{2} \end{align*} \end{split}\]

This validity of this formula can be established through a proof by induction. We do this below (after some other brief comments).

Note that the partial sum of the first \(N\) terms of an arithmetic progression is given by

\[S_N = \frac{(2a + (N − 1)d ) N}{2} = (N) \left( \frac{\{ (a) + (a + (N − 1) d ) \}}{2} \right)\]

As is noted in [Shannon, 1995] (p. 302), this formula has a very simple interpretation. It is simply the number of terms in the sequence that are being summed times the average of the first and last terms in that sequence.

Fact

\(\sum\limits^{N+1}_{n=1} (a + (n − 1) d ) = \frac{(2a+Nd )(N+1)}{2}\).

Proof

Note that the following proof is based on the one that is provided in [Basov, 2011] (pp. 22-23). By mathematical induction on \(N\).

Let \(N = 1\). We have

\[\begin{split} \sum_{n=1}^{N + 1} (a + (n − 1) d ) = \sum_{n=1}^2 (a + (n − 1) d ) \\ = (a + (1 − 1)d ) + (a + (2 − 1)d ) \\ = (a + 0d + a + 1d ) \\ = (2a + d ) \end{split}\]

and

\[ \frac{(2a + Nd ) (N + 1)}{2} = \frac{(2a + 1d ) (1 + 1)}{2} = \frac{(2a + d )(2)}{2} = (2a + d )\]

Thus the claim is true for \(N = 1\).

Assume that the claim is true for \(N = k\). In other words, assume that

\[ \sum_{n=1}^{k + 1} (a + (n − 1) d ) = \frac{(2a + kd ) (k + 1)}{2}\]

(Call this the “inductive assumption”.)

Now consider the case when \(N = (k + 1)\). We have

\[\begin{split} \begin{align*} \sum_{n=1}^{k + 2} (a + (n − 1) d ) \\ &= \left( \sum_{n=1}^{k + 1} (a + (n − 1) d ) \right) + (a + (k + 2 − 1) d ) \\ &= \frac{(2a + kd ) (k + 1)}{2} + (a + (k + 1)d ) \text{ (by the inductive assumption) } \\ &= \frac{(2a + kd ) (k + 1)}{2} + \frac{(2a + 2(k + 1)d )}{2} \\ &= \frac{2a(k + 1) + k(k + 1)d + 2a + 2(k + 1)d}{2} \\ &= \frac{2a ((k + 1) + 1) + ((k + 1) + 1) (k + 1)d}{2} \\ &= \frac{(2a + (k + 1)d ) ((k + 1) + 1)}{2} \end{align*} \end{split}\]

Since this is in the required form, and we used the inductive assumption in the process of deriving it, we have shown that, if the claim is true when \(N = k\), then it is also true when \(N = (k + 1)\).

Since \(P(1)\) is true, and \(P(k) \Rightarrow P(k + 1)\), we know, by the principle of mathematical induction, that the claim is true for all \(N \in \mathbb{N}\).

Note that the sum of all of the terms in an infinite arithmetic progression is unbounded, since

\[\begin{split} \begin{align*} S_\infty &= \lim_{N \rightarrow \infty} S_{N + 1} \\ &= \lim_{N \rightarrow \infty} \sum_{n=1}^{N + 1} (a + (n − 1)d ) \\ &= \lim_{N \rightarrow \infty} \frac{(2a + Nd ) (N + 1)}{2} \\ &= \begin{cases} \infty \quad \text{ if } d > 0, \\ −\infty \quad \text{ if } d < 0. \end{cases} \end{align*} \end{split}\]

Geometric progressions

Consider a real sequence \(\{ x_n \}_{n \in \mathbb{N}}\) in which \(x_n = ar^{(n−1)}\). We will assume that \(r \notin \{ 0, 1 \}\).

This sequence is known as a geometric progression because the ratio of any two consecutive terms of the sequence (with the highest index on numerator: \(\frac{x_{m+1}}{x_m}\) ) is equal to \(r\).

The infinite series associated with this sequence is

\[ \sum_{n=1}^{\infty} ar^{(n−1)} = \sum_{k=0}^{\infty} ar^k\]

The partial sum of the first \((N + 1)\) terms of this series is given by

\[\begin{split} \begin{align*} S_{(N+1)} &= \sum_{n=1}^{N+1} ar^{(n−1)} \\ &= \sum_{k=0}^{N} ar^k \\ &= a \sum_{k=0}^N r^k \\ &= \frac{a ( 1 − r^{(N+1)})}{(1 − r )} \end{align*} \end{split}\]

This validity of this formula can be established through a proof by induction. This is left for you to do as an exercise.

The sum of all of the terms in an infinite geometric progression is given by

\[\begin{split} \begin{align*} S_\infty &= \lim_{N \rightarrow \infty} S_{N+1} \\ &= \lim_{N \rightarrow \infty} \sum_{n=1}^{N+1} ar^{(n−1)} \\ &= \lim_{N \rightarrow \infty} \frac{a ( 1 − r^{(N+1)})}{(1 − r )} \\ &= \begin{cases} \frac{a}{(1−r )} \quad \text{ if } |r| < 1, \\ \pm\infty \quad \text{ if } |r| > 1. \end{cases} \end{align*} \end{split}\]