In today's blog, I will use the zeta function to answer the question: what are the odds that two integers selected at random are relatively prime.
Lemma 1: The odds that p divides any positive integer selected at random is 1/p
Proof:
(1) Let us assume that we have n integers, that is, the integers 1..n = 1, 2, 3, ..., n. Let x be an integer randomly selected from this list.
(2) If n ≡ 0 (mod p), then it is clear that the odds are 1/p since:
(a) Since p divides n, there exists a value n' such that n = pn'.
(b) So we can divide up n integers in the following way into n' groups of p:
1, ... , p
p+1, ..., 2p
...
n'p-1, ... n'p
(c) We can see that regardless of group n falls in, 1 out of p of those integers in each group are divisible by p.
(3) if n ≡ a (mod p) where a ≠ 0, then we know that p divides n-a so that we have (n-a)=pn'
(4) In this case, we divide up the n integers into n' groups of p just as before but then we are also left with a group of a integers.
1, ..., p
p+1, .. , 2p
...
n'p-1, ..., n'p
n'p+1, ... n'p+a
(5) We can see that there are a total of n' ways to be divisible by p out of a total of n integers. This gives us odds = n'/(n'p+a)
(6) As we increase n toward infinity, we can use L'Hopital's Rule to give us:
lim (n' → ∞) [n'/(n'p + a)]
let f(x) = n'
let g(x) = n'p + a
f'(x) = 1
g'(x) = p
So lim(n' → ∞) [n'/(n'p+a)] = f'(x)/g'(x) = 1/p
QED
Corollary 1.1: The odds that p divides any 2 positive integers selected at random is 1/p2
Proof:
This follows directly from Lemma 1 above. If the odds of p dividing each positive integer is 1/p, the odds of it dividing both are (1/p)(1/p) = 1/p2
QED
Lemma 2: The odds that any 2 positive integers selected at random are relatively prime is 6/π2
Proof:
(1) Let x,y be two positive integers selected at random.
(2) The odds that a prime p divides both is 1/p2 [From the Corollary 1.1 above]
(3) The odds that a prime p fails to divide both is (1 - 1/p2)
(4) Since each prime is distinct, the odds that no prime p divides both = ∏ (p = all primes)(1 - 1/p2)
(5) Now, let's consider the reciprocal of each factor (1 - 1/p2):
1/(1 - 1/p2) = 1/([p2 - 1]/p2) = p2/(p2 - 1)
(6) Now, consider what happens if we multiply to (p2 - 1) to the following sequence S:
Let S = 1 + 1/p2 + 1/p4 + 1/p6 + 1/p8 + ...
(p2 - 1)S = p2 + 1 + 1/p4 + ... - 1 - 1/p2 -1/p4 = p2
So that:
S = p2/(p2 - 1) = 1 + 1/p2 + 1/p4 + ...
(7) Putting this together gives us:
∏ (p = all primes)1/(1 - 1/p2)=∏ (p = all primes)(p2/(p2 - 1) = ∏ (p = all primes) ∑ (n=1,∞) 1/p2(n-1) = (1 + 1/22 + 1/24 + ... )(1 + 1/32 + 1/34 + ...)(1 + 1/52 + 1/54 + ...)*... =
= 1*1*1*1*...*1 + 1/22*1*1*1*...*1 + 1/32*1*1*1*...*1 + 1/52*1*1*1*..*1 + .... + 1/22*1/32*1*..*1 + ...
We note that it equals all combinations of 1/p2.
(8) Applying the Fundamental Theorem of Arithmetic (see here), this gives us:
1*1*1*1*...*1 + 1/22*1*1*1*...*1 + 1/32*1*1*1*...*1 + 1/52*1*1*1*..*1 + .... + 1/22*1/32*1*..*1 + ...
=∑ (n=1,∞) 1/n2
(9) So putting it all together gives us:
∏ (p = all primes)1/(1 - 1/p2) = ∑ (n=1, ∞) 1/n2
(10) But, we know that:
∑ (n=1, ∞) 1/n2 = π2/6 (see here)
(11) Now, taking the reciprocal of this gives us:
∏ (p = all primes)(1 - 1/p2) = 6/π2.
QED
References
The purpose of this blog is to present the story behind Fermat's Last Theorem and Wiles' proof in a way accessible to the mathematical amateur.
Saturday, September 02, 2006
Thursday, August 31, 2006
Sum of the reciprocal of the primes
In today's blog, I will show that the sum of the reciprocal of the primes is divergent, that is, it does not have a limit.
This was first proved by Leonhard Euler. The details in today's blog are based on Euler's original proof.
Lemma 1: ∑ (p=all primes) ∑ (n=2,∞) (p-n)/n is convergent, that is, it has a finite limit.
Proof:
(1) ∑ (p = all primes) ∑ (n=2,∞) (p-n)/n is less than ∑ (p = all primes) ∑ (n=2,∞) (p-n)
This is clear since n is an integer that starts at 2 and goes on until infinity. In each case, we have (p-n) is greater than (p-n)/n
(2) Using the infinite geometric series equation (see Lemma 1, here), we know that:
1 + 1/p + 1/p2 + ... = 1/(1 - 1/p)
(3) Now (1/p2)*[1 + 1/p + 1/p2 + 1/p3 + ... ] = [1/p2 + 1/p3 + ..] so that:
∑ (n=2, ∞) (p-n) = (1/p2)[1/(1 - 1/p)] = 1/[p2(1 - p-1)]
(4) We can then use step #3 to give us:
∑ (p = all primes) ∑ (n=2, ∞) (p-n) = ∑ (p = all primes) 1/[p2(1 - p-1)] =
= ∑ (p = all primes) 1/[(p)(p)(1 - p-1)] =
= ∑ (p = all primes) 1/[(p)(p - 1)]
(5) ∑ (p = all primes) 1/[(p)(p-1)] is less than ∑ (n=2, ∞) 1/[(n)(n-1)] since n includes nonprimes in the sum.
(6) ∑ (n=2, ∞) 1/[(n)(n-1)] = ∑ (n=2,∞) 1/(n2 - n) is less than ∑ (n=2, ∞) 1/(n2 - 2n + 1)
This is true since n2 - 2n + 1 is always less than n2 - n when n ≥ 2.
(7) Since n2 - 2n + 1 = (n-1)2, we have:
∑ (n=2,∞) 1/(n-1)2 = 1 + 1/4 + 1/9 + ... = π2/6 (See Theorem, here)
(8) So, we have now proved that:
∑ (p = all primes) ∑ (n=2,∞) (p-n)/n is less than π2/6 which is finite.
QED
Theorem: Sum of the Reciprocal of Primes is Divergent
∑ 1/p = 1/2 + 1/3 + 1/5 + 1/7 + ... is divergent, that is, does not have a limit.
Proof:
(1) We know that the ζ(1) = harmonic series, that is, ∑ 1/n diverges, that is, the limit of ∑ 1/n approaches infinity. [See Lemma 3, here]
NOTE: ζ(s) is the zeta function which is equal to ∑ 1/ns. So ζ(1) = ∑ 1/n1 = ∑ 1/n.
(2) From step #1, the limit of log(ζ(1)) approaches infinity. This follows directly from step #1 and the fact that as x gets bigger, log x likewise gets bigger. As x heads to infinity, log x also heads to infinity (see here for background on logarithms)
(3) Using Euler's Product Formula (see Theorem 4, here), we know that:
log(ζ(1)) = log(∑ 1/n) = log(∏ (1 - p-1)-1)
NOTE: ∏ (1 - p-1)-1) is a product of all primes p.
(4) By the property of logarithms (see here), we have:
log(∏ (1 - p-1)-1) = ∑ log([1 - p-1]-1) = ∑ -log(1 - p-1)
(5) Now using some basic properties of the integral (see Theorem, here), we have:
log (1 + x) = ∑ (n=1,∞) [(-1)n+1xn]/n
Let x = -p-1
Then we have:
log (1 + [-p-1]) = ∑ [(-1)n+1(-p-1)n]/n = ∑ [(-1)n+1(-1)n(p-1)n]/n =
= ∑ [(-1)2n+1(p-n)]/n
Since 2n+1 is always odd, this gives us:
log(1 + [-p-1]) = ∑ -(p-n)/n
Since p-n/n is always positive, we have ∑ -(p-n)/n = (-1)∑ (p-n)/n
Further,
-log(1 + [-p-1]) = (-1)log(1 + [-p-1]) = (-1)(-1)∑ (p-n)/n = ∑ (p-n)/n
(6) Combining step #5 with step #4 gives us:
∑ -log(1 - p-1) = ∑ (p=all primes) ∑ (n=1,∞) (p-n)/n
(7) ∑ (p=all primes) ∑ (n=1,∞) (p-n)/n=∑(p=all primes) 1/p + ∑ ∑ (n=2,∞) (p-n)/n
(8) Using Lemma 1 above, we know that ∑ ∑ (n=2,∞) (p-n)/n is convergent, that is, it has a finite limit.
(9) But from step #2, we know that ∑ 1/p + ∑ ∑ (n=2, ∞) (p-n)/n has a limit of infinity.
(10) Therefore, it follows, that ∑ 1/p must be divergent, that is, it must have a limit of infinity.
QED
References
This was first proved by Leonhard Euler. The details in today's blog are based on Euler's original proof.
Lemma 1: ∑ (p=all primes) ∑ (n=2,∞) (p-n)/n is convergent, that is, it has a finite limit.
Proof:
(1) ∑ (p = all primes) ∑ (n=2,∞) (p-n)/n is less than ∑ (p = all primes) ∑ (n=2,∞) (p-n)
This is clear since n is an integer that starts at 2 and goes on until infinity. In each case, we have (p-n) is greater than (p-n)/n
(2) Using the infinite geometric series equation (see Lemma 1, here), we know that:
1 + 1/p + 1/p2 + ... = 1/(1 - 1/p)
(3) Now (1/p2)*[1 + 1/p + 1/p2 + 1/p3 + ... ] = [1/p2 + 1/p3 + ..] so that:
∑ (n=2, ∞) (p-n) = (1/p2)[1/(1 - 1/p)] = 1/[p2(1 - p-1)]
(4) We can then use step #3 to give us:
∑ (p = all primes) ∑ (n=2, ∞) (p-n) = ∑ (p = all primes) 1/[p2(1 - p-1)] =
= ∑ (p = all primes) 1/[(p)(p)(1 - p-1)] =
= ∑ (p = all primes) 1/[(p)(p - 1)]
(5) ∑ (p = all primes) 1/[(p)(p-1)] is less than ∑ (n=2, ∞) 1/[(n)(n-1)] since n includes nonprimes in the sum.
(6) ∑ (n=2, ∞) 1/[(n)(n-1)] = ∑ (n=2,∞) 1/(n2 - n) is less than ∑ (n=2, ∞) 1/(n2 - 2n + 1)
This is true since n2 - 2n + 1 is always less than n2 - n when n ≥ 2.
(7) Since n2 - 2n + 1 = (n-1)2, we have:
∑ (n=2,∞) 1/(n-1)2 = 1 + 1/4 + 1/9 + ... = π2/6 (See Theorem, here)
(8) So, we have now proved that:
∑ (p = all primes) ∑ (n=2,∞) (p-n)/n is less than π2/6 which is finite.
QED
Theorem: Sum of the Reciprocal of Primes is Divergent
∑ 1/p = 1/2 + 1/3 + 1/5 + 1/7 + ... is divergent, that is, does not have a limit.
Proof:
(1) We know that the ζ(1) = harmonic series, that is, ∑ 1/n diverges, that is, the limit of ∑ 1/n approaches infinity. [See Lemma 3, here]
NOTE: ζ(s) is the zeta function which is equal to ∑ 1/ns. So ζ(1) = ∑ 1/n1 = ∑ 1/n.
(2) From step #1, the limit of log(ζ(1)) approaches infinity. This follows directly from step #1 and the fact that as x gets bigger, log x likewise gets bigger. As x heads to infinity, log x also heads to infinity (see here for background on logarithms)
(3) Using Euler's Product Formula (see Theorem 4, here), we know that:
log(ζ(1)) = log(∑ 1/n) = log(∏ (1 - p-1)-1)
NOTE: ∏ (1 - p-1)-1) is a product of all primes p.
(4) By the property of logarithms (see here), we have:
log(∏ (1 - p-1)-1) = ∑ log([1 - p-1]-1) = ∑ -log(1 - p-1)
(5) Now using some basic properties of the integral (see Theorem, here), we have:
log (1 + x) = ∑ (n=1,∞) [(-1)n+1xn]/n
Let x = -p-1
Then we have:
log (1 + [-p-1]) = ∑ [(-1)n+1(-p-1)n]/n = ∑ [(-1)n+1(-1)n(p-1)n]/n =
= ∑ [(-1)2n+1(p-n)]/n
Since 2n+1 is always odd, this gives us:
log(1 + [-p-1]) = ∑ -(p-n)/n
Since p-n/n is always positive, we have ∑ -(p-n)/n = (-1)∑ (p-n)/n
Further,
-log(1 + [-p-1]) = (-1)log(1 + [-p-1]) = (-1)(-1)∑ (p-n)/n = ∑ (p-n)/n
(6) Combining step #5 with step #4 gives us:
∑ -log(1 - p-1) = ∑ (p=all primes) ∑ (n=1,∞) (p-n)/n
(7) ∑ (p=all primes) ∑ (n=1,∞) (p-n)/n=∑(p=all primes) 1/p + ∑ ∑ (n=2,∞) (p-n)/n
(8) Using Lemma 1 above, we know that ∑ ∑ (n=2,∞) (p-n)/n is convergent, that is, it has a finite limit.
(9) But from step #2, we know that ∑ 1/p + ∑ ∑ (n=2, ∞) (p-n)/n has a limit of infinity.
(10) Therefore, it follows, that ∑ 1/p must be divergent, that is, it must have a limit of infinity.
QED
References
- Jay R. Goldman, The Queen of Mathematics, A K Peters, 1998
- Proof that the Sum of the Reciprocals of Primes Diverge, Wikipedia
- Natural Logarithm, Wikipedia
Monday, August 28, 2006
∑ 1/n2 = π2/6
In today's blog, I show the proof that ∑ 1/n2 = π2/6. For background on Basel's problem and Leonhard Euler's technique for arriving at the solution, see here. In today's blog, I show a proof that Euler's solution is correct.
Most of the content in today's blog is taken from the Wikipedia article on the Basel Problem. See references below for more information.
Lemma 1: cot2(x) is one-to-one on the interval (0,π/2)
Proof:
(1) Suppose there exists x,y such that cot2(x) = cot2(y) in the interval (0,π/2)
(2) By definition, cot(x) = (cos x)/(sin x) so that we have:
(cos2 x)/(sin2 x) = (cos2 y)/(sin2 y)
which means that:
(cos2 x)/(cos2 y) = (sin2 x)/(sin2 y)
(3) We also know (see Corollary 2, here), cos2(x) + sin2(x) = 1 which is the same as:
1 - sin2(x) = cos2(x)
(4) Now, we can make the same argument for y and then we can divide by y to get:
[1 - sin2(x)]/[1 - sin2(y)] = [cos2(x)]/[cos2(y)]
(5) Now, we can substitute in step #2 to give us:
[1 - sin2(x)]/[1 - sin2(y)] = (sin2 x)/(sin2 y)
(6) This amounts to:
(sin2 y)(1 - sin2 x) = (sin2 x)(1 - sin2 y)
(7) Adding (sin2 x)(sin2 y) to both sides gives us:
(sin2 y)(1 - sin2 x) + (sin2 x)(sin2 y) =
= (sin2 y)(1 - sin2 x + sin2 x) = sin2 y
(sin2x)(1 - sin2 y) + (sin2 x)(sin2 y) =
= (sin2x)(1 - sin2y + sin2 y) = sin2 x
So that we have:
sin2 y = sin2 x
(8) Squaring both sides gives us:
±(sin y) = ±(sin x)
(9) Since we know that the sin function is nonnegative on the interval (0, π/2), we know that the square has to be nonnegative. This gives us:
sin y = sin x
(10) Finally, since sin x is one-to-one on the interval (0,π/2) (see here for properties of sin), we can see that x = y.
The basic idea here is that the sin function between 0 and π/2 does not repeat any of its values. This proves that if sin x = sin y, then x = y.
QED
Lemma 2: Sum of coefficients for a polynomial
if :
f(t) = amtm + am-1tm-1 + ... + a1t + a0 where am ≠ 0
then:
the sum of the roots of f(t) [counting multiplicities] is -am-1/am
Proof:
(1) Using the Fundamental Theorem of Algebra (see here), we know that we can divide up f(t) into a sequence of m roots such that:
f(t) = am(t - r1)(t - r2)*...*(t - rm)
(2) Now when we multiply all these values together it is clear that the sum of coefficients for tm-1 = the sum of all the roots multiplied by am.
We can see that if we carry out the multiplication of (t - r1)(t - r2)*...*(t - rm), we get:
tm + tm-1(-r1 + -r2 + ... + -rm) + ... + (-r1)(-r2)*...*(-rm)
(3) We can see that the coefficient for tm-1, am-1 = -am(r1 + r2 + ... + rm)
(4) But then r1 + r2 + ... + rm = -am-1/am
QED
Lemma 3: csc2(x) = 1 + cot2(x)
Proof:
(1) sin2x + cos2x = 1 (see Corollary 2, here)
(2) Divide both sides by sin2
Then we have:
1/(sin2x) = 1 + (cos2x)/(sin2x)
(3) Since by definition, cot2x = (cos2 x)/(sin2 x) and csc2x = 1/(sin2x), step #2 gives us:
csc2 x = 1 + cot2 x
QED
Lemma 4: cot2x is less than 1/x2 which is less than csc2 x on the interval (0,π/2)
Proof:
(1) If x is in (0, π/2), then (see Theorem, here):
sin x is less than x which is less than tan x.
(2) Taking the inverse of each (since x ≠ 0 → sin x ≠ 0 and tan x ≠ 0) gives us:
csc x is greater than 1/x which is greater than cot x.
(3) Now, squaring each value gives us:
cot2 x is less than 1/x2 which is less than csc2 x.
QED
Lemma 5: as m approaches infinity, both (2m)(2m+2)/(2m+1)2 and (2m)(2m-1)/(2m+1)2 approaches 1
Proof:
(1) Putting all values into polynomial form, we have:
(2m)(2m+2) = 4m2 + 4m
(2m)(2m - 1) = 4m2 - 2m
(2m+1)2 = 4m2 + 4m + 1
(2) Now, we can calculate the limits using L'Hopital's rule (see here)
lim (m → ∞) [(4m2 - 2m)/(4m2 + 4m + 1)] = lim (m → ∞) [(8m - 2)/(8m + 4)] = lim (m → ∞) [8/8] = 1.
lim (m → ∞) [(4m2 + 4m)/(4m2 + 4m + 1)] = lim (m → ∞) [(8m + 4)/(8m + 4)] = 1.
QED
Theorem: ∑ 1/n2 = π2/6
Proof:
(1) Using De Moivre's Formula (see Corollary, here for proof) we know that:
(cos x + i sin x)n = cos(nx) + i sin(nx)
(2) Dividing both sides by (sin x)n gives us:
[cos(nx) + i sin(nx)]/(sin x)n = (cos x + i sin x)n/(sin x)n = [(cos x + i sin x)/sin x]n
(3) Since cot x = (cos x)/(sin x) [by definition, cot(x) = 1/tan(x)], we have:
[(cos x + i sin x)/sin x] = cot x + i
(4) Putting this all together gives us:
[ cos(nx) + i sin(nx) ]/(sin x)n = (cot x + i)n
(5) Using the Binomial Theorem [See here], we know that:
(cot x + i)n = cotn x + (n,1)(cotn-1x)i + ... + (n,n-1)(cot x)in-1 + in
(6) Since i2 = -1, we can now divide up all terms in step #5 so that we have:
cotn x + (n,1)(cotn-1x)i + ... + (n,n-1)(cot x)in-1 + in = [(cotnx) - (n,2)(cotn-2 x) ± ... ] + i[(n,1)(cotn-1x) - (n,3)(cotn-3x) ± ... ]
(7) Since for any identity a + bi = c + di, we know that a=c and b=d, we can build the following equation from step #2 and step #6:
[isin(nx)]/(sin x)n = i[(n,1)(cotn-1x) - (n,3)(cotn-3x) ± ... ]
(8) Dividing both sides by i gives us:
sin(nx)/(sin x)n = [(n,1)(cotn-1x) - (n,3)(cotn-3x) ± ... ]
(9) Now, since step #8 is an identity, it is true for all values n,x.
Let n = 2m + 1 where m is a positive integer.
Let x = rπ/(2m + 1) where r can = 1, 2, ..., m
From this, we can see that:
nx = (2m + 1)*(rπ)/(2m+1) = rπ
(10) From a property of sin (see Lemma 1, here), we can see that:
sin(nx) =0
(11) Applying these values to step #8 gives us:
sin(nx)/(sin x)n = 0/(sin x)n = 0 =
= [(n,1)(cotn-1x) - (n,3)(cotn-3x) ± ... ] =
= [(2m+1,1)(cot2mx) - (2m+1,3)(cot2m-2x) ± ... + (-1)m ]
(12) Using Lemma 1 above, we can conclude that the values for x in step #11 are distinct. By the above equation we know that each of these m distinct solutions for x are roots to the following equation:
(2m + 1, 1)tm - (2m + 1,3)tm-1 ± ... + (-1)m = 0
(13) Using Lemma 2 to calculate the sum of roots using the coefficients, we have:
cot2(π/[2m+1]) + cot2(2π/[2m + 1]) + ... + cot2(mπ/[2m + 1]) = (2m+1,3)/(2m+1,1) = [(2m+1)!/(2m-2)!(3!)]/[(2m+1)!/(2m)!] = [(2m+1)(2m)(2m-1)/6]/(2m+1)] = (2m)(2m-1)/6.
(14) Using Lemma 3 above, we know that:
csc2 x = cot2x + 1
which means that:
cot2x = csc2 x - 1
(15) Applying (cot2x = csc2x - 1) to step #13 gives us:
cot2(π/[2m+1]) + cot2(2π/[2m + 1]) + ... + cot2(mπ/[2m + 1]) =
csc2(π/[2m+1]) + csc2(2π/[2m + 1]) + ... + csc2(mπ/[2m + 1]) - m =
= (2m)(2m-1)/6.
(16) If we add m to both sides we get:
csc2(π/[2m+1]) + csc2(2π/[2m + 1]) + ... + csc2(mπ/[2m + 1]) = (2m)(2m-1)/6 + m = (2m)(2m-1)/6 + 6m/6 = (4m2 - 2m + 6m)/6 = (4m2 + 4m)/6 = (2m)(2m+2)/6
(17) From Lemma 4 above, we know that for the interval (0,π/2) we have the following inequality:
cot2x is less than 1/x2 which is less than csc2 x
(18) But this implies that:
cot2(π/[2m+1]) + cot2(2π/[2m + 1]) + ... + cot2(mπ/[2m + 1]) is less than ([2m+1]/π)2 + ([2m+1]/2π)2 + ... + ([2m+1]/mπ)2 which is less than csc2(π/[2m+1]) + csc2(2π/[2m + 1]) + ... + csc2(mπ/[2m + 1])
(19) Now since we know that
(a) cot2(π/[2m+1]) + cot2(2π/[2m + 1]) + ... + cot2(mπ/[2m + 1]) = (2m)(2m-1)/6
(b) csc2(π/[2m+1]) + csc2(2π/[2m + 1]) + ... + csc2(mπ/[2m + 1]) = (2m)(2m+2)/6
We have:
(2m)(2m-1)/6 is less than ([2m+1]/π)2 + ([2m+1]/2π)2 + ... + ([2m+1]/mπ)2 which is less than (2m)(2m+2)/6
(20) If we multiply on all sides by (π/(2m+1))2, then we have:
π2/(2m+1)2(2m)(2m-1)/6 = (π2)(2m)(2m-1)/(6)(2m+1)2
(π2)/(2m+1)2([2m+1]/π)2 + ([2m+1]/2π)2 + ... + ([2m+1]/mπ)2 = 1/1 + 1/4 + .. + 1/m2
(π2)/(2m+1)2(2m)(2m+2)/6 = π2(2m)(2m-1)/(6)(2m+1)2
(21) By Lemma 5 above, as m approaches infinity, both the left and right hand expressions approach (π2)/6 so by the Squeeze Theorem (see Lemma 3, here for proof), we have:
∑ (k=1,∞) (1/k2) = lim (m → ∞) (1/12 + 1/22 + ... + 1/m2) = π2/6
QED
References
Most of the content in today's blog is taken from the Wikipedia article on the Basel Problem. See references below for more information.
Lemma 1: cot2(x) is one-to-one on the interval (0,π/2)
Proof:
(1) Suppose there exists x,y such that cot2(x) = cot2(y) in the interval (0,π/2)
(2) By definition, cot(x) = (cos x)/(sin x) so that we have:
(cos2 x)/(sin2 x) = (cos2 y)/(sin2 y)
which means that:
(cos2 x)/(cos2 y) = (sin2 x)/(sin2 y)
(3) We also know (see Corollary 2, here), cos2(x) + sin2(x) = 1 which is the same as:
1 - sin2(x) = cos2(x)
(4) Now, we can make the same argument for y and then we can divide by y to get:
[1 - sin2(x)]/[1 - sin2(y)] = [cos2(x)]/[cos2(y)]
(5) Now, we can substitute in step #2 to give us:
[1 - sin2(x)]/[1 - sin2(y)] = (sin2 x)/(sin2 y)
(6) This amounts to:
(sin2 y)(1 - sin2 x) = (sin2 x)(1 - sin2 y)
(7) Adding (sin2 x)(sin2 y) to both sides gives us:
(sin2 y)(1 - sin2 x) + (sin2 x)(sin2 y) =
= (sin2 y)(1 - sin2 x + sin2 x) = sin2 y
(sin2x)(1 - sin2 y) + (sin2 x)(sin2 y) =
= (sin2x)(1 - sin2y + sin2 y) = sin2 x
So that we have:
sin2 y = sin2 x
(8) Squaring both sides gives us:
±(sin y) = ±(sin x)
(9) Since we know that the sin function is nonnegative on the interval (0, π/2), we know that the square has to be nonnegative. This gives us:
sin y = sin x
(10) Finally, since sin x is one-to-one on the interval (0,π/2) (see here for properties of sin), we can see that x = y.
The basic idea here is that the sin function between 0 and π/2 does not repeat any of its values. This proves that if sin x = sin y, then x = y.
QED
Lemma 2: Sum of coefficients for a polynomial
if :
f(t) = amtm + am-1tm-1 + ... + a1t + a0 where am ≠ 0
then:
the sum of the roots of f(t) [counting multiplicities] is -am-1/am
Proof:
(1) Using the Fundamental Theorem of Algebra (see here), we know that we can divide up f(t) into a sequence of m roots such that:
f(t) = am(t - r1)(t - r2)*...*(t - rm)
(2) Now when we multiply all these values together it is clear that the sum of coefficients for tm-1 = the sum of all the roots multiplied by am.
We can see that if we carry out the multiplication of (t - r1)(t - r2)*...*(t - rm), we get:
tm + tm-1(-r1 + -r2 + ... + -rm) + ... + (-r1)(-r2)*...*(-rm)
(3) We can see that the coefficient for tm-1, am-1 = -am(r1 + r2 + ... + rm)
(4) But then r1 + r2 + ... + rm = -am-1/am
QED
Lemma 3: csc2(x) = 1 + cot2(x)
Proof:
(1) sin2x + cos2x = 1 (see Corollary 2, here)
(2) Divide both sides by sin2
Then we have:
1/(sin2x) = 1 + (cos2x)/(sin2x)
(3) Since by definition, cot2x = (cos2 x)/(sin2 x) and csc2x = 1/(sin2x), step #2 gives us:
csc2 x = 1 + cot2 x
QED
Lemma 4: cot2x is less than 1/x2 which is less than csc2 x on the interval (0,π/2)
Proof:
(1) If x is in (0, π/2), then (see Theorem, here):
sin x is less than x which is less than tan x.
(2) Taking the inverse of each (since x ≠ 0 → sin x ≠ 0 and tan x ≠ 0) gives us:
csc x is greater than 1/x which is greater than cot x.
(3) Now, squaring each value gives us:
cot2 x is less than 1/x2 which is less than csc2 x.
QED
Lemma 5: as m approaches infinity, both (2m)(2m+2)/(2m+1)2 and (2m)(2m-1)/(2m+1)2 approaches 1
Proof:
(1) Putting all values into polynomial form, we have:
(2m)(2m+2) = 4m2 + 4m
(2m)(2m - 1) = 4m2 - 2m
(2m+1)2 = 4m2 + 4m + 1
(2) Now, we can calculate the limits using L'Hopital's rule (see here)
lim (m → ∞) [(4m2 - 2m)/(4m2 + 4m + 1)] = lim (m → ∞) [(8m - 2)/(8m + 4)] = lim (m → ∞) [8/8] = 1.
lim (m → ∞) [(4m2 + 4m)/(4m2 + 4m + 1)] = lim (m → ∞) [(8m + 4)/(8m + 4)] = 1.
QED
Theorem: ∑ 1/n2 = π2/6
Proof:
(1) Using De Moivre's Formula (see Corollary, here for proof) we know that:
(cos x + i sin x)n = cos(nx) + i sin(nx)
(2) Dividing both sides by (sin x)n gives us:
[cos(nx) + i sin(nx)]/(sin x)n = (cos x + i sin x)n/(sin x)n = [(cos x + i sin x)/sin x]n
(3) Since cot x = (cos x)/(sin x) [by definition, cot(x) = 1/tan(x)], we have:
[(cos x + i sin x)/sin x] = cot x + i
(4) Putting this all together gives us:
[ cos(nx) + i sin(nx) ]/(sin x)n = (cot x + i)n
(5) Using the Binomial Theorem [See here], we know that:
(cot x + i)n = cotn x + (n,1)(cotn-1x)i + ... + (n,n-1)(cot x)in-1 + in
(6) Since i2 = -1, we can now divide up all terms in step #5 so that we have:
cotn x + (n,1)(cotn-1x)i + ... + (n,n-1)(cot x)in-1 + in = [(cotnx) - (n,2)(cotn-2 x) ± ... ] + i[(n,1)(cotn-1x) - (n,3)(cotn-3x) ± ... ]
(7) Since for any identity a + bi = c + di, we know that a=c and b=d, we can build the following equation from step #2 and step #6:
[isin(nx)]/(sin x)n = i[(n,1)(cotn-1x) - (n,3)(cotn-3x) ± ... ]
(8) Dividing both sides by i gives us:
sin(nx)/(sin x)n = [(n,1)(cotn-1x) - (n,3)(cotn-3x) ± ... ]
(9) Now, since step #8 is an identity, it is true for all values n,x.
Let n = 2m + 1 where m is a positive integer.
Let x = rπ/(2m + 1) where r can = 1, 2, ..., m
From this, we can see that:
nx = (2m + 1)*(rπ)/(2m+1) = rπ
(10) From a property of sin (see Lemma 1, here), we can see that:
sin(nx) =0
(11) Applying these values to step #8 gives us:
sin(nx)/(sin x)n = 0/(sin x)n = 0 =
= [(n,1)(cotn-1x) - (n,3)(cotn-3x) ± ... ] =
= [(2m+1,1)(cot2mx) - (2m+1,3)(cot2m-2x) ± ... + (-1)m ]
(12) Using Lemma 1 above, we can conclude that the values for x in step #11 are distinct. By the above equation we know that each of these m distinct solutions for x are roots to the following equation:
(2m + 1, 1)tm - (2m + 1,3)tm-1 ± ... + (-1)m = 0
(13) Using Lemma 2 to calculate the sum of roots using the coefficients, we have:
cot2(π/[2m+1]) + cot2(2π/[2m + 1]) + ... + cot2(mπ/[2m + 1]) = (2m+1,3)/(2m+1,1) = [(2m+1)!/(2m-2)!(3!)]/[(2m+1)!/(2m)!] = [(2m+1)(2m)(2m-1)/6]/(2m+1)] = (2m)(2m-1)/6.
(14) Using Lemma 3 above, we know that:
csc2 x = cot2x + 1
which means that:
cot2x = csc2 x - 1
(15) Applying (cot2x = csc2x - 1) to step #13 gives us:
cot2(π/[2m+1]) + cot2(2π/[2m + 1]) + ... + cot2(mπ/[2m + 1]) =
csc2(π/[2m+1]) + csc2(2π/[2m + 1]) + ... + csc2(mπ/[2m + 1]) - m =
= (2m)(2m-1)/6.
(16) If we add m to both sides we get:
csc2(π/[2m+1]) + csc2(2π/[2m + 1]) + ... + csc2(mπ/[2m + 1]) = (2m)(2m-1)/6 + m = (2m)(2m-1)/6 + 6m/6 = (4m2 - 2m + 6m)/6 = (4m2 + 4m)/6 = (2m)(2m+2)/6
(17) From Lemma 4 above, we know that for the interval (0,π/2) we have the following inequality:
cot2x is less than 1/x2 which is less than csc2 x
(18) But this implies that:
cot2(π/[2m+1]) + cot2(2π/[2m + 1]) + ... + cot2(mπ/[2m + 1]) is less than ([2m+1]/π)2 + ([2m+1]/2π)2 + ... + ([2m+1]/mπ)2 which is less than csc2(π/[2m+1]) + csc2(2π/[2m + 1]) + ... + csc2(mπ/[2m + 1])
(19) Now since we know that
(a) cot2(π/[2m+1]) + cot2(2π/[2m + 1]) + ... + cot2(mπ/[2m + 1]) = (2m)(2m-1)/6
(b) csc2(π/[2m+1]) + csc2(2π/[2m + 1]) + ... + csc2(mπ/[2m + 1]) = (2m)(2m+2)/6
We have:
(2m)(2m-1)/6 is less than ([2m+1]/π)2 + ([2m+1]/2π)2 + ... + ([2m+1]/mπ)2 which is less than (2m)(2m+2)/6
(20) If we multiply on all sides by (π/(2m+1))2, then we have:
π2/(2m+1)2(2m)(2m-1)/6 = (π2)(2m)(2m-1)/(6)(2m+1)2
(π2)/(2m+1)2([2m+1]/π)2 + ([2m+1]/2π)2 + ... + ([2m+1]/mπ)2 = 1/1 + 1/4 + .. + 1/m2
(π2)/(2m+1)2(2m)(2m+2)/6 = π2(2m)(2m-1)/(6)(2m+1)2
(21) By Lemma 5 above, as m approaches infinity, both the left and right hand expressions approach (π2)/6 so by the Squeeze Theorem (see Lemma 3, here for proof), we have:
∑ (k=1,∞) (1/k2) = lim (m → ∞) (1/12 + 1/22 + ... + 1/m2) = π2/6
QED
References
- Basel Problem, Wikipedia
Sunday, August 27, 2006
The Basel Problem
Leonhard Euler first gained fame by his solution to what has been called the Basel Problem (named after Basel, Switzerland where the problem gained its notoriety). This is the resolution of the infinite sum:
∑ 1/(n2)
The problem had first been posed in 1644 by Pietro Mengoli. The problem was popularized by the celebrated mathematician Jakob Bernoulli in 1689. John Wallis calculated its value of its first three decimals (1.645...). The great Gottfriend von Leibnitz was unable to solve it. Johann Bernoulli, the younger brother of Jakob, also worked on it and failed to solve it.
By the 1730s the problem had gained a mystique as the greatest mathematicians of the age seemed unable to solve it. Then, in 1735, when he was 28, Euler announced that he had found a solution. At first, Euler succeeded in calculating the sum to six decimal places and then later, he reached his very insightful conclusion:
∑ 1/(n2) = π2/6
In today's blog, I will show the steps that Euler followed to arrive at this amazing result. This will not be a proof. Euler purposely made assumptions that enabled him to simplify the problem but which prevented his solution from rising to the level of a proof.
Solution: Euler's solution to the Basel Problem
∑ 1/(n2) = π2/6
(1) Using the Taylor expansion for sin x, we know that (see Lemma 3, here for details)
sin x = x - (x3/3!) + (x5/5!) - (x7/7!) + ...
(2) We know that sin x = 0 in the case where x = 0, ±π, ±2π, ±3π ... (see Lemma 1, here for details).
(3) Using the Fundamental Theorem of Algebra, we get:
x - (x3/3!) + (x5/5!) - (x7/7!) + ... = C(x)(x - π)(x + π)(x - 2π)(x + 2π)(x - 3π)(x + 3π)*... where C is a constant.
(4) Since for each value of π we have a pair: π and -π, we can multiply each of these pairs together to get:
x - (x3/3!) + (x5/5!) - (x7/7!) + ... = C(x)(x2 - π2)(x2 - 4π2)(x2 - 9π2)*...
(5) Since each of these x2 - nπ2 = 0, we can rearrange each to a form of (1 - x2/(nπ2) [See Corollary 1.1, here] so that we have:
x - (x3/3!) + (x5/5!) - (x7/7!) + ... = C(x)(1 - x2/π2)(1 - x2/4π2)(1 - x2/9π2)*...
(6) Now, if we divide each side by x, we get:
(sin x)/x = 1 - (x2/3!) + (x4/5!) - (x6/7!) + ... = C(1 - x2/π2)(1 - x2/4π2)(1 - x2/9π2)*...
(7) Now, since (sin x)/x = 1 as x approaches 0 (see Lemma 2, here), we see that C = 1
Here's why:
As x approaches 0, we have, C(1 - x2/π2)(1 - x2/4π2)(1 - x2/9π2)*... = C(1 - 0)(1 - 0)(1 -0)*... = C
Since sin(x)/x = 1, we can see that C = 1.
(8) So, we are left now with:
1 - (x2/3!) + (x4/5!) - (x6/7!) + ... = (1 - x2/π2)(1 - x2/4π2)(1 - x2/9π2)*...
(9) Now, in mathematics:
if we an identity (that is, an equation that is true for all cases of x):
a0 + a1x + a2x2 + ... anxn = b0 + b1x + b2x2 + ... + bnxn
then:
ai = bi
This means that we can take any power of x and the two sides must be equal.
(10) At this point, Euler took the factor x2 which gives us:
-(x2)/3! = -x2/π2 - x2/4π2 - x2/9π2 - ...
(11) Dividing -x2/π2 from both sides gives us:
π2/6 = 1 + 1/4 + 1/9 + ...
Euler would later publish a more thorough proof of his solution. See here for a proof that ∑ (1/n2) = π2/6.
References
∑ 1/(n2)
The problem had first been posed in 1644 by Pietro Mengoli. The problem was popularized by the celebrated mathematician Jakob Bernoulli in 1689. John Wallis calculated its value of its first three decimals (1.645...). The great Gottfriend von Leibnitz was unable to solve it. Johann Bernoulli, the younger brother of Jakob, also worked on it and failed to solve it.
By the 1730s the problem had gained a mystique as the greatest mathematicians of the age seemed unable to solve it. Then, in 1735, when he was 28, Euler announced that he had found a solution. At first, Euler succeeded in calculating the sum to six decimal places and then later, he reached his very insightful conclusion:
∑ 1/(n2) = π2/6
In today's blog, I will show the steps that Euler followed to arrive at this amazing result. This will not be a proof. Euler purposely made assumptions that enabled him to simplify the problem but which prevented his solution from rising to the level of a proof.
Solution: Euler's solution to the Basel Problem
∑ 1/(n2) = π2/6
(1) Using the Taylor expansion for sin x, we know that (see Lemma 3, here for details)
sin x = x - (x3/3!) + (x5/5!) - (x7/7!) + ...
(2) We know that sin x = 0 in the case where x = 0, ±π, ±2π, ±3π ... (see Lemma 1, here for details).
(3) Using the Fundamental Theorem of Algebra, we get:
x - (x3/3!) + (x5/5!) - (x7/7!) + ... = C(x)(x - π)(x + π)(x - 2π)(x + 2π)(x - 3π)(x + 3π)*... where C is a constant.
(4) Since for each value of π we have a pair: π and -π, we can multiply each of these pairs together to get:
x - (x3/3!) + (x5/5!) - (x7/7!) + ... = C(x)(x2 - π2)(x2 - 4π2)(x2 - 9π2)*...
(5) Since each of these x2 - nπ2 = 0, we can rearrange each to a form of (1 - x2/(nπ2) [See Corollary 1.1, here] so that we have:
x - (x3/3!) + (x5/5!) - (x7/7!) + ... = C(x)(1 - x2/π2)(1 - x2/4π2)(1 - x2/9π2)*...
(6) Now, if we divide each side by x, we get:
(sin x)/x = 1 - (x2/3!) + (x4/5!) - (x6/7!) + ... = C(1 - x2/π2)(1 - x2/4π2)(1 - x2/9π2)*...
(7) Now, since (sin x)/x = 1 as x approaches 0 (see Lemma 2, here), we see that C = 1
Here's why:
As x approaches 0, we have, C(1 - x2/π2)(1 - x2/4π2)(1 - x2/9π2)*... = C(1 - 0)(1 - 0)(1 -0)*... = C
Since sin(x)/x = 1, we can see that C = 1.
(8) So, we are left now with:
1 - (x2/3!) + (x4/5!) - (x6/7!) + ... = (1 - x2/π2)(1 - x2/4π2)(1 - x2/9π2)*...
(9) Now, in mathematics:
if we an identity (that is, an equation that is true for all cases of x):
a0 + a1x + a2x2 + ... anxn = b0 + b1x + b2x2 + ... + bnxn
then:
ai = bi
This means that we can take any power of x and the two sides must be equal.
(10) At this point, Euler took the factor x2 which gives us:
-(x2)/3! = -x2/π2 - x2/4π2 - x2/9π2 - ...
(11) Dividing -x2/π2 from both sides gives us:
π2/6 = 1 + 1/4 + 1/9 + ...
Euler would later publish a more thorough proof of his solution. See here for a proof that ∑ (1/n2) = π2/6.
References
- Julian Havil, Gamma: Exploring Euler's Constant, Princeton University Press, 2003
- Jay R. Goldman, The Queen of Mathematics, AK Peters, Ltd., 1998
- G. Polya, Induction and Analogy in Mathematics, Princeton University Press, 1954.