ANALYSIS I
Induction, Sequences and Limits
1/29/96 

Chapter 3 deals with limits and the topology of IR. First we recall the concept of induction.

Theorem. (Principle of Mathematical Induction.) Suppose that a statement p(n) is defined for each natural number n. If

  1. p(1) is true
  2. ( (p(n) true) Þ (p(n+1) true) ) is a true statement for each n Î IN,
then p(n) is a true statement for each natural number n.
 
Pf. Suppose to the contrary that the set B: = {n Î IN|p(n) false } is not empty. Notice that 1 does not belong to B. Let N be the smallest element of B (possible since you can take a minimum of a finite set of integers), then set n: = N-1. Observe by assumption (1) that n Î IN, and by the definition of B that p(n) is true. By assumption (2), it follows that p(n+1) is true. But n+1 = N. Contradiction. Hence B must be empty.  [¯]


Example. These will useful in our study of convergence. Both are proved by induction.

  1.   åj = 0n rj = [(1-rn+1)/(1-r)],  if r ¹ 1.
  2.   1+n a £ (1+a)n,  if a > 0 & n Î IN. (Bernoulli's inequality)
Defn. If e > 0 an e-neighborhood of a is defined to be the set
Ne(a) : = {x Î IR| |x-a| < e}.
Notice that Ne(a) = (a-e, a+e).

Defn. A sequence of real numbers is defined to be a mapping from the natural numbers IN to the reals and is denoted by a1, a2,a3,... or by {an}n = 1¥. The following definitions are used throughout the course:

  1. {an} is bounded, if |an|£ K, for all n Î IN.
  2. {an} is convergent to a, denoted by limn®¥ an = a, if each e-nbhd of a contains all but a finite number of terms of the sequence. We also use the shorter notation an ® a when there is no ambiguity on the indices.
Example. The following are examples of sequences:
  1.   1/2, 1/3, 1/4, ¼
  2.   1, r, r2, r3, ¼
  3.   1,  1+r,  1+r+r2,  1+r+r2+r3, ¼
Lemma.  limn®¥an = a   if and only if

for every e > 0, there exists N Î INso that if n ³ IN, then |an - a|< e.

In short hand this reads ` "e > 0, $N = N(e) Î IN ' n ³ IN(e) Þ  |an - a| < e.'
 
Pf. Notice that if a statement is true except for at most a finite number of terms, then there is a a largest integer for which it is not true. Take N to be that integer's successor. [¯]


Example.

  1. limn®¥ [1/n] = 0.

    2. Proof. Use the Archimedean Principle.
  2. limn®¥ [(3n2-1)/(n2+n+25)] = 3.

    3. (Hint: For a given e > 0, use N: = max{76,4N1} where N1 is the `cutoff' for Example 1, i.e. any integer larger than 1/e)
  3. If |r| < 1, then  rn ® 0 .


    4. Pf. If r = 0, then the conclusion follows straight away. Suppose that 0 < |r| < 1, then if b: = 1/|r| -1 we see that b > 0 and |r| = 1/(1+b). By Bernoulli's inequality, |rn|-1 = (1+b)n ³ 1+nb. Inverting this inequality gives |rn-0|£ 1/(1+nb). By example 1, pick N so that 1/n < be if n ³ N. Hence,

    |rn-0|£ 1
    1+nb    		 <  1
    nb    		 < e,   if  n ³ N.   [¯]
  4. limn®¥ an = 1/(1-r),  if an : = 1+r+r2+¼ +rn and |r| < 1.


    5. Pf. If r = 0, the conclusion follows immediately. We may suppose then that 0 < |r| < 1. In this case, we use the identity above, i.e.

    an: =  n
    å
    j = 0    		 rn =  1-rn+1
    1-r
    to see that
    an-a = -rn+1/(1-r)
    where a: = 1/(1-r). Now, given e > 0, by example 3 there is an N0 such that n ³ N0 implies |rn| < ([(1-|r|)/(|r|)])e. Combined with the displayed equation, this gives |an-a| < e if n ³ N0. [¯]
Theorem.  If limn®¥ an exists, then it is unique.
 
Pf. Suppose that limn®¥ an = A1 and limn®¥ an = A2 and that A1 ¹ A2. Set e: = |A1-A2|/2. Now e > 0 so there exists N1, such that if n ³ N1 then |an-A1| < e. Since the sequence converges to A2, we also have that there exists N2, such that if n ³ N2 then |an-A2| < e. Let N: = N1+N2, then N is larger than both N1 and N2 and so
|A1 - A2|£|A1 - aN| + |A2 - aN|< 2 e = |A1 - A2|, 
 
which gives a contradiction.   [¯]


Theorem.  Each convergent sequence is bounded.
 

Pf. Suppose that limn®¥an = a. Let e: = 1, then there is an integer N such that an Î Ne(a) if n ³ N. This means that a-1 < an < a+1, if n ³ N. If M: = max{a+1, a1, a2, ...,aN-1} and m: = min{a-1, a1, a2, ..., aN-1}, then
m £ an£ M,   for all n.  [¯]
 

Note. Not every bounded sequence is convergent. For example, the sequence an : = (-1)n is bounded, but the sequence is not convergent. To see this take e = 1.

File translated from TEX by TTH, version 1.2.