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 an instead of f(n).

Example:

an = 1/n

a1 = 1, a2 = 1/2, a3 = 1/3, a4 = 1/4, ...

Definition: Monotone increasing sequence

A sequence is monotone increasing if for all natural n an <= an+1 (a1 <= a2 <= a3 <= ... <= an).

Example:

an = n is monotone increasing.

a1 = 1, a2 = 2, a3 = 3, a4 = 4, ...

Definition: Monotone decreasing sequence

A sequence is monotone decreasing if for all natural n an >= an+1 (a1 >= a2 >= a3 >= ... >= an).

Example:

an = 1/n is monotone increasing.

a1 = 1, a2 = 1/2, a3 = 1/3, a4 = 1/4, ...

Finite limit of a sequence

Consider the sequence an = 1/n.

a1 = 1
a2 = 1/2 = 0.5
a3 = 1/3 ≈ 0.33
a4 = 1/4 = 0.25
a5 = 1/5 = 0.2
a6 = 1/6 ≈ 0.17
a7 = 1/7 ≈ 0.14
a8 = 1/8 ≈ 0.12
a9 = 1/9 ≈ 0.11
a10 = 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 an are clustered near 0 as n grows.

Sequence with limit 0

It is said that an tends to 0, or that it has limit 0.
This is expressed symbolically by: lim an = 0 or, occasionally, by the short notation an -> 0.

Definition: Finite limit

lim an = a <=> for all ε>0 there exists N natural / for all n > N a - ε < an < a + ε, or what is the same, |an - 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 |an - 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 an = n2.

a1 = 1
a2 = 4
a3 = 9
a4 = 16
...
a10 = 100
...
a100 = 10.000

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

Definition: Infinite limit

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

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

Similarly, we define lim an = -inf <=> for all K<0 there exists N natural / for all n > N an < 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 an = 1/n converges to 0.
The sequence an = n2 is divergent.
The sequence an = 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 an = b
C) b is unique

Demonstration:

The proof is by contradiction.
We assume that an has two different limits b and c.
We assume that b > c.

lim an = b => (by def. of finite limit of a sequence) for all ε>0 there exists n1 natural / for all n > n1 b - ε < an < b + ε;

lim an = c => (by def. of finite limit of a sequence) for all ε>0 there exists n2 natural / for all n > n2 c - ε < an < c + ε

Consider ε such that c+ε < b-ε, that is, ε < (b - c)/2

Let N = max {n1,n2}

For all n > N it holds that

  • b - ε < an < b + ε
  • c - ε < an < c + ε

Absurd, since an cannot belong to two disjoint neighborhoods.
The absurd comes from supposing b ≠ c.
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 an = lim bn = p
    For all n > n0 an <= cn <= bn
C) lim cn = p

Demonstration:

lim an = p => (by def. of limit of a sequence) for all ε1 > 0 there exists n1 natural / for all n > n1 p - ε1 < an < p + ε1

lim bn = p => (by def. of limit of a sequence) for all ε2 > 0 there exists n2 natural / for all n > n2 p - ε2 < bn < p + ε2

Let N = max {n0, n1, n2}

For all n > N it holds that p-ε1 < an <= cn <= bn < p+ε2

p-ε1 < cn < p+ε2

Let ε = min {ε1, ε2}

For all n > N p-ε < cn < p+ε

=> (by def. of limit of a sequence) lim cn = 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 an 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 an = a, lim bn = b
C) lim an + bn = a + b

Demonstration:

We want to prove that, given ε > 0, there exists N > 0 such that for all n > N |(an + bn) - (a+b)| < ε.

Let ε' = ε/2

lim an = a => (by def. of finite limit of a sequence) for all ε' > 0 there exists n0 natural / for all n > n0 |an - a| < ε'.

lim bn = b => (by def. of finite limit of a sequence) for all ε' > 0 there exists n1 natural / for all n > n1 |bn - b| < ε'.

Let N = max {n0, n1}

For all n > N it holds that:

  • |an - a| < ε'
  • |bn - b| < ε'

=> |an - a| + |bn - b| < 2ε' = ε

|(an + bn) - (a+b)| = |(an - a) + (bn - b)| <= (*) |an - a| + |bn - b| < ε

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

Summarizing, given ε>0 there exists N / for all n > N |(an + bn) - (a+b)| < ε

=> (by def. of finite limit of a sequence) lim an + bn = 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 an if an < M for all n.
m is a lower bound of the sequence an if an > 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) an monotone
     There exist m and M / m < an < M for all n.
C) lim an = b

Demonstration:

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

Suppose that an is increasing (if we suppose that it is decreasing, the demonstration is analogous).

an < M for all n

That means that the set of all the terms of the sequence S = {a1, a2, a3, ...} has a least upper bound (the smallest of the upper bounds), let’s call it b.

Let ε>0

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

=> there exists N / aN > b-ε.

an is increasing => for all n > N an >= aN => an > b-ε => -(an - b) < ε (1)


b+ε is also an upper bound of S

=> for all n an < (b+ε) => => an - b < ε (2)


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

Theorem

If a sequence is convergent then it is bounded.

H) an convergent
C) an bounded

Demonstration:

an is convergent, that means it has a finite limit: lim an = a

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

=> (by def. of bounded sequence) an is bounded.

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

Counterexample: an = (-1)n is bounded but not convergent.

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

Definition: Pair of convergent monotone sequences (PCMS)

((an),(bn)) is a pair of convergent monotone sequences if
a) an is increasing and bn is decreasing.
b) For all natural n an <= bn
c) For all ε>0 there exists h natural / bh - ah < ε

Pair of convergent monotone sequences

Example:

an = -1/n, bn = 1/n

  • an is increasing.

    We must prove that an+1 >= an, that is, an+1 - an >= 0

    -1        -1    -n + n + 1       1
    -----  -  --- = ------------ = -------- > 0
    n+1      n       n(n+1)      n2 + n
            
  • bn is decreasing.

    We must prove that bn+1 <= bn, that is, bn - bn+1 >= 0

    1       1         n + 1 - n         1
    --- - ------ = ------------ = -------- > 0
     n     n+1       n(n+1)      n2 + n
            
  • For all n an < bn
    -1     1
    --- < --- since -n < n for all n.
     n      n
  • Given ε>0, there exists h / bh - ah < ε
    1    -1      2                          
    --- - --- = --- < ε 
     h     h      h
            

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

    Property: Any PCMS has a boundary

    ((an),(bn)) is a PSMC => there exists c / for all n an <= c <= bn, lim an = c- and lim bn = c+.

    lim an = c- means that an approaches c from the left, and lim bn = c+ means that bn approaches c from the right.

    Boundary of a PCMS

    The number e

    Often, a number is defined by an infinite sequence an of approximations; that is, the value a is given by the value an 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 an = (1 + 1/n)n or the limit of the sequence bn = (1 + 1/n)n+1.

    We will prove that both sequences are a PCMS.

  • an is increasing.

    Demonstration:

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

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

         n!       ?         (n+1)!
    ---------- <= ------------------
    (n-i)!i!ni     (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 an is lower than the corresponding summand of an+1.

    => an is increasing.

  • bn is decreasing.
    bn = (1 + 1/n)n+1
    bn+1 = (1 + 1/n+1)n+2 = (1 + 1/n+1)n+1.(1 + 1/n+1)
             ?
    bn+1 <= bn
                                                    ?
    (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
    
      n2 + 2n + 1  n+1     ?              1
    ( --------------- )          >=    1 + -----
         n2 + 2n                                n+1    
      
                    1            n+1     ?             1
    ( 1 + --------------- )         >=    1 + -----		
                n2 + 2n                              n+1
            
    Bernoulli's inequality: (1+p)q >= 1 + pq if p>=-1 and q>1
                 1         n+1           n+1
    ( 1 + ---------- )   >= 1 + ---------		
             n2 + 2n                 n2 + 2n
    	  
              n+1     ?            1  
    1 + ----------  >=  1 + -----
           n2 + 2n               n+1
    	
       n+1     ?      1
    ----------  >=  -----
    n2 + 2n        n+1
    
    n2 + 2n + 1 > n2 + 2n is true for all n.
  • For all n an < bn
    an = (1 + 1/n)n
    bn = (1 + 1/n)n+1
    
                ?
    bn - an > 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.
  • Given ε>0 there exists n natural / bn - an < ε
     
                                                           (1)           (2)
    bn - an = 1/n(1+1/n)n = (1/n)an < (1/n)bn < (1/n)b1 = (1/n)4 < ε

    (1) an < bn
    (2) bn decreasing

    It suffices to choose n > 4/ε

    Therefore, an and bn 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