summations and series

Harmonic Number

We define the

n

-th harmonic number as

H_{n} : = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} = \sum_{k = 1}^{n} \frac{1}{k}

Closed form of a Geometric Summation

For any

x \in R^{\neq 1}

and

k \in N_{0}

\sum_{n = 0}^{k} x^{n} = \frac{1 - x^{k + 1}}{1 - x}

Let

S = \sum_{n = 0}^{k} x^{n}

, then

x S - S = x^{k + 1} - x^{0}

therefore

S = \frac{x^{k + 1} - 1}{x - 1}

, so also

S = \frac{1 - x^{k + 1}}{1 - x}

by factoring -1 from the numerator and the denominator, as needed

Or instead it can be proven inductively as follows, in the base case we get

\sum_{n = 0}^{0} x^{n} = x^{0} = 1 = \frac{1 - x^{1}}{1 - x}

assume it holds true for

j \in N_{0}

and we want to prove that it holds true for

j + 1

\sum_{n = 0}^{j + 1} x^{n} & = \sum_{n = 0}^{j} x^{n} + x^{j + 1} & = \frac{1 - x^{j + 1}}{1 - x} + \frac{x^{j + 1} (1 - x)}{1 - x} & = \frac{1 - x^{j + 1} + x^{j + 1} (1 - x)}{1 - x} & = \frac{1 - x^{j + 2}}{1 - x}

as needed.

Geometric Summation with Offset

For any

x \in R^{\neq 1}

and

k \in N_{0}

we have

\sum_{n = m}^{k} x_{n} = x^{m} (\frac{1 - x^{k - m + 1}}{1 - x})

Once we've proven the generalized factoring for arbitrary sums then we have

\sum_{n = m}^{k} x_{n} = x^{m} (\sum_{n = 0}^{k - m + 1} x^{n}) = x^{m} (\frac{1 - x^{k - m + 1}}{1 - x})

Note that when $x = 1$ the sum simply yields $k + 1$ .

Series

Given a sequence

{(a_{n})}_{n = 1}^{\infty}

and defining

S_{k} = \sum_{i = 1}^{k} a_{k}

then we define

\sum_{i = 0}^{\infty} a_{i} : = {lim}_{n \to \infty} S_{n}

Note that because it is defined as a limit we can ask if $\sum_{i = 0}^{\infty} a_{n}$ converges or not.

Harmonic Series Diverges

\sum_{n = 1}^{\infty} \frac{1}{n}

diverges to

\infty

We claim that

S_{2^{k}} \geq \frac{k + 2}{2} = \frac{k}{2} + 1

for all

k \in N_{0}

, for the base case we see that

S_{2^{0}} = S_{1} = \frac{1}{1} \geq \frac{0}{2} + 1

so it holds true, now suppose its true for some

j \in N_{0}

we want to prove that

S_{2^{j + 1}} \geq \frac{j + 1}{2} + 1

S_{2^{k + 1}} & = S_{2^{k}} + \sum_{m = 2^{k} + 1}^{2^{k + 1}} \frac{1}{m} & \geq (\frac{k}{2} + 1) + \sum_{m = 2^{k} + 1}^{2^{k + 1}} \frac{1}{m} & \geq (\frac{k}{2} + 1) + \sum_{m = 2^{k} + 1}^{2^{k + 1}} \frac{1}{2^{k + 1}} & \geq (\frac{k}{2} + 1) + \sum_{m = 2^{k} + 1}^{2^{k + 1}} \frac{1}{2^{k + 1}} & = (\frac{k}{2} + 1) + 2^{k} (\frac{1}{2^{k + 1}}) & = (\frac{k}{2} + 1) + \frac{1}{2} & = \frac{k + 1}{2} + 1

Thus since

S_{2^{k}} \geq \frac{k}{2} + 1

and

{lim}_{k \to \infty} \frac{k}{2} + 1 = \infty

then we know that

\sum_{k \to \infty} S_{2^{k}} = \infty

and thus since a subsequence

S_{n}

diverges then we know that

S_{n}

diverges

Geometric Power Series

for

| x | <; 1

we have

\sum_{n = 0}^{\infty} x^{n} = \frac{1}{1 - x}

By definition we know that $\sum_{n = 0}^{\infty} x^{n} = {lim}_{k \to \infty} \sum_{n = 0}^{k} x^{n}$ $=$ ${lim}_{k \to \infty} \frac{1 - x^{k + 1}}{1 - x}$

exponent limit lemma if

| x | <; 1

then

{lim}_{k \to \infty} x^{k + 1}

becomes zero and we get

{lim}_{k \to \infty} \frac{1 - x^{k + 1}}{1 - x} = \frac{1}{1 - x}

Geometric Power Series with Offset

For

| x | < 1

we have

\sum_{n = m}^{\infty} x_{n} = \frac{x^{m}}{1 - x}

By the geometric summation with offset we know that

\sum_{n = m}^{\infty} x_{n} = {lim}_{k \to \infty} x_{m} (\frac{1 - x^{k - m + 1}}{1 - x}) = \frac{x^{m}}{1 - x}

Series of Halves is Bounded

\sum_{n = 0}^{\infty} {\frac{1}{2}}^{n} = \frac{1}{1 - \frac{1}{2}} = 2

In the above proposition take

x = \frac{1}{2}

geometric sum with incrementing factor

Given

t \in ℝ^{\neq 0}

, the following holds:

\sum_{i = 1}^{n} i t^{i} = t \frac{1 - t^{n}}{{(1 - t)}^{2}} - n \frac{t^{n + 1}}{1 - t}

We want to find the sum defined by

S (t) : = t + 2 t^{2} + 3 t^{3} + \dots + (n - 1) t^{n - 1} + n t^{n}

But then we know that

t \cdot S (t) = t^{2} + 2 t^{3} + 3 t^{4} + \dots + (n - 1) t^{n} + n t^{n + 1}

⟺

S (t) - t S (t) = t + t^{2} + t^{3} + \dots + t^{n} - n t^{n + 1}

⟺

(1 - t) S (t) = t + t^{2} + t^{3} + \dots + t^{n} - n t^{n + 1}

Now since we know that

t + t^{2} + t^{3} + \dots + t^{n} = t \frac{1 - t^{n}}{1 - t}

, then we have

(1 - t) S (t) = t \frac{1 - t^{n}}{1 - t} - n t^{n + 1}

⟺

S (t) = \frac{t \frac{1 - t^{n}}{1 - t} - n t^{n + 1}}{1 - t}

⟺

S (t) = t \frac{1 - t^{n}}{{(1 - t)}^{2}} - n \frac{t^{n + 1}}{1 - t}

geometric series with incrementing factor

Suppose that

| t | < 1

, then

\sum_{i = 1}^{\infty} i t^{i} = \frac{t}{{(1 - t)}^{2}}

We know that $\sum_{i = 1}^{\infty} i t^{i} = {lim}_{n \to \infty} \sum_{i = 1}^{n} i t^{i}$ $=$ ${lim}_{n \to \infty} t \frac{1 - t^{n}}{{(1 - t)}^{2}} - n \frac{t^{n + 1}}{1 - t}$

Now since $| t | < 1$ , then ${lim}_{n \to \infty} t^{n} = 0$ and ${lim}_{n \to \infty} n t^{n + 1} = 0$ , therefore ${lim}_{n \to \infty} t \frac{1 - t^{n}}{{(1 - t)}^{2}} - n \frac{t^{n + 1}}{1 - t} = \frac{t}{{(1 - t)}^{2}}$ as needed.

Convergent Series Implies Sequence goes to Zero

\sum_{n = 1}^{\infty} a_{n}

is convergent then

{lim}_{n \to \infty} a_{n} = 0

Let

{(S_{n})}_{n = 1}^{\infty}

be so defined such that

S_{n} = \sum_{i = 0}^{n} a_{i}

, observe that

S_{n} - S_{n - 1} = a_{n}

for all

n \geq 2

so then

{lim}_{n \to \infty} a_{n} = {lim}_{n \to \infty} (s_{n} - s_{n - 1}) = {lim}_{n \to \infty} s_{n} - {lim}_{n \to \infty} s_{n - 1} = 0

Cauchy Criterion for Series

Suppose that

\sum_{n = 1}^{\infty} a_{n}

is a series, then the following are equivalent:

The series converges
$\forall ϵ \in R^{+}, \exists N \in N_{0} st \forall n \in N_{0}, n \geq N ⟹ | \sum_{k = n + 1}^{\infty} a_{k} | < ϵ$
$\forall ϵ \in R^{+}, \exists N \in N_{0} st \forall n, m \in N_{0}, n, m \geq N ⟹ | \sum_{k = n + 1}^{m} a_{k} | < ϵ$

We start by proving that $1 ⟹ 2$ so assume that series converges. Let $S_{n} : = \sum_{k = 1}^{n} a_{k}$ be the sequence of partial sums, therefore we know that for any $ϵ$ there is an $N \in N_{0}$ such that for all $n \geq N, | S_{n} - L | < ϵ$ , note that $L - S_{n} & = ({lim}_{m \to \infty} S_{m}) - S_{n} & = {lim}_{m \to \infty} (S_{m} - S_{n}) & = {lim}_{m \to \infty} \sum_{k = n + 1}^{m} a_{k} & = \sum_{k = n + 1}^{\infty} a_{k}$ then it follows that $| \sum_{k = n + 1}^{\infty} a_{k} | = | S_{n} - L | < ϵ$ as needed.

Now we'll prove that $2 ⟹ 3$ so to show this is true, let $ϵ \in R^{+}$ therefore by considering $\frac{ϵ}{2}$ in our assumption we get an $N \in N_{1}$ such that for any $n \geq N$ we have that $| \sum_{k = n + 1}^{\infty} a_{k} | \leq \frac{ϵ}{2}$

Now let $a, b \geq N$ and we'll prove that $| \sum_{k = a + 1}^{b} a_{k} | < ϵ$ , to do this note the following $| \sum_{k = a + 1}^{b} a_{k} | & = | \sum_{k = a + 1}^{b} a_{k} + \sum_{k = b + 1}^{\infty} a_{k} - \sum_{k = b + 1}^{\infty} a_{k} | & = | \sum_{k = a + 1}^{\infty} a_{k} - \sum_{k = b + 1}^{\infty} a_{k} | & \leq | \sum_{k = a + 1}^{\infty} a_{k} | + | \sum_{k = b + 1}^{\infty} a_{k} | & < \frac{ϵ}{2} + \frac{ϵ}{2} = ϵ$ as needed.

We'll prove that $3 ⟹ 1$ , since we assume $3$ and use the notation for $S_{n}$ as the partial sums, then we can see that $| \sum_{k = n + 1}^{m} | = | S_{m} - S_{n} |$ and thus assuming $3$ is the same as assuming that $S_{n}$ is cauchy, but we know that any cauchy sequence is convergent and thus $S_{n}$ converges, which shows that $\sum_{n = 1}^{\infty} a_{n}$ converges.

Note that 2 informally says that tails converge and are arbitrarily small, and 3 essentially says that $S_{n}$ is a cauchy sequence because $\sum_{k = n + 1}^{m} a_{k} = S_{m} - S_{n}$

Summable

We say that the sequence

(a_{n})

is summable if the limit

\sum_{n = 1}^{\infty} a_{n}

exists.

Comparison Test

Consider two sequences of real numbers

(a_{n}), (b_{n}) : N_{1} \to R

with

| a_{n} | \leq b_{n}

for all

n \in N_{1}

, then if

(b_{n})

is summable then

(a_{n})

is summable and

| \sum_{n = 1}^{\infty} a_{n} | \leq \sum_{n = 1}^{\infty} b_{n}

while if

(a_{n})

is not summable, then

(b_{n})

is not summable.

Assume our hypothesis, and we'll show that

(a_{n})

is summable, to do this we'll use 2 of the cauchy criterion, so let

ϵ \in R^{+}

, also since

(b_{n})

is summable, by

3

of the cauchy criterion we obtain some

N \in N_{1}

such that for any

n, m \geq N

we have

| \sum_{k = n + 1}^{m} b_{k} | < ϵ

, but recall the inequalities we've assumed between

(a_{n}), (b_{n})

, which shows us that

| \sum_{k = n + 1}^{m} a_{k} | \leq \sum_{n = k + 1}^{m} | a_{k} | \leq \sum_{k = n + 1}^{m} b_{k} < ϵ

The first

\leq

follows from the generalized triangle inequality, the second follows from our assumed inequality. Thus

(a_{n})

is summable.

Suppose that

(a_{n})

is not summable, we'll show that

(b_{n})

is not summble, for if it were then by part one of the proof then

(a_{n})

would be which is a contradiction.

If the Absolute Valued Series Converges then so does the Original

\sum_{n = 1}^{\infty} | a_{n} |

converges then so does

\sum_{n = 1}^{\infty} a_{n}

Clearly

| a_{n} | \leq | a_{n} |

for all

n \in N_{1}

thus by considering

b_{n} = | a_{n} |

in the comparison test we have that

(a_{n})

is summable.

Non-Negative Series Converges iff Partial Sums are Bounded Above

Suppose that

a_{n} \geq 0

for every

n \in N_{1}

, then

(a_{n})

is summable iff

(S_{n})

is bounded above, where

S_{k} : = \sum_{n = 1}^{k} a_{n}

We required that $a_{n} \geq 0$ because if you consider the series $\sum_{n = 1}^{\infty} {(- 1)}^{(n + 1)}$ that has a sequence of partial sums of the form $1, 0, 1, 0, 1, 0, \dots$ which is clearly bounded but the limit doesn't exist.

Monotone Increasing Sequence with a Subsequence which is Bounded Above Implies Entire Sequence is Bounded Above

Suppose that

(a_{n})

is monotone increasing, and there is some subsequence

(a_{σ (n)})

that is bounded above, then

(a_{n})

is bounded above.

Cauchy Condensation Test

Suppose that

(a_{n}) : N_{1} \to R^{+}

is monotone decreasing then

\sum_{n = 1}^{\infty} a_{n} < \infty ⟺ \sum_{n = 0}^{\infty} 2^{n} a_{2^{n}} < \infty

Let's define

S_{n} = \sum_{k = 1}^{n} a_{k}

and

T_{n} = \sum_{k = 0}^{n} 2^{k} a_{2^{k}}

Assume that $\sum_{n = 0}^{\infty} 2^{n} a_{2^{n}}$ converges, which by definition means that $(T_{n})$ converges and is therefore bounded above, which means there is some $M$ such that for any $i \in N_{0}, T_{i} \leq M$ , we'll use this fact to show that $(S_{n})$ is bounded above by showing that it has a subsequence which is bounded above. Namely we will prove that $S_{2^{n} - 1} \leq t_{n - 1} \leq M$

Base case $n = 1$ , $S_{2^{1} - 1} = S_{1} = a_{1} = 2^{0} a_{2^{0}} = T_{0} \leq M$ as needed. Now asssume that it holds true for $n \in N_{1}$ , which is to say that $S_{2^{n} - 1} \leq T_{n - 1} \leq M$ and now let's prove that $S_{2^{n + 1} - 1} \leq T_{n} \leq M$

Note that in the induction step the following fact will be useful, which says for any $n \in N_{1}$ we have that $T_{n} - T_{n - 1} = 2^{n} a_{2^{n}}$ Now continuing on, we note the following

$S_{2^{n + 1} - 1} & = S_{2^{n} - 1} + \sum_{i = 2^{n}}^{2^{n + 1} - 1} a_{i} & \leq T_{n - 1} + \sum_{i = 2^{n}}^{2^{n + 1} - 1} a_{i} & \leq T_{n - 1} + 2^{n} a_{2^{n}} & = T_{n - 1} + (T_{n} - T_{n - 1}) & = T_{n} \leq M$ Note that going from the second line to the third comes from the fact that $(a_{n})$ is decreasing which means for any $x \in {2_{n}, \dots, 2^{n + 1} - 1}$ that $a_{2^{n}} \geq a_{x}$ additionally the the size of that set is $2^{n + 1} - 1 - 2^{n} + 1 = 2^{n} (2 - 1) = 2^{n}$ , which allow us to upper bound that summation by $2^{n} a_{2^{n}}$ , which shows the induction step true. Thus we've proven that $S_{n}$ is bounded above, and so by the MCT it converges which is to say that $\sum_{n = 1}^{\infty} a_{n} < \infty$

Now let's assume that $\sum_{n = 0}^{\infty} 2^{n} a_{2^{n}}$ converges, and show that the other one does as well, we'll follow a similar structure that in we show that $T_{n}$ is bounded above. Specifically we will show that $a_{1} + 2 \sum_{i = 2}^{2^{n}} a_{n} \geq T_{n}$ Since $(S_{n})$ is bounded above by some $M \in R$ then by adding $a_{1}$ to both sides we obtain $2 S_{2^{n}} \geq a_{1} + T_{n}$ which is to say that $2 M \geq a_{1} + T_{n}$ which shows that $T_{n}$ is bounded above, and since it is increasing we would know that it converges by the MCT.

For the base case of $n = 0$ we have $a_{1} + 2 a_{2} \geq a_{1} = T_{0}$ so it holds true. Now let $n \in N_{0}$ and suppose that $a_{1} + 2 \sum_{i = 2}^{2^{n}} a_{n} \geq T_{n}$ we need to prove that $a_{1} + 2 \sum_{i = 2}^{2^{n + 1}} a_{n} \geq T_{n + 1}$ , then notice that $a_{1} + 2 \sum_{i = 2}^{2^{n + 1}} a_{n} & = a_{1} + 2 \sum_{i = 2}^{2^{n}} a_{n} + 2 \sum_{i = 2^{n} + 1}^{2^{n + 1}} a_{n} & \geq T_{n} + 2 \sum_{i = 2^{n} + 1}^{2^{n + 1}} a_{n} & \geq T_{n} + 2 (2^{n} a_{2^{n + 1}}) & = T_{n} + 2^{n + 1} a_{2^{n + 1}} & = T_{n} + (T_{n + 1} - T_{n}) & = T_{n + 1}$ In this case the 3rd line follows by a similar argument to the previous induction step, but this team using the fact that for all $x \in {2^{n} + 1, \dots, 2^{n + 1}}$ we have $a_{x} \geq a_{2^{n + 1}}$ because $(a_{n})$ is monotone decreasing.

One over N to the p Convergence iff p is greater than One

\sum_{n = 1}^{\infty} \frac{1}{n^{p}} < \infty ⟺ p \geq 1

Recall that

\sum_{n = 1}^{\infty} \frac{1}{n^{p}}

converges iff

\sum_{n = 0}^{\infty} 2^{n} \frac{1}{({(2^{n})}^{p})} = \sum_{n = 0}^{\infty} 2^{n - n p} = \sum_{n = 0}^{\infty} {(2^{1 - p})}^{n}

which converges iff

2^{(1 - p)} \in (- 1, 1)

since

2^{(1 - p)}

is always positive then we just need

2^{(1 - p)} < 1

which is the same as

1 - p < \log_{2} (1) = 0

which is equivalent to

1 < p

Root Test

Suppose that

a_{n} \geq 0

for all

n \in N_{1}

and let

l = lim sup (\sqrt[n]{a_{n}})

l < 1

then

\sum_{n = 1}^{\infty} a_{n}

converges and if

l > 1

then

\sum_{n = 1}^{\infty}

diverges

Suppose everything in the hypothesis is true, let's prove that

\sum_{n = 1}^{\infty} a_{n}

converges. Clearly we can pick an

r \in (l, 1)

since

l < 1

and since

lim sup (\sqrt[n]{a_{n}}) = l

by using

ϵ = r - l \in R^{+}

, then we know that there is some

N \in N_{1}

such that for all

n \geq N

we have

| sup ({\sqrt[k]{a_{k}} : k \geq n}) - l | < ϵ

since

\sqrt[n]{a_{n}} \in {\sqrt[k]{a_{k}} : k \geq n}

then we must have

\sqrt[n]{a_{n}} \leq sup ({\sqrt[k]{a_{k}} : k \geq n})

as it's an upper bound, thus

| \sqrt[n]{a_{n}} - l | < | sup ({\sqrt[k]{a_{k}} : k \geq n}) - l | < ϵ

so that

\sqrt[n]{a_{n}} < l + ϵ = l + (r - l) = r

, in other words

a_{n} < r^{n}

for all

n \geq N

, then we construct the sequence by

$b_{n} : = a_{n}$ for $n \in [1, \dots N - 1]$
$b_{n} : = r^{n}$ if $n \geq N$

thus by construction we have

| a_{k} | = a_{k} \leq b_{k}

for all

k \in N_{1}

moreover we can confirm that

(b_{n})

is summable directly as

\sum_{n = 1}^{\infty} b_{n} = \sum_{n = 1}^{N - 1} b_{n} + \sum_{n = N}^{\infty} r^{n} = \sum_{n = 1}^{N - 1} b_{n} + \frac{r^{N}}{1 - r}

the final equality comes from a geometric series with an offset since the right hand side is the sum of two finite things then

(b_{n})

is summable and thus by the comparison test we conclude that

\sum_{n = 1}^{\infty} a_{n}

converges.

Ratio Test

Suppose that

{(a_{n})}_{n = 1}^{\infty}

is a sequence of positive terms. Show that if

{lim sup}_{n \to \infty} \frac{a_{n + 1}}{a_{n}} < 1

then

\sum_{n = 1}^{\infty} a_{n}

converges

Alternating Sequence

A sequence is alternating if it has the form

{(- 1)}^{n} a_{n}

{(- 1)}^{(n + 1)} a_{n}

where

a_{n} \geq 0

for all

n \in N_{1}

This characterization simply states that consecutive terms change sign.

Alternating Series

A series

\sum_{n = 1}^{\infty} a_{n}

is said to be alternating if

(a_{n})

is alternating.

Leibniz Alternating Series Test

Suppose that

(a_{n}) : N_{1} \to R

is a monotone decreasing sequence and

{lim}_{n \to \infty} a_{n} = 0

then the alternating series

\sum_{n = 1}^{\infty} {(- 1)}^{n} a_{n}

converges

Absolutely Convergent Series

A series

\sum_{n = 1}^{\infty} a_{n}

is said to be absolutely convergent if the series

\sum_{n = 1}^{\infty} | a_{n} |

converges.

Conditionally Convergent Series

A series

\sum_{n = 1}^{\infty} a_{n}

is said to be conditionally convergent if it converges but

\sum_{n = 1}^{\infty} a_{n}

does not.

Recall that $\sum_{n = 1}^{\infty} \frac{{(- 1)}^{n + 1}}{n}$ converges to $\ln (2)$ and is conditionally convergent because the harmonic series diverges.

Series Rearrangement

A rearrangment of a series

\sum_{n = 1}^{\infty}

is another series

\sum_{n = 1}^{\infty} a_{π (n)}

where

π

is a permutation of

N_{1}

The above definition formalizes the idea of taking a series and then looking at it with the same terms in a different order. Also note that the definition of a series is the limit of the partial sums, which is an entirely different thing than the $+$ operation, thus we have no idea whether or not the new series will have the same limit, or even exist.

Every Rearrangment of an Absolutely Convergent Series converges to the same Limit

As per title.

🏗️ ΘρϵηΠατπ🚧 (under construction)

🏗️ $Θ ρ ϵ η Π α τ π$ 🚧 (under construction)