# Sequences

## Definition: Sequence

A sequence is a function whose domain is the set of natural numbers.

The nth element of the sequence is denoted by a_{n} instead of f(n).

**Example:**

a_{n} = 1/n

a_{1} = 1, a_{2} = 1/2, a_{3} = 1/3, a_{4} = 1/4, ...

## Definition: Monotone increasing sequence

A sequence is monotone increasing if for all natural n _{n} <= a_{n+1}_{1} <= a_{2} <= a_{3} <= ... <= a_{n}).

**Example:**

a_{n} = n is monotone increasing.

a_{1} = 1, a_{2} = 2, a_{3} = 3, a_{4} = 4, ...

## Definition: Monotone decreasing sequence

A sequence is monotone decreasing if for all natural n _{n} >= a_{n+1}_{1} >= a_{2} >= a_{3} >= ... >= a_{n}).

**Example:**

a_{n} = 1/n is monotone increasing.

a_{1} = 1, a_{2} = 1/2, a_{3} = 1/3, a_{4} = 1/4, ...

## Finite limit of a sequence

Consider the sequence a_{n} = 1/n.

a_{1} = 1

a_{2} = 1/2 = 0.5

a_{3} = 1/3 ≈ 0.33

a_{4} = 1/4 = 0.25

a_{5} = 1/5 = 0.2

a_{6} = 1/6 ≈ 0.17

a_{7} = 1/7 ≈ 0.14

a_{8} = 1/8 ≈ 0.12

a_{9} = 1/9 ≈ 0.11

a_{10} = 1/10 = 0.1

As n increases, the terms of the sequence get closer to 0. If we represent the terms as points on a line, the points a_{n} are clustered near 0 as n grows.

It is said that a_{n} tends to 0, or that it has limit 0.

This is expressed symbolically by: _{n} = 0_{n} -> 0

## Definition: Finite limit

lim a_{n} = a <=> for all ε>0 there exists N natural / for all n > N _{n} < a + ε_{n} - a| < ε

For any positive number ε, no matter how small, we can find a natural N sufficiently large such that from the index N onwards, it holds that _{n} - a| < ε

In other words, if we consider a neighborhood of a with any radius there will always be an index N such that from N onwards all the terms of the sequence belong to that neighborhood.

## Infinite limit of a sequence

Consider the sequence a_{n} = n^{2}.

a_{1} = 1

a_{2} = 4

a_{3} = 9

a_{4} = 16

...

a_{10} = 100

...

a_{100} = 10.000

As n increases, a_{n} does not tend to a definite limit, but grows beyond bound. It is said that a_{n} tends to infinite.

## Definition: Infinite limit

lim a_{n} = +inf <=> for all K>0 there exists N natural / for all n > N a_{n} > K.

For any positive number K (as large as you want), we can find a natural N such that a_{N} and all the subsequent terms are greater than K. This means that a_{n} can be greater than any bound, provided that n is large enough.

Similarly, we define lim a_{n} = -inf <=> for all K<0 there exists N natural / for all n > N a_{n} < K.

## Definition: Convergence and divergence

If a sequence has a finite limit a, then it is said to be convergent and it converges to a.

A sequence that has an infinite limit is called divergent.

A sequence that has no limit is called oscillating.

The sequence a_{n} = 1/n converges to 0.

The sequence a_{n} = n^{2} is divergent.

The sequence a_{n} = sen n is oscillating, since its values vary between 1 and -1.

## Properties of the finite limit of a sequence

### Uniqueness of the limit

The limit of a convergent sequence is unique..

H) lim a_{n} = b

C) b is unique

**Demonstration:**

The proof is by contradiction.

We assume that a_{n} has two different limits b and c.

We assume that b > c.

lim a_{n} = b => (by def. of finite limit of a sequence) for all ε>0 there exists n_{1} natural / for all _{1}_{n} < b + ε

lim a_{n} = c => (by def. of finite limit of a sequence) for all ε>0 there exists n_{2} natural / for all _{2}_{n} < c + ε

Consider ε such that

Let N = max {n_{1},n_{2}}

For all n > N it holds that

- b - ε < a
_{n}< b + ε - c - ε < a
_{n}< c + ε

Absurd, since a_{n} cannot belong to two disjoint neighborhoods.

The absurd comes from supposing

Therefore b = c.

### Limit of a "squeezed" sequence

If a sequence is "squeezed" between two sequences that have the same limit, then it has that limit.

H) lim a_{n} = lim b_{n} = p

For all n > n_{0} a_{n} <= c_{n} <= b_{n}

C) lim c_{n} = p

**Demonstration:**

lim a_{n} = p => (by def. of limit of a sequence) for all _{1} > 0_{1} natural / for all _{1}_{1} < a_{n} < p + ε_{1}

lim b_{n} = p => (by def. of limit of a sequence) for all _{2} > 0_{2} natural / for all _{2}_{2} < b_{n} < p + ε_{2}

Let N = max {n_{0}, n_{1}, n_{2}}

For all n > N it holds that _{1} < a_{n} <= c_{n} <= b_{n} < p+ε_{2}

p-ε_{1} < c_{n} < p+ε_{2}

Let ε = min {ε_{1}, ε_{2}}

For all n > N p-ε < c_{n} < p+ε

=> (by def. of limit of a sequence) _{n} = p.

## Operations with limits

The limit of the sum, product and quotient of sequences is determined by the same rules as for continuous variable functions. The demonstrations are identical, just replace f(x) by a_{n} and consider that n always tends to +infinite. Here we will prove only the limit of a sum. To see the other rules visit the page on operations with limits.

### Limit of a sum of sequences

If two sequences have finite limit, then the limit of the sum equals the sum of the limits of the sequences.

H) lim a_{n} = a, lim b_{n} = b

C) lim a_{n} + b_{n} = a + b

**Demonstration:**

We want to prove that, given _{n} + b_{n}) - (a+b)| < ε

Let ε' = ε/2

lim a_{n} = a => (by def. of finite limit of a sequence) for all _{0} natural / for all _{0}_{n} - a| < ε'

lim b_{n} = b => (by def. of finite limit of a sequence) for all _{1} natural / for all _{1}_{n} - b| < ε'

Let N = max {n_{0}, n_{1}}

For all n > N it holds that:

- |a
_{n}- a| < ε' - |b
_{n}- b| < ε'

=> |a_{n} - a| + |b_{n} - b| < 2ε' = ε

|(a_{n} + b_{n}) - (a+b)| = |(a_{n} - a) + (b_{n} - b)| <= (*) _{n} - a| + |b_{n} - b| < ε

(*) Triangle inequality: |x + y| <= |x| + |y|

Summarizing, given ε>0 there exists N / for all n > N |(a_{n} + b_{n}) - (a+b)| < ε

=> (by def. of finite limit of a sequence) lim a_{n} + b_{n} = a + b

## Definition: Equivalent sequences

Two sequences are equivalent if the limit of their quotient is 1.

## Definition: Bounded sequence

M is an upper bound of the sequence a_{n} if a_{n} < M for all n.

m is a lower bound of the sequence a_{n} if a_{n} > m for all n.

A sequence is bounded if it has both upper bound and lower bound.

## Theorem

If a sequence is monotone and bounded, then it converges.

H) a_{n} monotone

There exist m and M / m < a_{n} < M for all n.

C) lim a_{n} = b

**Demonstration:**

We want to prove that there exists N / for all n > N |a_{n} - b| < ε.

Suppose that a_{n} is increasing (if we suppose that it is decreasing, the demonstration is analogous).

a_{n} < M for all n

That means that the set of all the terms of the sequence _{1}, a_{2}, a_{3}, ...}

Let ε>0

b - ε is not an upper bound of S since it is lower than the least upper bound.

=> there exists N / a_{N} > b-ε.

a_{n} is increasing => for all n > N a_{n} >= a_{N} => a_{n} > b-ε => -(a_{n} - b) < ε (1)

b+ε is also an upper bound of S

=> for all n a_{n} < (b+ε) => => a_{n} - b < ε (2)

=> From 1) and 2) for all n > N |a_{n} - b| < ε

## Theorem

If a sequence is convergent then it is bounded.

H) a_{n} convergent

C) a_{n} bounded

**Demonstration:**

a_{n} is convergent, that means it has a finite limit: lim a_{n} = a

=> (by def. of finite limit of a sequence) for all ε>0 there exists N / for all _{n} < a+ε

=> (by def. of bounded sequence) a_{n} is bounded.

**Note:** The converse is not true. A bounded sequence is not necessarily convergent.

Counterexample: a_{n} = (-1)^{n} is bounded but not convergent.

-1, 1, -1, 1, -1, 1, -1, 1, ...

## Definition: Pair of convergent monotone sequences (PCMS)

((a_{n}),(b_{n})) is a pair of convergent monotone sequences if

a) a_{n} is increasing and b_{n} is decreasing.

b) For all natural n a_{n} <= b_{n}

c) For all ε>0 there exists h natural / b_{h} - a_{h} < ε

**Example:**

a_{n} = -1/n, b_{n} = 1/n

_{n}is increasing.

We must prove that a_{n+1} >= a_{n}, that is, a_{n+1} - a_{n} >= 0

-1 -1 -n + n + 1 1 ----- - --- = ------------ = -------- > 0 n+1 n n(n+1) n^{2}+ n

_{n}is decreasing.

We must prove that b_{n+1} <= b_{n}, that is, b_{n} - b_{n+1} >= 0

1 1 n + 1 - n 1 --- - ------ = ------------ = -------- > 0 n n+1 n(n+1) n^{2}+ n

_{n}< b

_{n}

-1 1 --- < --- since -n < n for all n. n n

_{h}- a

_{h}< ε

1 -1 2 --- - --- = --- < ε h h h

For that to be true, it suffices to choose h > 2/ε

## Property: Any PCMS has a boundary

((a_{n}),(b_{n})) is a PSMC => there exists c / for all n _{n} <= c <= b_{n}_{n} = c-_{n} = c+.

_{n} = c-_{n} approaches c from the left, and _{n} = c+_{n} approaches c from the right.

## The number e

Often, a number is defined by an infinite sequence a_{n} of approximations; that is, the value a is given by the value a_{n} with any desired degree of accuracy if the index n is chosen large enough.

This is the case of the number e (e = 2,718281...), which can be defined as the limit of the sequence a_{n} = (1 + 1/n)^{n} or the limit of the sequence b_{n} = (1 + 1/n)^{n+1}.

We will prove that both sequences are a PCMS.

_{n}is increasing.

Demonstration:

By using Newton's Binomial formula, we can express (1+1/n)^{n} as:

a_{n+1} has one more summand than a_{n} and each summand is positive. If we prove that each summand of a_{n} is less than or equal to the corresponding summand of a_{n+1} we will prove that a_{n} is increasing.

n! ? (n+1)! ---------- <= ------------------ (n-i)!i!n^{i}(n+1-i)!i!(n+1)^{i}n(n-1)...(n-i+1) ? (n+1)(n)...(n+1-i+1) --> i factors ------------------- <= -------------------------- n.n....n (n+1)(n+1)...(n+1) --> i factors (n-1) (n-i+1) ? n n+1-i+1 ------.....--------- <= -----.....---------- n n n+1 n+1 1 i-1 ? 1 i-1 (1 - ---)...(1 - ---) <= (1 - -----)...(1 - -----) n n n+1 n+1

Each factor is of the form 1 - p/n where p is the same on both sides of the inequalities.

1 - p/n < 1 - p/(n+1)

Then each factor of the left hand side is lower than the corresponding factor of the right hand side.

Therefore, each summand of a_{n} is lower than the corresponding summand of a_{n+1}.

=> a_{n} is increasing.

_{n}is decreasing.

bBernoulli's inequality: (1+p)_{n}= (1 + 1/n)^{n+1}b_{n+1}= (1 + 1/n+1)^{n+2}= (1 + 1/n+1)^{n+1}.(1 + 1/n+1) ? b_{n+1}<= b_{n}? (1 + 1/n+1)^{n+1}.(1 + 1/n+1) <= (1 + 1/n)^{n+1}(1 + 1/n)^{n+1}? 1 ------------------- >= 1 + ----- (1 + 1/n+1)^{n+1}n+1 n+1/n^{n+1}? 1 ( ------------ ) >= 1 + ----- n+2/n+1 n+1 n^{2}+ 2n + 1^{n+1}? 1 ( --------------- ) >= 1 + ----- n^{2}+ 2n n+1 1^{n+1}? 1 ( 1 + --------------- ) >= 1 + ----- n^{2}+ 2n n+1

^{q}>= 1 + pq if p>=-1 and q>1

1^{n+1}n+1 ( 1 + ---------- ) >= 1 + --------- n^{2}+ 2n n^{2}+ 2n n+1 ? 1 1 + ---------- >= 1 + ----- n^{2}+ 2n n+1 n+1 ? 1 ---------- >= ----- n^{2}+ 2n n+1 n^{2}+ 2n + 1 > n^{2}+ 2n is true for all n.

_{n}< b

_{n}

a_{n}= (1 + 1/n)^{n}b_{n}= (1 + 1/n)^{n+1}? b_{n}- a_{n}> 0 ? (1+1/n)^{n+1}- (1+1/n)^{n}> 0 ? (1+1/n)^{n}(1+1/n) - (1+1/n)^{n}> 0

Factoring out the common factor:

(1+1/n)^{n}(1+1/n - 1) = 1/n(1+1/n)^{n}> 0 for all n >= 1.

_{n}- a

_{n}< ε

(1) (2) b_{n}- a_{n}= 1/n(1+1/n)^{n}= (1/n)a_{n}< (1/n)b_{n}< (1/n)b_{1}= (1/n)4 < ε

(1) a_{n} < b_{n}

(2) b_{n} decreasing

It suffices to choose n > 4/ε

Therefore, a_{n} and b_{n} is a PCMS. The boundary is the number e.

n=1: 2 < e < 4 n=2: 2,25 < e < 3,375 n=3: 2,37 < e < 3,16 n=4: 2,44 < e < 3,05 ... n=100: 2,70 < e < 2,73