Back to Real Analysis

Example Proofs: Using Theorems

n! = n factorial
n! = 𝛱_{k = 1 to n} k for n ≥ 1
So 1! = 1, 2! = 1*2, 3! = 1*2*3, ...
And 0! is defined to be 1.

Show that s_n = ∑_{_{i=0 to n}}1/i! converges.

Thought Process:

Note: Using the definition of convergence

a_n converges to limit, L ⇔ ∀ 𝜀 > 0, ∃ N ∈ ℕ s.t. n ≥ N ⇒ |a_n - L| < 𝜀

to prove the sequence converges requires knowing the limit.
Let's assume we don't recognize the series as e = ∑_{i=0 to ∞}1/i!.

So we would look over the theorems on convergence.
Theorems have one or more conditions and some conclusion.
When using a theorem, you must prove that every condition is met.
This can effectively lead to one proof per condition.
Here are two theorems that can be used to conclude that a sequence converges.

Cauchy Criterion:
A sequence a_n is said to be a Cauchy sequence if
∀ 𝜀 > 0, ∃ N ∈ ℕ s.t. n≥ N and m ≥ N ⇒ |a_n - a_m| < 𝜀

Theorem 1: A real valued sequence converges iff it is Cauchy.

Bounded Monotonic Sequences:
A sequence a_n is said to be monotonically increasing if a_n ≤ a_n+1 for n = 1, 2, 3, ...
A sequence a_n is said to be monotonically decreasing if a_n ≥ a_n+1 for n = 1, 2, 3, ...

Theorem 2: A monotonic sequence converges iff it is bounded.

So how do we decide which theorem to use?
In a way it doesn't matter. Neither theorem requires knowing the limit. Either one should work.
Theorem 1 has a single condition (the Cauchy property), but that condition is complicated.
Theorem 2 has two conditions (monotonic and bounded), but each condition is simple.

Let's try both.

Using Bounded Monotonicity (Theorem 2)

∀ integer n ≥ 1,

0	<	1/(n+1)!
s_n + 0	<	s_n + 1/(n+1)!
s_n	<	(∑_{_{i=0 to n}} 1/i!) + 1/(n+1)!
	<	∑_{_{i=0 to n+1}} 1/i!
	<	s_n+1

So s_n is monotonically increasing. (intermediate result 1)

Is s_n bounded?
The difficult part to work with is the factorials.
Trying to simplify the factorial, we note that if we want an upper bound on 1/i!, we can look for a lower bound on i!.

2⁰

1*2

2¹

1*2*3

2²

1*2*3*4

2³

≥

2^i-1

for i ≥ 1

1/i!

≤

1/2^i-1

for i ≥ 1

Note: The presentation above illustrates the idea.
To be rigorous, you could use proof by induction to shiw that 1/i! ≤ 1/2^i-1.

Then

\|s_n\|	=	s_n
	=	∑_{_{i=0 to n}} 1/i!
	=	1/0! + ∑_{_{i=1 to n}} 1/i!
	=	1/1 + ∑_{_{i=1 to n}} 1/i!
	=	1 + ∑_{_{i=1 to n}} 1/i!
	≤	1 + ∑_{_{i=1 to n}} 1/2^i-1
	≤	1 + ∑_{_{i=0 to n-1}} (1/2)ⁱ
\|s_n\|	≤	1 + ∑_{_{i=0 to n-1}} (1/2)ⁱ	(intermediate result 3)

Then we either remember or derive a closed form for b_n = ∑_{_{i=0 to m}} rⁱ,

(1-r) * b_n	=			(1-r) * ∑_{_{i=0 to m}} rⁱ
	=			∑_{_{i=0 to m}} rⁱ - r * ∑_{_{i=0 to m}} rⁱ
	=		r⁰	+ r¹ + r² + ... + r^n-1 + r^m
				- r¹ - r² - ... - r^m-1 - r^m	- r^m+1
	=	1			- r^m+1
(1-r) * b_m	=	1			- r^m+1
b_m	=			(1 - r^m+1) / (1-r)
∑_{_{i=0 to m}} rⁱ	=			(1 - r^m+1) / (1-r)		(intermediate result 4)

Then

\|s_n\|	≤	1 + ∑_{_{i=0 to n-1}} (1/2)ⁱ	(intermediate result 3)
	=	1 + (1 - (1/2)ⁿ) / (1-1/2)	using (intermediate result 4) with r = 1/2 and m = n-1
	=	1 + (1 - (1/2)ⁿ) / (1/2)
	=	1 + 2 - (1/2)^{n - 1}
	<	1 + 2 - (1/2)^{n - 1} + (1/2)^{n - 1}	since (1/2)^{n - 1} > 0
	=	1 + 2 + 0
	=	3
\|s_n\|	<	3

So s_n is bounded. (intermediate result 2)

s_n is monotonic and bounded by (intermediate result 1) and (intermediate result 2)
so s_n converges by Theorem 2.

Notes:

Each property requires its own proof.
Because the properties were not too complicated, the work does not need to be re-ordered for the proof.
The actual use of the theorem is only a single sentence (2 lines).

Using The Cauchy Criterion (Theorem 1)

Assume n ≥ 0 and m ≥ 0. Without loss of generality, assume n ≤ m

\|s_n - s_m\|	=	\|∑_{_{i=0 to n}}1/i! - ∑_{_{i=0 to m}} 1/i!\|	Definition of s_n
	=	\|∑_{_{i=n+1 to m}} 1/i!\|
	=	∑_{_{i=n+1 to m}} 1/i!
	<	∑_{_{i=n+1 to m}} 1/2^i-1	Same argument as in previous proof.
	=	2 * ∑_{_{i=n+1 to m}} 1/2ⁱ
	<	2 * (1/2)^{n + 1}∑_{_{i=0 to m-n-1}} 1/2ⁱ
	=	(1/2)ⁿ * (1 - (1/2)^{m - n})/(1 - 1/2)	Using (intermediate result 4)
	=	(1/2)ⁿ * (1 - (1/2)^{m - n})/(1/2)
	=	(1/2)^{n - 1} * (1 - (1/2)^{m - n})
	<	(1/2)^{n - 1} * (1)
	=	(1/2)^{n - 1}
	=	(1/2)^{n - 1}

The Cauchy property requires that |a_n - a_m| < 𝜀.
So we want to find values of n that satisfy (1/2)^{n - 1} < 𝜀.

(1/2)^{n - 1} < 𝜀	⇔	2*(1/2)ⁿ < 𝜀
	⇔	(1/2)ⁿ < 𝜀/2
	⇔	2ⁿ > 2/𝜀
	⇔	n > log₂(2/𝜀)

Writing out the Proof:

Let s_n = ∑_{_{i=0 to n}}1/i!
∀ 𝜀 > 0, let N = ceiling(log₂(2/𝜀))
Then let n and m be integers s.t. n≥N and m≥N. (without loss of generality, assume n ≤ m.)

\|s_n - s_m\|	=	\|∑_{_{i=0 to n}} 1/i! - ∑_{_{i=0 to m}} 1/i!\|	Definition of s_n
	=	\|∑_{_{i=n+1 to m}} 1/i!\|
	=	∑_{_{i=n+1 to m}} 1/i!
	<	∑_{_{i=n+1 to m}} 1/2^i-1	Same argument as in previous proof.
	=	2 * ∑_{_{i=n+1 to m}} 1/2ⁱ
	<	2 * (1/2)^{n + 1}∑_{_{i=0 to m-n-1}} 1/2ⁱ
	=	(1/2)ⁿ * (1 - (1/2)^{m - n})/(1 - 1/2)	Using (intermediate result 4)
	=	(1/2)ⁿ * (1 - (1/2)^{m - n})/(1/2)
	=	(1/2)^{n - 1} * (1 - (1/2)^{m - n})
	<	(1/2)^{n - 1} * (1)
	=	(1/2)^{n - 1}
	=	2 * (1/2)ⁿ
	≤	2 * (1/2)^N	since n ≥ N
	≤	2*(1/2)^{log₂(2/𝜀)}	By choice of N
	=	2*1/2^{log₂(2/𝜀)}
	=	2*1/(2/𝜀)
	=	𝜀
\|s_n - s_m\|	<	𝜀

∀ 𝜀 > 0, ∃ N = ceiling(log₂(2/𝜀)) ∈ ℕ
s.t. for n,m ∈ ℕ, n≥N and m≥N ⇒ |s_n - s_m| < 𝜀

s_n = ∑_{_{i=0 to n}}1/i! is a Cauchy sequence.

s_n converges by Theorem 1.

Key Takeaways:

Again, the order in which the proof is presented is not the order in which the proof is constructed.
Construction: N is found at the end.
Presentation: N is given at the beginning.
If one reads only the proof, the key part (N = ceiling(log₂(2/𝜀))) seems to appear out of thin air.
The way to study the proof is to try the proof on your own and figure out the thought process that motivates the key parts.

This page shows an example of how you can prove a single result in multiple ways.

Patterns:
When applying theorems, you must make sure that every condition is met.
The proof will be a sequence of sub-proofs, one for each property.
After those, applying the theorem may be just one line.

Notation:
When your proofs get long, you might want to label intermediate results for easier reference later in the proof.
Using different colors or boxes around key points makes your proof easier to follow.

Organizing the theorems:
This example considered only two theorems.
But a typical class will have many theorems.
One way to organize the theorems in you head is to group them by inputs and outputs.
Inputs are the conditions that must be met (monotonic, bounded, Cauchy).
Outputs are the conclusions (the squence converges, the sequence converges to limit L, the function is differentiable).

Back to Real Analysis