Saturday, September 09, 2006

Cauchy's Criterion

Cauchy's criterion is a well known criteria for when an infinite sum converges, that is, has a finite limit.

Augustin Cauchy was not the first to come up with the criteria. Leonhard Euler, for example, used a similiar criteria. It may be that the significance of the criteria became appreciated in the context of Cauchy's great work on the foundations of calculus.

Definition 1: Cauchy Sequence

A sequence si is Cauchy Sequence if and only if given any positive number ε, there exists an integer N such that if m,n are greater than N, then absolute(sm - sn) is less than ε

In other words, elements of the sequence get arbitrarily close to one another.

I will need a few properties of absolute inequalities:

Lemma 1: absolute(a - b) ≤ absolute(a) + absolute(b)

Proof:

(1) Case I: a - b is nonnegative

So abs(a-b) = a - b

If b ≥ 0, then a - b ≤ a ≤ abs(a) + abs(b)

If b is less than 0, then a - b = a + abs(b) ≤ abs(a) + abs(b)

(2) Case II: a - b is negative

So abs(a-b) = -(a-b) = b - a = abs(b - a)

Using step #1, we know that abs(b - a) ≤ abs(b) + abs(a) = abs(a) + abs(b)

So that:

abs(a - b) ≤ abs(a) + abs(b)

QED

Lemma 2: abs(a) - abs(b) ≤ abs(a - b)

Proof:

(1) Case I: a - b is nonnegative so that abs(a - b) = a - b

If a ≥ 0, then abs(a - b) = a - b ≥ abs(a) - abs(b)

NOTE: It is = except for the case where b is negative.

If a is less than 0, then abs(b) is greater than abs(a) and abs(a) - abs(b) must be a negative number.

(2) Case II: a - b is negative and abs(a - b) = -(a - b) = b - a

If a is ≥ 0, then abs(b) is greater than a and abs(a) - abs(b) is a negative number.

If a is less than 0 and b is less than 0, then b - a = b + abs(a) = abs(a) - abs(b) so that abs(a - b) = abs(a) - abs(b)

If a is less than 0 and b ≥ 0, then b - a = b + abs(a) = abs(a) + abs(b) ≥ abs(a) - abs(b).

QED

Here are some properties of Cauchy Sequences which I will use below:

Lemma 3: Any convergent sequences is a Cauchy Sequence

Proof:

(1) Let ai be a convergent sequence (that is, as ai gets larger, it approaches a limit) so that it's limit = L. [See definition 7, here for definition of a convergent sequence]

(2) So from the above definition, we know for any positive number ε, there exists a positive number N such that:

if n is greater than N, then absolute(an - L) is less than ε

(3) So, for a value (1/2)ε, there exists an integer N such that if n is greater than N, absolute(an - L) is less than (1/2)ε

(3) So let's assume that we have two integers m,n both greater than N.

(4) This means that in both cases absolute(am - L) is less than (1/2)ε and absolute(an - L) is less than (1/2)ε

(5) This gives us:

absolute(am - an) = absolute([am - L] - [an - L]) ≤ absolute(am - L) + absolute(an - L) [See Lemma 1 above]

(6) Finally,

absolute(am - L) - absolute(an - L) is less than (1/2)ε + (1/2)ε = ε

QED

Lemma 4: A Cauchy Sequence has a bound

Proof:

(1) Let (ai) be a Cauchy Sequence.

(2) Then, for any positive number ε greater than 0, there is an integer N such that:

for any integer m,n ≥ N, abs(an - am) is less than ε [See Definition of a Cauchy Sequence above]

(3) So that if we ε = 1 (since ε can be any positive number), we have:

abs(an) - abs(am) ≤ abs(an - am) less than 1 for all n,m ≥ N. [See Lemma 2 above]

(4) Let m = N (since m can be any integer ≥ N), then we have:

abs(an) - abs(aN) is less than 1 which means that:

abs(an) is less than abs(aN) + 1 for n ≥ N.

(5) Now, let n = N (since n can be any integer ≥ N), then we have:

abs(aN) - abs(am) is less than 1 which means that:

abs(am) is greater than abs(aN) - 1 for all n ≥ N.

(6) So, for all n, we have:

abs(an) is less than max { abs(a1), ..., abs(aN-1), abs(aN) + 1 }

and

abs(an) is greater than min { abs(an1), ..., abs(aN-1), abs(aN) - 1 }

(7) This shows that for all finite subsets of the sequence, there exists a bound for ai where upper bound = max { abs(a1), ..., abs(aN-1), abs(aN) + 1 } and a lower bound = min { abs(a1, ..., abs(aN-1), abs(aN)-1 }

QED

Lemma 5: If a Cauchy Sequence has a subsequence convergent to b, then the Cauchy sequence itself converges to b.

Proof:

(1) Let an be a Cauchy sequence with the subsequence ain convergent to b.

(2) By the definition of convergence, we know that for a positive number ε/2, there exists an integer M such that for all n ≥ M abs(ain - b) ≤ ε/2.

(3) By the definition of a Cauchy sequence, we know that there exists an integer n0 such that for all m,n ≥ n0, abs(an - am) ≤ ε/2.

(4) Now, if iM (this is the start of the subsequence that converges) is less than n0, we can always find a M' which is greater than M such that iM' ≥ n0.

We can assume this since we are assuming an infinite subsequence.

(5) So for all n ≥ n0, we have:

abs(an - b) = abs(an - aiM' + aiM' - b) ≤ abs(an - aiM') + abs(aiM' - b) [See Lemma 1 above]

(6) Now, abs(an - aiM') + abs(aiM' - b) is less than ε/2 + ε/2 = ε

We know that abs(an - aiM') is less than ε/2 from the definition of a Cauchy sequence.

We know that abs(aiM') is less than ε/2 from the definition of the convergent sequence.

(7) Now putting this all together gives us that:

abs(an - b) ≤ ε

Which by definition (see Definition 7, here) means that lim(an) = b.

QED

Lemma 6: Every real Cauchy sequence is convergent.

Proof:

(1) By Lemma 4 above, every Cauchy sequence is bounded.

(2) So, by the Bolzano-Weierstrass Theorem (see Theorem, here), every Cauchy sequence has a convergent subsequence.

(3) So, by Lemma 5 above, every Cauchy sequence is convergent.

QED

Lemma 7: A sequence of reals converges if and only if it is a Cauchy sequence

Proof:

(1) By Lemma 6 above, we know that a Cauchy sequence is convergent.

(2) By Lemma 3 above, we know that a convergent sequence is a Cauchy sequence.

QED

Here is the Criterion:

Theorem: Cauchy's Criterion

A series ai is convergent (that is, has a finite limit) if and only if for every positive number ε, there exists a positive integer N such that:

for all n greater than N and p ≥ 1:

absolute(an+1 + an+2 + ... + an+p) is less than ε

Proof:

(1) Let sn = ∑ ai

The assumption here is that i ranges from 0 to n.

(2) sn converges if and only if it is a Cauchy Sequence. [See Lemma 7 above]

(3) Assume than sn is a Cauchy Sequence.

(4) Then, for every positive number ε, there exists a number N such that for all integers n,m greater than N, absolute(sm - sn) is less than ε [See Definition 1 above]

(5) Let's assume that m is greater than n.

At this point, we've made no assumption about m or n and this is consistent with our assumption in step #3.

(6) We know that there exists an integer p ≥ 1 such that m = n + p

(7) Based on the definition of sn, we can see that:

absolute(sm - sn) = absolute(sn+p - sn) = absolute(an+1 + an+2 + ... + an+p)

(8) Now, using step #6, we can see that ∑ ai is convergent if and only if the conditions of the given apply.

QED

References

10 comments :

The Absolute Advantage said...

Are Cauchy sequences bounded for all numbers or just for real numbers?

Larry Freeman said...

Great question. Cauchy sequences are applicable to any metric space.

Wikipedia has a very good article on the subject here.

-Larry

adnan said...

adnan
is every cauchy sequence is convergent?

Larry Freeman said...

Hi Adnan,

Yes, every Cauchy sequence, by definition, converges.

If a sequence doesn't converge, then it isn't a Cauchy sequence.

-Larry

Anonymous said...

Thank you, thank you, thank you. This post is so much easier to understand then my text book.

Sarah said...

Finally! Thorough, clear explanations. Thank you so, so much.

anuj said...
This comment has been removed by the author.
anuj said...

is there a condition like if
abs(Xn+1 - Xn)=c^n
and abs(Xn+2 -Xn+1)=c*abs(Xn=1 -Xn)
where c<1 then its a cauchy sequence.
if at all its true then i request you to publish a rigorous proof of this!

zdzakula said...

Thank you for the post - enjoyed reading it. There's a little typo in the following sentence:

"Here are some properties of Caucy Sequences which I will use below"

(Cauchy's name misspelled).

-Zeljko

Larry Freeman said...

Hi Zeljko,

Thanks for noticing. I've updated the post.

-Larry