Infinite Products

Today, I present some basic ideas about infinite products that I will use later to demonstrate the convergence of the Euler Product Formula.

Definition 1: Convergence of an infinite product

An infinite product ∏ (n ∈ N) c_n is said to converge to a limit L ≠ 0 if the partial products P_n approaches L as n approaches ∞ where:

P_n = ∏ (0 ≤ m ≤ n) c_m

It also makes sense to define divergence for an infinite product.

Definition 2: Divergence of an infinite product

An infinite product ∏ (n ∈ N) c_n is said to diverge if either the product does not converge (according to definition 1 above) or if it converges to 0.

So, if any of the factors of an infinite product is 0, then, that infinite product is said to diverge.

Lemma 1: if ∏ c_n is convergent, then (lim n → ∞) c_n = 1.

Proof:

(1) Assume that an infinite product ∏ c_n is convergent.

(2) Let P_n be the partial product of this infinite product such that:

P_n = ∏ (0 ≤ m ≤ n) c_m

(3) Then, for each c_n of the series:

c_n = P_n/(P_n-1)

(4) Since the product is convergent, there exists L such that as n goes to ∞, P_n → L and P_n-1 → L.

(5) It therefore follows that lim (n → ∞) c_n = lim (n → ∞) P_n/P_n-1 = L/L = 1.

QED

Corollary 1.1: lim(1 + a_n)

if a_n = c_n - 1, then:
∏(1 + a_n) is convergent → lim (n → ∞) a_n = 0.

Proof:

(1) a_n = c_n - 1

(2) lim (n → ∞) a_n = lim(n → ∞) c_n - 1 = 1 - 1 = 0 [This follows from Lemma 1 above]

QED

Lemma 2: Criteria for Convergence of ∑ a_n

For any N ≥ 0, if ∑ (n=N, ∞) a_n is finite, then ∑ (n=0, ∞) a_n is finite where a_i is a real number.

Proof:

(1) Let {a_n} be a sequence such that each a_n is a real number.

(2) Assume that ∑ (n=N, ∞) a_n is finite

(3) Clearly, if N is any natural number, then ∑ (n=0, n less than N) a_n is finite.

(3) Since, ∑ (n=0, ∞) a_n = ∑ (n=0, n less than N) a_n + ∑ (n = N, ∞), it follows that:

∑ (n=0, ∞) a_n is finite and therefore convergent.

QED

Lemma 3: Criteria for Convergence of ∏(1 + a_n)

If a_n ≠ -1 for n ∈ N, then:
∏ (1 + a_n) converges if and only if ∑ log(1 + a_n) converges

Proof:

(1) Assume ∑ log(1 + a_n) converges to S

(2) Let S_n = ∑ (m ≤ n) log(1 + a_m)

(3) Then:

e^S_n = ∏ (m ≤ n) (1 + a_m) since:

e^{log(x) + log(y)} = e^log(xy) = xy [See here for review of the properties of Log]

(4) Since lim (n → ∞) S_n = S, this implies that:

lim (n → ∞) e^s_n = e^S

(5) Thus, we have shown that:

lim (n → ∞) (1 + a_n) = e^S

(6) Assume that ∏(1 + a_n) converges

(7) Let ε be a real number greater than 0.

(8) Then, by Lemma 1 above (see here for review of mathematical limits), there exists N such that:

abs(P_n/P_n-1 - 1) is less than ε if m,n ≥ N.

This follows since lim (n → ∞) P_n = L which means:

lim (n → ∞) P_n/P_n-1 = L/L = 1

(9) Let P_n = ∏ (m ≤ N) (1 + a_n)

(10) If m,n ≥ N, then:

Log(P_n/P_N) = Log(P_m/P_N * P_n/P_m) = Log(P_m/P_N) + Log(P_n/P_m) [See here for properties of Log]

(11) Let m = n-1

(12) Since c_n = P_n/P_n-1 = P_n/P_m = a_n + 1 (see Lemma 1 above for details), we have:

Log(P_n/P_N) = Log(P_m/P_N) + Log(1 + a_n)

(13) Since m = n-1 and since we can apply this same argument to m-1, m-2, etc. we get:

Log(P_n/P_N) = [Log(P_m-1) + Log(1 + a_m)] + Log(1 + a_n) = ∑ (N is less than i ≤ n) Log(1 + a_i)

(14) Since lim (n → ∞) P_n = L, it follows that:

lim (n → ∞) Log(P_n/P_N) = Log(L/P_N)

(15) This shows that:

lim (n → ∞) ∑ (n greater than N) Log(1 + a_n) = Log(L/P_N)

(16) Using Lemma 2 above gives us:

∑ (n ≥ 0) Log(1 + a_n) is convergent.

QED

Lemma 4: If abs(z) ≤ (1/2), then abs(log(1 + z)) ≤ 2*abs(z)

Proof:

(1) If abs(z) is less than 1, then Log(1 + z) is holomorphic. [Details to be added later, in the mean time see here]

(2) Since Log(1 + z) is holomorphic (see here for definition of holomorphic),

Log(1 + z) = z - z²/2 + z³/3 - ... [See Theorem, here]

(3) Using the Triangle Inequality for Complex Numbers (see Lemma 3, here), we have:

abs(Log(1 + z)) ≤ abs(z) + abs(z²/2) + abs(z³/3) + ...

which is less than

abs(z) + abs(z)² + abs(z)³ + ...

(4) Now, abs(z) + abs(z)² + abs(z)³ + ... = abs(z)/[1 - abs(z)] [See Lemma 1, here]

(5) Since abs(z) ≤ (1/2), it follows that:

1/[1 - abs(z)] ≤ 1/[1 - (1/2)] = 1/(1/2) = 2.

(6) So that we have:

abs(Log(1 + z)) ≤ 2*abs(z)

QED

Lemma 5: if ∑ a_n converges, there exists an natural number N such that for all n ≥ N, a_n is less than (1/2).

Proof:

(1) If ∑ a_i converges, then only a finite number of a_i ≥ (1/2).

(a) Assume that there is an infinite number of a_i such that a_i ≥ (1/2)

(b) If we build a subsequence (see Definition 6, here for definition of subsequence) of just those values of a_i where a_i ≥ (1/2)

(c) Since there are an infinite number of them, it follows that ∑ a_i = ∞

(d) But this is impossible since ∑ (i=1, ∞) a_i converges in step #1, so we reject our assumption at step #1a.

(2) If there are only a finite number of a_i where a_i ≥ (1/2), then we can let N-1 = the last such a_i ≥ (1/2).

(3) Then, it follows that for all i ≥ N, a_i is less than (1/2).

QED

Lemma 6: Criteria for Convergence using ∑ abs(a_n)

if a_n ≠ -1 for n ∈ N, then:

∑ abs(a_n) is convergent → ∏(1 + a_n) is convergent

Proof:

(1) Assume that ∑ abs(a_n) converges such that ∑ abs(a_n) = L

(2) Then there exists N such that n ≥ N → abs(a_n) is less than (1/2) [See Lemma 5 above]

(3) Using Lemma 4 above with a_n, it follows that:

abs(Log(1 + a_n)) ≤ 2*abs(a_n)

(4) So that we have:

∑ abs(Log(1 + a_n)) ≤ ∑ 2*abs(a_n) = 2*∑ abs(a_n) = 2*L.

(5) The conclusion follows from applying Lemma 3 above.

QED

References

• James M. Hyslop, Infinite Series, Dover Publications, 2006.
• Complex Logarithms, Wikipedia
  

Integral Test for Infinite Series

The Integral Test for Infinite Series is a well known convergence test that uses integrals. The Integral Test, for example, can be used, for example, to show that the harmonic series diverges (that is, does not have a limit).

The content in today's blog is taken from Edwards and Penney, Calculus and Analytic Geometry.

Definition 1: Improper Integral

An Improper Integral is an integral on an interval that is open (does not include its endpoints) or on a closed interval that is unbounded (that is, one of its endpoints is either ∞ or -∞). [See here for a review of open and closed intervals]

Improper integrals are used to analyze infinite series. The improper integral is the limit of a sequence of definite integrals where endpoints get closer and closer to the limit.

Theorem 1: The Integral Test

Let ∑ a_n be a positive-term series (none of the elements are negative) and let f(x) be a function that is a positive valued, decreasing continuous function for x ≥ 1.

If f(n) = a_n for all integers n ≥ 1, then the series and the improper integral:

∑ (n=1, ∞) a_n

∫ (1,∞) f(x)dx

either both converge or diverge. That is, one diverges if and only if the other diverges.

Proof:

(1) Let S_n = a₁ + a₂ + ... + a_n

(2) If f(n) = a_n for all integers n ≥ 1, then it is clear that for the region under y=f(x) from x=1 to x = n+1:

∫ (1,n+1) f(x)dx ≤ S_n (see graph below)

(3) If we now consider the sum S_n - a₁ = a₂ + a₃ + ... + a_n, then:

If f(n) = a_n for all integers n ≥ 1, then it is clear that for the region under y=f(x) from x=1 to x = n:

S_n - a₁ ≤ ∫ (n,1) f(x)dx (see graph below)

(4) Assume that ∫(∞,1) f(x)dx diverges.

Then it goes to +∞ since by assumption f(x) is a positive term series.

(5) lim (n → ∞) ∫ (n+1,1) f(x) = +∞

(6) From step #2, it is clear that lim (n → ∞) Sn = +∞ so that ∑ a_n diverges.

(7) Assume that ∫(∞,1) f(x)dx converges with value = I.

(8) From step #3,

S_n ≤ a₁ + ∫(n,1)f(x)dx ≤ a₁ + I

(9) So the monotone increasing sequence {S_n} (∞,1) is bounded. [See Definition 8, here for definition of monotone increasing sequence, see Definition 4, here for definition of bounded]

(10) This gives that the infinite series ∑ a_n = lim (n → ∞) S_n converges also.

QED

Corollary 1.1: Harmonic series diverges

∑ (n=1, ∞) 1/n = 1 + 1/2 + 1/3 + 1/4 + ...

Proof:

(1) f(x)=1/x is positive, continuous, and decreasing for x ≥ 1.

(2) ∫(∞,1) (1/x)dx = lim (b → ∞) ∫ (b,1) (1/x)dx = lim (b → ∞) [ln x] (b,1) [This follows from the derivative of 1/x, see Lemma 1, here]

(3) lim (b → ∞) [ln x] (b,1) = lim (b → 0) (ln b - ln 1) = + ∞

(4) Therefore, using the Integral Test above, the series diverges.

QED

Corollary 1.2: Zeta function converges if s > 1 but diverges if 0 is less than s ≤ 1.

ζ(s) = ∑ (n=1,∞) 1/n^s = 1 + 1/2^s + 1/3^s + ... + 1/n^s + ...

Proof:

(1) The case where s=1 was proven in Corollary 1.1

(2) If s is greater than 0 and s ≠ 1, then f(x) = 1/x^s satisfies the conditions of the integral test (it is a positive-valued, decreasing, continuous function for x ≥ 1).

(3) ∫ (∞,1) (1/x^s)dx = lim (b → ∞) ∫ (b,1) (1/x^s)dx = lim (b → ∞) [-1/[(s-1)x^s-1]] (b,1) [This follows from the power rule for derivatives (see Lemma 2, here) and the fundamental theorem of calculus]

(4) lim (b → ∞) [-1/[(s-1)x^s-1]] (b,1) = lim(b → ∞) (1/[s-1])[1 - 1/(b^s-1)]

(5) If s is greater than 1, then:

lim(b → ∞) (1/[s-1])[1 - 1/(b^s-1)] = (1/[s-1])(1) = (1/[s-1]) which is less than ∞ so it converges.

(6) If 0 is less than s is less than 1, then:

∫ (∞,1)(1/x^s)dx = lim (b → ∞) [1/(1-s)](b^1-p - 1) = ∞

[This follows from the generalized power rule for derivatives (see Theorem, here) and the fundamental theorem of calculus]

(7) The conclusion follows from the Integral Test above.

QED

References

• Mohamed A. Khamsi, "Improper Integrals: An Introduction", SOSMath.com
• Edwards & Penney, Calculus and Analytic Geometry

Power rule for integrals

Here is another elementary use of the fundamental theorem of calculus.

Lemma: Power rule for integrals

if n ≠ -1, then ∫ axⁿdx = (1/[n+1])axⁿ⁺¹+C

Proof:

(1) d/dx[ (1/[n+1])axⁿ⁺¹+C] = (1/[n+1]a)d/dx[xⁿ⁺¹] + d/dx[C] =
(1/[n+1])(n+1)*axⁿ + 0 = axⁿ

First, we apply Lemma 3, here to split up the sum. Since the derivative is defined in terms of limits (see Definition 1, here), we can move the constants (1/[n+1])*a. The constant rule (see Lemma 1, here) gives us that d/dx[C] = 0. Finally, the power rule for derivatives (see Lemma 2, here) gives us our result.

(2) Since (1/[n+1])axⁿ⁺¹ + C is the antiderivative for axⁿ (see Definition 2, here, for definition of antiderivative), the Fundamental Theorem of Calculus (see Theorem 2, here) gives us our conclusion.

QED

log (1 + x) = ∑ (n=1,∞) [(-1)n+1xn]/n

In today's blog, I use the fundamental theorem of calculus and the basic properties of derivatives to show that:
log (1 + x) = ∑ (n=1,∞) [(-1)ⁿ⁺¹xⁿ]/n

First, we need a lemma:

Lemma 1: 1/(x+1) = ∑ (i=1,∞) (-1)⁽ⁱ⁺¹⁾*x^i-1

for x ≠ -1

Proof:

(1) Let s = ∑ (i=1,∞) (-1)⁽ⁱ⁺¹⁾*x^i-1 which gives us:

s = 1 - x + x² -x³ + ....

(2) xs = x - x² + x³ - x⁴ + ...

(3) Then xs + s = 1

(4) Solving for s gives us:

s(x+1) = 1

so that:

s = 1/(x+1)

QED

Theorem: log (1 + x) = ∑ (n=1,∞) [(-1)ⁿ⁺¹xⁿ]/n

Proof:

(1) From Lemma 1 above;

1/(1+x) = ∑ (i=1,∞) (-1)⁽ⁱ⁺¹⁾*x^i-1

(2) d/dx(ln(1+x)) = 1/(1+x) since:

(a) Let g(x) = 1 + x

(b) Let h(x) = ln(x)

(c) Using the Chain Rule for Derivatives (see Lemma 2, here), we have:

d/dx(ln(1+x)) = d/dx(h(g(x)) = h'(g(x))*g'(x)

where:

h'(g(x)) = ln(1+x) = 1/(1+x) [see Lemma 1, here]

g'(x) = d/dx(1 + x) = d/dx(1) + d/dx(x) = 0 + 1 = 1

so:

d/dx(ln(1+x)) = [1/(1+x)]*1 = 1/(1+x)

(3) Since d/dx(ln(1+x)) = 1/(1+x), we know that ∫(1/(1+x)dx) = ln(1+x)+C [See Theorem 2, here]

(4) If we take the antiderivative of both sides (see Definition 2, here for definition of antiderivative), we have:

ln(1+x) = ∫(1 - x + x² - x³ + ...)

(5) Using the linearity property of integrals (see Lemma, here) gives us:

ln(1+x) = ∫1 - ∫xdx + ∫x²dx - ∫x³dx + ...

(6) Using the power rule for integrals (see Lemma, here) gives us:

ln(1+x) = x - x²/2 + x³/3 -x⁴/4 + ....

QED

Linearity Property of the Integral

The linearity property of the integral refers to the very important property of being able to break integrals apart into sums. That is, ∫(b,a) [f(x)dx + g(x)dx] = ∫ (b,a) f(x)dx + ∫(b,a)g(x)dx.

The content in today's blog is taken from Edwards and Penney's Calculus and Analytic Geometry.

Theorem: Linearity Property of Integrals

If α, β are constants and f(x) and g(x) are continuous functions on [a,b], then:

∫ (b,a) [αf(x) + βg(x)]dx = α∫(b,a)f(x)dx + β∫(b,a)g(x)dx

Proof:

(1) By the Constant Multiple Property (see Lemma 2, here):

∫(b,a) cf(x)dx = c∫(b,a) f(x)dx

(2) Let F(x) be the antiderivative of f(x) and G(x) be the antiderivative of g(x).

(3) d/dx[F(x) + G(x)] = f(x) + g(x) [See Lemma 3, here]

(4) Using the Fundamental Theorem of Calculus (see Thereom 2, here), this gives us:

∫ (b,a) [f(x) + g(x)]dx = [F(x) + G(x)] (b,a)

(5) Using the Evaluation of Integrals (see Theorem 3, here), we have:

[F(x) + G(x)](b,a) = [F(b) + G(b)] - [F(a) + G(a)] = [F(b) - F(a)] + [G(b) - G(a)] =

= [F(x)](b,a) + [G(x)](b,a) = ∫(b,a) f(x)dx + ∫(b,a) g(x)dx.

QED

References

• Edwards & Penney, Calculus and Analytic Geometry

Intermediate Value Property of Continuous Functions

Today's blog is another presentation of an elementary proof that I will use in my proof of the fundamental theorem of calculus.

The content in today's blog is taken from Edwards & Penney's Calculus and Analytic Geometry.

Theorem: Intermediate Value Property of Continuous Functions

If a function f is continuous on [a,b] and f(a) is less than K which is less than f(b), then K = f(c) for some number c in (a,b).

Proof:

(1) Let us start by defining three sequences {a_i}, {b_i}, and {I_i}

a₁ = a
b₁ = b

m_i = midpoint of [a_i,b_i]

we can assume that f(m_i) ≠ K since if it did, then c = m_i and we are done with this proof.

if K is less than f(m_i), then:

a_i+1 = a_i
b_i+1 = m_i

Otherwise K is greater than f(m_i) and:

a_i+1 = m_i
b_i+1 = b_i

In this way, we can also define a sequence of nested intervals such that:
I_i = [a_i,b_i] and for all i, K lies between f(a_i) and f(b_i)

(2) Using the Nested Intervals Property of Real Numbers (see Lemma 1, here), we know that there exists a point c in I₁ such that {c} = I₁ ∩ I₂ ∩ I₃ ∩ ...

(3) We can see that both {a_i} and {b_i} have this point c as their limit. [See Definition 1, here for a definition of a limit]

(4) Since the function f(x) is continuous on (a,b), we know (see Definition 1, here for definition of continuous on a point) that:

for any positive real ε, there exists a positive real δ such that:

if abs(x-c) is less than δ, then abs(f(x) - f(c)) is less than ε

(5) By the definition of limits of a function (see Definition 1, here), it follows that the limit of {f(b_n)} and the limit of {f(a_n)} is f(c).

(6) Since for all n, f(b_n) is greater than K, it follows that f(c) ≥ K.

(7) Likewise for all n, f(a_n) is less than K so that f(c) ≤ K.

(8) But the only way that step #6 and step #7 can both be true is if f(c)=K.

QED

References

• Edwards & Penney, Calculus and Analytic Geometry

Properties of integrals

In today's blog, I use Reimann sums (see Definition 2, here) to establish some basic properties of integrals. I will later use these properties to present the fundamental theorem of calculus.

The content in today's blog is taken straight from Edwards and Penney's Calculus and Analytic Geometry.

Lemma 1: Integral of a Constant

∫ (b,a) c dx = c(b-a)

Proof:

In the case of a constant, one interval will do and the area is exactly c(b-a). [See here for a discussion of Riemann sums]

QED

Lemma 2: Constant Multiple Property

∫ (b,a) cf(x)dx = c ∫ (b,a) f(x)dx

Proof:

(1) Let R = the Riemann sum (see Definition 2, here) for this equation so that we have:

R = ∑ (j=1,n) c*f(c_j)(x_j - x_j-1)

(2) Now, since c is constant, we have:

R = c*∑ (j=1,n) f(c_j)(x_j - x_j-1)

(3) Now, using the definition of the integral as the limit of the Riemann sum R (see Definition 5, here), we get:

I = lim (n → ∞) R = lim (n → ∞) c*∑ (j=1,n) f(c_j)(x_j - x_j-1) =

= c*lim(n → ∞) ∑ (j=1,n) f(c_j)(x_j - x_j-1) = c*∫ (b,a) f(x)dx

QED

Lemma 3: Interval Union Property

If a is less than c is less than b, then:

∫ (a,b) f(x)dx = ∫ (c,a) f(x)dx + ∫ (b,c) f(x)dx

Proof:

(1) Let R₁ = Riemann sum for f(x) on the interval [c,a] with Partition P₁ and a set S₁ of arbitrary points in each subinterval [See Definition 2, here for definition of Riemann sum]

(2) Let R₂ = Riemann sum for f(x) on the interval [b,c] with Partition P₂ and a set S₂ of arbitrary points in each subinterval [See Definition 2, here for definition of Riemann sum]

(3) Let S = S₁ ∪ S₂

(4) Let P = P₁ ∪ P₂

(5) Let x_1,i be the set of intervals that make up P₁ [See Definition 1, here for definition of partition]

(6) Let x_2,i be the set of intervals that make up P₂ [See Definition 1, here for definition of partition]

(7) Since a is less than c which is less than b, we have:

a=x_1,0 less than x_1,1 less than ... less than x_1,n=c=x_2,0 less than x_2,1 less than ... less than x_2,n = b

(8) From this, we can see that P is a partition on [a,b] (See Definition 1, here for definition of partition)

(9) Since S₁ is a set of arbitary points in each subinterval on [a,c] and S₂ is a set of arbitrary points in each subinterval on [b,c], it follows that S is set of arbitrary points on [a,c] [See Definition 2, here on Riemann sum]

(10) So, R is a Riemann sum since it is defined on [a,c] using a partition P and a set S of arbitrary points in each subinterval.

(11) Since f(x) is continuous, we know that R, R₁, and R₂ have limits (that is, their integrals exist. (See Theorem, here)

(12) Therefore, it follows that:

lim (n → ∞) R = lim (n → ∞)R₁ + lim(n → ∞) R₂

which using the definition of definite integrals in terms of Riemann sums (see Definition 5, here) gives us:

∫ (a,b) f(x)dx = ∫ (c,a)f(x)dx + ∫ (b,c) f(x)dx.

QED

Lemma 4: Comparison Property

If m ≤ f(x) ≤ M for all x in [a,b], then:

m(b - a) ≤ ∫ (b,a) f(x)dx ≤ M(b-a)

Proof:

(1) Let m be ≤ minimum of f(x) on [a,b] (See Theorem, here for proof of the existence of the minimum)

(2) Let M be ≥ maximum of f(x) on [a,b] (See Lemma 3, here for proof of the existence of the maximum)

(3) For any partition P on [a,b], m(b-a) ≤ L(P) [Since L(P) = min of f(x) on [a,b], see Definition 2, here]

(4) Likewise, M(b-a) ≥ U(P) [Since U(P) = max of f(x) on [a,b], see Definition 2, here]

(5) Since L(P) ≤ I ≤ U(P) [See Lemma 1, here], we have:

m(b-a) ≤ L(P) ≤ I ≤ U(P) ≤ M(b-a)

QED

References

• Edwards & Penney, Calculus and Analytic Geometry

Fundamental Theorem of Calculus

In today's blog, I present the Fundamental Theorem of Calculus. This is the insight that the integral, the area under the curve, is the same as the antiderivative (that is, the inverse of the derivative) of the curve itself. This enables evaluation of the integral without relying on a Riemann sum.

The Fundamental Theorem is often presented as a single proof. In today's blog, I break it down into two theorems.

The content is taken from Edwards and Penney's Calculus and Analytic Geometry.

Definition 1: Average Value of a Function

If a function f is integrable on [a,b], then the average value y of y = f(x) on [a,b] is:

y = 1/(b-a) ∫ (b,a) f(x)dx

This definition becomes more intuitive, when we realize that:

∫ (b,a) f(x) dx = (b-a)y = (b-a)f(x)

This definition is used in the following theorem:

Theorem 1: Average Value Theorem

If a function f is continuous on [a,b], then:

f(x) = 1/(b-a) ∫ f(x)dx for some point x on [a,b]

Proof:

(1) Let m = f(c) be the minimum value of f on [a,b] (See Theorem, here for proof that it exists)

(2) Let M = f(d) be the maximum value of f on [a,b]. (See Lemma 3, here for proof that it exists)

(3) Using the Comparison Property (see Lemma 4, here),

m(b-a) ≤ ∫ (b,a) f(x)dx ≤ M(b-a)

Then, dividing all sides by (b-a) gives us:

m ≤ 1/(b-a) ∫ (b,a) f(x)dx ≤ M

(4) Because f is continuous and because y=[1/(b-a) ∫ (b,a) f(x)dx] lies between two values of f: m and M, we can use the Intermediate Value Property (see Theorem, here) to conclude that y must be a value of f.

(5) Thus, there must exists a point x where y = f(x) and where x lies between a and b.

QED

Definition 2: antiderivative

A function F is an antiderivative of a function f if and only if the derivative F'(x) = f(x).

The fundamental theorem of calculus (see Theorem 2 below) gives another notation for this same point:

F(x) = ∫ f(x)dx

Here is the proof.

Theorem 2: The integral is the antiderivative of a continuous function.

d/dx (∫ (x,a) f(t)dt) = f(x) where f(x) is a continuous function

Proof:

(1) Let F(x) be a continuous function defined on [a,b] by:

F(x) = ∫ (x,a) f(t)dt

(2) By the definition of the derivative (see Definition 1, here):

F'(x) = lim (Δx → 0) [F(x + Δx) - F(x)]/Δx

= lim (Δx → 0) (1/Δx)(∫ (x+Δx,a) f(t)dt - ∫ (x,a) f(t)dt)

(3) Using the interval union property (see Lemma 3, here), we know that:

∫ (x+Δx,a) f(t)dt = ∫ (x,a) f(t)dt + ∫(x+Δx, x) f(t)dt

(4) Thus:

F'(x) = lim (Δx → 0) (1/Δx) ∫ (x+Δx,x) f(t)dt

(5) The average value theorem (see Thereom 1, above) gives us:

1/Δx ∫ (x+Δx,x) f(t)dt = f(t) for some number t in [x, x + Δx].

(6) It is clear that as Δx → 0, t → x.

(7) Thus, because f is continuous, we see that:

F'(x) = lim(Δx → 0) (1/Δx) ∫ (x+Δx,x) f(t)dt = lim (Δx → 0) f(t) = lim (t → x) f(t) = f(x).

(8) Hence the function F defined above is indeed the antiderivative of f.

QED

Theorem 3: Evaluation of Definite Integrals

The definite integral of a continuous function G'(x) is equal to the difference of the antiderivatives:

∫ (b,a) G'(x)dt = G(b) - G(a)

Proof:

(1) Let F'(t)=f(t) be a continous function on [a,b].

NOTE: For purposes of clarity, I use f(t) and F'(t) when refering to the continuous function itself and F(x),G(x) when refering to the antiderivative. The reason for this is to make clear the definite integral:

F(x) = ∫ (x,a) f(t)dt.

(2) F(x) is then its antiderivative with:

F(x) = ∫ (x,a) f(t)dx

(3) Let G be any antiderivative of F'(t) such that:

G(x) = F(x) + C on [a,b] where C is a constant.

Since F'(t) is the continuous function, F(x) is the antiderivative and the set of all antiderivatives is characterized by F(x) + C since d/dx(F(x) + C) = d/dx(F(x)) + d/dx(C) = F'(x) + 0 = F'(x) [See Lemma 1, here for details on why F(C)=0]

(4) Since F(a) = ∫ (a,a) f(t)td = 0, we know that:

G(a) = F(a) + C = 0 + C = C

(5) Combining this with step #1 gives us:

G(x) = F(x) + G(a) for all x in [a,b].

which is the same as:

F(x) = G(x) - G(a)

(6) If x=b, this gives us:

G(b) - G(a) = F(b) = ∫ (b,a) f(x)dx.

QED

References

• Edwards & Penney, Calculus and Analytic Geometry

Summation Formula

It is not very difficult to verify the simplest summation formulas but it raises the question how these formulas were derived.

In today's blog, I will first use induction to prove the summation formulas for ∑ x, ∑ x², and
∑ x³. Then, I will show how it is possible to derive each of these formulas.

I will use the summation formula ∑ x³ in my example of using a Riemann sum to calculate the area under a simple curve.

Lemma 1:

(a) (n-1)² = n² - 2n + 1

(b) (n-1)³ = n³ - 3n² + 3n - 1

(c) (n-1)⁴ = n⁴ -4n³ + 6n² -4n + 1

Proof:

(a) This follows straight from multiplying (n-1)(n-1)

(b) (n-1)³ = (n-1)(n² - 2n + 1) = n³ - 2n² + n -n² + 2n - 1 = n³ - 3n² + 3n - 1

(c) (n-1)⁴ = (n-1)(n³ - 3n² + 3n - 1) = n⁴ -3n³ + 3n² - n -n³ +3n² -3n + 1 = n⁴ -4n³ + 6n² -4n + 1

QED

Lemma 2: ∑(i=1,n) i = (1/2)n² + (1/2)n

Proof:

(1) ∑ (i=1,1) i = 1 = (1/2)(1) + (1/2)(1) = 1

(2) Since this is true for n=1, let's assume it's true up to n-1.

(3) Then ∑ (i=1,n) i = ∑(i=1,n-1)i + n = (1/2)(n-1)² + (1/2)(n-1) + n = (1/2)(n² - 2n + 1) + (1/2)(n) - (1/2) + n = (1/2)n² + (1/2)n

(4) Which proves its true by mathematical induction.

QED

Corollary 2.1: ∑(i=1,n) i = (1/2)n(n+1)

Proof:

(1) From Lemma 2, we have:

∑(i=1,n) i = (1/2)n² + (1/2)n

(2) (1/2)n² + (1/2)n = (1/2)[n² + n] = (1/2)[n(n + 1)]

QED

Lemma 3: ∑ (i=1,n) i² = (1/3)n³ + (1/2)n² + (1/6)n

Proof:

(1) ∑ (i=1,1) i ² = 1 = (1/3)(1) + (1/2)(1) + (1/6)(1) = 1

(2) Since this is true for n=1, let's assume it's true up to n-1.

(3) Then ∑(i=1,n) i² = ∑(i=1,n-1)i² + n² = (1/3)(n-1)³ + (1/2)(n-1)² + (1/6)(n-1) + n²

(4) Applying lemma 1 above gives us:

(1/3)(n-1)³ + (1/2)(n-1)² + (1/6)(n-1) = (1/3)(n³ - 3n² + 3n - 1) + (1/2)(n² - 2n + 1) + (1/6)n - (1/6) + n² = (1/3)n³ -n² +n - (1/3) + (1/2)n² -n + (1/2) + (1/6)n - (1/6) + n² = (1/3)n³ + (1/2)n² + (1/6)n

(5) Which proves its true by mathematical induction.

QED

Lemma 4: ∑ (i=1,n) i³ = (1/4)n⁴ + (1/2)n³ + (1/4)n²

Proof:

(1) ∑ (i=1,1) i³ = 1 = (1/4)(1) + (1/2)(1) + (1/4)(1) = 1

(2) Since this is true for n=1, let's assume it's true up to n-1.

(3) Then ∑ (i=1,n) i³ = ∑(i=1,n-1)i³ + n³ = (1/4)(n-1)⁴ + (1/2)(n-1)³ + (1/4)(n-1)² + n³

(4) Applying lemma 1 above gives us:

(1/4)(n-1)⁴ + (1/2)(n-1)³ + (1/4)(n-1)² + n³ = (1/4)(n⁴ -4n³ + 6n² -4n + 1) + (1/2)( n³ - 3n² + 3n - 1) + (1/4)(n² - 2n + 1) + n³ =

= (1/4)n⁴ + (1/2)n³ + (1/4)n²

(5) Which proves its true by mathematical induction.

QED

I now present a method for deriving each of these formulas. The content in this section is taken from Boris Spokoinyi's web site (see references below)

Example 1: ∑ i = (1/2)n² + (1/2)n

This formula comes from Carl Friedrich Gauss. The story goes that he came up with it when he was a young schoolboy. He was told to add up all the numbers from 1 to 100. Gauss came up with the formula and calculated the sum in less than five minutes.

(1) The sum = 1 + 2 + 3 + 4 + 5 + ...

(2) If we line this up with n going the other way we have:

1 + 2 + 3 + 4 + 5 + ....
n + (n-1) + (n-2) + ....

So that we have (1 + n) + (2 + n - 1) + (3 + n - 2) + ...

(3) This means that addition of the two sums ∑ (i=1,n) (n)*2 = (n)(n+1) and dividing both sides by 2 gives us:

∑ (i=1,n) (n) = (1/2)(n)(n+1) = (1/2)(n² n) = (1/2)n² + (1/2)n.

Example 2: ∑ (i=1,n) i²

(1) ∑ (i=1,n) (i+1)³ = ∑ (i=1,n)(i³ + 3i² + 3i + 1)

(2) ∑ (i=1,n)(i³ + 3i² + 3i + 1) = ∑ (i=1,n) i³ + 3∑(i=1,n) i² + 3∑(i=1,n) i + ∑ (i=1,n) 1

(3) From Lemma 2 (see Example 1 for deriving it), we have:

∑ (i=1,n) i = (n)(n+1)/2

(4) ∑ (i=1,n) 1 = 1 + 1 + ... + 1 = n

(5) Applying step #3 and step #4 to step #2 gives us:

∑ (i=1,n) i³ + 3∑(i=1,n) i² + 3∑(i=1,n) i + ∑ (i=1,n) 1 = ∑ (i=1,n) i³ + 3∑(i=1,n) i² + 3(n)(n+1)/2 + n

(6) ∑(i=1,n) (i+1)³ = ∑ (i=2,n+1) i³ = ∑ (i=1,n) i³ + (n+1)³ - 1³

(7) So that combining step #5 and step #6 gives us:

∑ (i=1,n) i³ + 3∑(i=1,n) i² + 3(n)(n+1)/2 + n = ∑ (i=2,n+1) i³ = ∑ (i=1,n) i³ + (n+1)³ - 1

After subtracting ∑ (i=1,n) i³ from both sides, we get:

3∑(i=1,n) i² + 3(n)(n+1)/2 + n = (n+1)³ - 1

(8) Subtracting 3(n)(n+1)/2 + n from both sides gives us:

3∑(i=1,n) i² = (n+1)³ - 1 - 3(n)(n+1)/2 -n

So that we have:

∑(i=1,n) i² = (1/3)[(n+1)³ - 1 - 3(n)(n+1)/2 -n]

(9) Since (n+1)³ = n³ + 3n² + 3n + 1, we have:

(1/3)[(n+1)³ - 1 - 3(n)(n+1)/2 -n] = (1/3)[n³ + 3n² + 3n + 1 - 1 - (1/2)3n² - (1/2)(3n) - n] =

= n³/3 + n²/2 + n/6

Example 3: ∑ (i=1,n) i³

(1) Since (i+1)⁴ = (i⁴ + 4i³ + 6i² + 4i + 1), we have:

∑ (i=1,n) (i+1)⁴ = ∑ (i=1,n) (i⁴ + 4i³ + 6i² + 4i + 1) =

= ∑ (i=1,n) i⁴ + 4∑(i=1,n)i³ + 6∑(i=1,n)i² + 4∑(i=1,n)i + ∑(i=1,n)1

(2) Likewise, we have:

∑ (i=1,n) (i+1)⁴ = ∑ (i=2,n+1) i⁴ = ∑ (i=1,n) i⁴ + (n + 1)⁴ - 1⁴

(3) So that we get:

∑ (i=1,n) i⁴ + 4∑(i=1,n)i³ + 6∑(i=1,n)i² + 4∑(i=1,n)i + ∑(i=1,n)1 = ∑ (i=1,n) i⁴ + (n + 1)⁴ - 1

And subtracting ∑ (i=1,n) i⁴ from both sides gives us:

4∑(i=1,n)i³ + 6∑(i=1,n)i² + 4∑(i=1,n)i + ∑(i=1,n)1 = (n + 1)⁴ - 1

(4) Which means that:

∑ (i=1,n)i³ = (1/4)[(n + 1)⁴ - 1 - 6∑(i=1,n)i² - 4∑(i=1,n)i - ∑(i=1,n)1]

(5) Now, we know that:

∑ (i=1,n) = n

∑ (i=1,n)i = (1/2)n² + (1/2)n [See Lemma 2 above and Example 1 above]

∑ (i=1,n) i² = (1/3)n³ + (1/2)n² + (1/6)n [See Lemma 3 above and Example 2 above]

(4) So that we have:

∑ (i=1,n)i³ = (1/4)[(n + 1)⁴ - 1 - 6(1/3)n³ - 6(1/2)n² - (6)(1/6)n - 4(1/2)n² - 4(1/2)n - n] = (1/4)[n⁴ + 4n³ + 6n² + 4n + 1 - 1 -2n³ -3n² -n -2n² -2n -n] =

= (1/4)[n⁴ + 2n³ + n²] = (1/4)n⁴ + (1/2)n³ + (1/4)n²

References

• Boris Spoloinyi, Summation Formulas
  

Countability

Definition 1: Set of natural numbers N

The set of natural numbers N = { 1, 2, 3, ... }

Definition 2: Set of integers Z

The set of integers Z = { .., -2, -1, 0, 1, 2, ... }

Definition 3: Set of rational numbers Q

The set of rational numbers Q = { a/b : where a,b ∈ Z }

Definition 4: ~

A~B if and only if there is a one-to-one correspondence between the elements of A and the elements of B.

Definition 5: Infinitely countable

A set S is said to be infinitely countable if there is a one-to-one correspondence between that set and the set N. That is, S~N.

Theorem 1: The union of two infinitely countable sets is infinitely countable

Proof:

(1) Let A be an infinitely countable set so that A~N

(2) Let B be an infinitely countable set so that B~N

(3) Let O be the set of odd positive integers = {1, 3, 5, ... }

(4) Let E be the set of even positive integers = {2, 4, 6, ... }

(5) N~O since we can map x to 2x-1 such that:

1 --> 1
2 --> 3
3 --> 5
...

(6) N~E since we can x to 2x such that:

1 --> 2
2 --> 4
3 -- > 6
...

(7) O + E = N ~ N

This is true since N consists of all the positive odd integers and all the positive even integers.

(8) A ~ O since A~N and O~N

(9) B ~ E since B~N and E~N

(10) A + B ~ A + B ~ O + E ~ N

QED

Corollary 1.1: The set of integers Z is countable

Proof:

(1) Let W = the set of positive integers = {0, 1, 2, 3, ... }

(2) W ~ N

In this case, x maps to x-1 so that we have:

1 --> 0
2 --> 1
3 --> 2
...

(3) Let Z-= the set of negative integers = {-1, -2, -3, ... }

(4) Z- ~ N

In this case, x maps -x so that we have:

1 --> -1
2 --> -2
3 --> -3
...

(5) Z = Z- + W so Z is countable because it is the union of two countable sets. [Using Theorem 1 above]

QED

Theorem 2: The set of ordered pairs WxW is infinitely countable

The set WxW is infinitely count where W={0, 1, 2, ... } and WxW = { (0,0), (0,1), ..., (1,0), (1,1), ..., (2,0), ... }

Proof:

(1) The trick here is to find a way of ordering WxW so that we can visit each ordered pair one-at-a-time and still be on track to visit all of them.

(2) Here's the ordering:















(3) We can see that all possible ordered pairs can be listed in this grid and the zig-zag traversal will eventually visit each one.

QED

Corollary 2.1: If two sets A,B are infinitely countable, then AxB is infinitely countable.

Proof:

(1) Since W ~ N, we can see that A ~W, B~W

(2) This means that AxB ~ WxW

(3) Since WxW ~ N [By Theorem 2 above], we have AxB ~ N.

QED

Theorem 3: All infinite subsets of an infinitely countable set are infinitely countable

Proof:

(1) Let A be an infinite set that is infinitely countable.

(2) Let B be an infinite subset of A.

(3) Now, by definition, we know that we can order the elements in A such that A = {a₁, a₂, ..., a_n }

(4) Now, it follows that B can be listed in the same way with deletions so that you have:

{a_a, a_b, a_c, ... } where a is less than b is less than c etc.

(5) The mapping consists of traversing B in the same order as A so that you have:

1 --> a_a [The first element in A not deleted]
2 --> a_b [The second element in A not deleted]
3 --> a_c [The third element in A not deleted]
...

QED

Theorem 3: The set of rational numbers is infinitely countable

Proof:

(1) The trick here is that we can allow repeats. We come up with an algorithm that will sequentially generate all the rational numbers that exist with repeats.

(2) We can use repeats since by Lemma 2 above, if Q + repeats is infinitely countable then its subset Q (deleting all the repeats) is infinitely countable.

(3) We can map rational numbers to Z x N where Z is the set of integers = { ..., -1, 0, 1, ... } and N is the set of natural numbers = {1,2,3,4, ... } since:

(a) Each rational number q = a/b where a,b ∈ Z. [Definition of rational numbers]

(b) We can assume b is a positive integer since:

b ≠ 0 [Since division by zero is not allowed] and if b ≤ -1, then a/b = (-a)/b where b ≥ 1.

(c) So, every q=a/b maps to (a,b) where a ∈ Z and b ∈ N.

(4) Since Z is infinitely countable (See Corollary 1.1 above) and N is infinitely countable (by definition), we know that ZxN is infinitely countable (By Corollary 2.1 above)

QED

Theorem 4: The number of real numbers between 0 and 1 is not infinitely countable

Proof:

(1) Assume that the real numbers between 0 and 1 is infinitely countable so that there is a mapping between these numbers and N.

(2) Then there should be a complete list. All real numbers would have to be included in this mapping.

(3) But it is possible to construct a number that is not one the list.

(4) All numbers in this list are of the form. 0.xxxxxxxxx....

(5) Let x₁ = the first number in the list and x_1,1 = the first digit of the first number in the list so that 0 ≤ x_1,1 ≤ 9.

(6) Let n₁ = any other digit. For example, if x_1,1 = 9 then we could have n₁ = 8.

(7) We can see that all numbers that we create from n will not equal x₁

(8) Let x_2,2 = the second digit of the second number on the list.

(9) We can now set n₂ = any other digit so that n is now distinct from x₁ and x₂.

(10) We can continue doing this for as long as i and in each case n is different from all the real numbers that came up to i.

(11) In this way, it is possible to set n = a real number which is not on the list.

(12) But this is impossible since we assumed that there was a complete mapping. Therefore, we have a contradiction and we reject our assumption at step #1.

QED

Corollary 4.1: There are an uncountable number of real numbers.

Proof:

This follows directly from the theorem above since (0,1) is a subset of all real numbers so that if (0,1) is uncountable, it follows that the R, the superset of (0,1) is also uncountable.

QED

Corollary 4.2: The number of irrational numbers is uncountable

Proof:

(1) The set of real numbers = the set of rational numbers + the set of irrational numbers.

(2) The set of rational numbers is infinitely countable. [See Theorem 3 above]

(3) Assume that the set of irrational numbers is infinitely countable.

(4) Then the set of real numbers is infinitely countable since it is the union of the rational and the irrational numbers [See Theorem 1 above]

(5) But this contradicts Theorem 4 that the real numbers are not infinitely countable.

(6) Therefore, we have a contradiction and we reject our assumption in step #3.

QED

References

• Countable Set, Wikipedia
• Countability of the Rational Numbers, Cut-The-Knot