|
re. .-1
Eric, the sequence looks like:
{ 2, 2, 2, 5, 7, 13, 23, 43, 75, 137, 255, 464, 872, 1612, 3030, ... }
where 3030 is the number of primes between 2^15 and 2^16
/Kostas
|
| Let n be a positive integer >= 2, p be a positive integer prime,
and x a positive real number >= 2. The number of primes <= x is
usually written with the pi symbol, so let pi(x) be the number of
primes <= x. Let C(n,m) = n!/(m!(n-m)!) be that binomial coefficient.
Let [y] be the least integer <= y for any real number y. Let
t(x,p) be the largest integral power of p <= x, so that
t(x,p) = [ln x / ln p] and also p^t(x,p) <= x < p^(1+t(x,p)).
A) 2^n < C(2n,n) < 2^2n
Proof:
C(2n,n) = (2n)!/(n!)^2
= (2n * ... * 2)(2n-1 * ... * 1)/(n!)^2
= (2n * ... * 2)/n! * (2n-1 * ... * 1)/(n * ... * 1)
= 2^n * (2n-1)/n * ... * 1/1
This shows C(2n,n) is 2^n times a product of n >= 2 terms
all of which, except for the last, are > 1 and the last is = 1.
Therefore C(2n,n) > 2^n.
It also shows C(2n,n) is 2^n times a product of n >= 2 terms
all of which are < 2. Therefore C(2n,n) < 2^n * 2^n = 2^2n.
B) [2y] - 2[y] is 0 or 1 for all reals y
C) The number of times the prime p divides n! is given by the
sum of one for each of the [n/p] multiples of p <= n, plus
one more for each of the [n/p^2] of those which are actually
multiples of p^2, plus one more for each of the [n/p^3] of
*those* which are actually multiple of p^3, plus .... This
infinite sum is really a finite sum because the terms for
exponents greater than t(n,p) are all zero. This sum is
sum(m=1,...,oo) [n/p^m] = sum(m=1,...,t(n,p)) [n/p^m].
D) The number of times the prime p divides C(2n,n) [adding for
the numerator and subtracting for the denominator] is therefore
sum(m=1,...,oo) ([2n/p^m] - 2[n/p^m]) =
sum(m=1,...,t(2n,p)) ([2n/p^m] - 2[n/p^m]) by part (C). By
part (B) this is a sum of t(2n,p) terms each of which is 0 or 1
and so 0 <= the number of times the prime p divides C(2n,n) <= t(2n,p).
[digression: therefore C(2n,n) is an integer]
E) The least common multiple of the numbers 1,...,n is the
product over all primes p of p^t(n,p). This infinite product
is really a finite product as all of the terms for p > n are
equal to 1.
F) By parts (D) and (E), C(2n,n) divides evenly into lcm({1,...,2n})
and so C(2n,n) <= lcm({1,...,2n}) = prod(p <= 2n) p^t(2n,p).
G) By parts (A) and (F) 2^n < C(2n,n) <= prod(p <= 2n) p^t(2n,p).
The product on the right has pi(2n) terms, each of which is <= 2n.
Therefore 2^n < (2n)^pi(2n) and so n ln 2 < pi(2n) ln 2n and
pi(2n) > (n ln 2) / ln 2n or pi(2n) > ((1/2)ln 2) 2n/ln 2n
H) By part (G) there exists a positive real number A such that
pi(x) > A x/ln x for all x >= 2.
Proof:
To go from (G) to (H) seems easy enough, ((1/2)ln 2) almost
works for A, except for the small difference between x/ln x
and 2n/ln 2n. The following just grinds through to show
you only have to divide by 2 at most.
Note that x/ln x decreases as x grows from 2 to e, reaches
its minimum for x >= 2 at x = e, then increases as x
increases for x > e, not reaching as high as it does for x=2
until x >= 4. For x >= e (i.e., in the increasing range)
(x+1)/ln (x+1) < (x+1)/ln x = x/ln x + 1/ln x and so
increasing x by 1 increases x/ln x by less than 1/ln x <= 1.
Let x >= 4, and let the positive integer n be such that
2n <= x < 2(n+1), i.e., n <= [x/2]. x >= 4 so x/2 >= 2
so [x/2] >= 2 so n >= 2 and therefore (G) applies.
Thus pi(x) >= pi(2n) > ((1/2)ln 2) 2n/ln 2n. But
x/ln x <= x/ln 2n = 2n/ln 2n + (x-2n)/ln 2n < 2n/ln 2n + 2/ln 2n.
<= 2n/ln 2n + 2/ln 4.
So 2n/ln 2n > x/ln x - 2/ln 4 and therefore
pi(x) > ((1/2)ln 2) (x/ln x - 2/ln 4). For x >= 4, x/ln x
always is >= 4/ln 4 and so -4/ln 4 >= - x/ln x, or
-2/ln 4 >= - (1/2) x/ln x, so x/ln x - 2/ln 4 >= (1/2) x/ln x.
Thus pi(x) > ((1/2)ln 2) (1/2) x/ln x = ((1/4)ln 2) x/ln x.
If 2 <= x <= 4, then pi(x) is 1 or 2 and x/ln x <= 2/ln 2
so there is an A1 such that pi(x) > A1 x/ln x; just let
A1 < (1/2)ln 2 and then A1 x / ln x < 1 < pi(x).
Now let A be the minimum of (1/4)ln 2 and A1. A = (1/4)ln 2
works, and for all x >= 2, pi(x) > A x/ln x.
I) prod(n < p <= 2n) p divides C(2n,n), because each such prime p
occurs once in the numerator and not at all in the denominator.
J) By (A) and (I), prod(n < p <= 2n) p <= C(2n,n) < 2^2n and so
sum(n < p <= 2n) ln p < 2n ln 2. Therefore
sum(p <= 2n) ln p <= 2n ln 2 + sum(p <= n) ln p.
K) sum(p <= x) ln p >= sum(sqrt(x) < p <= x) ln p
>= sum(sqrt(x) < p <= x) ln sqrt(x)
= sum(sqrt(x) < p <= x) (1/2)ln x
>= (1/2) (pi(x) - sqrt(x)) ln x
where the last inequality holds because of the pi(x) primes p <= x,
certainly at most sqrt(x) of them are <= sqrt(x).
L) By part (K), pi(x) <= sqrt(x) + (2 / ln x) sum(p <= x) ln p
M) sum(p <= 2^k) ln p < 2^(k+1) for all positive integers k
Proof by induction: For k = 1 this is ln 2 < 4 and is true.
Assume the statement is true for k = 1,...,m and try to
prove it true for k = m+1.
By (J) sum(p <= 2n) ln p <= 2n ln 2 + sum(p <= n) ln p.
So sum(p <= 2^(m+1)) ln p = sum(p <= 2 * 2^m) ln p
<= 2^(m+1) ln 2 + sum(p <= 2^m) ln p
By the inductive hypothesis sum(p <= 2^m) ln p < 2^(m+1)
Therefore, sum(p <= 2^(m+1)) < 2^(m+1) ln 2 + 2^(m+1)
= 2^(m+1) * (1 + ln 2)
< 2^(m+1) * 2 = 2^((m+1)+1)
and so (M) is true for all positive integers k by induction
N) Let x be any real >= 2. Let k = t(x,2) = [ln x / ln 2] so that
2^k <= x < 2^(k+1). Then sum(p <= x) ln p <= sum(p <= 2^(k+1)) ln p
which by (M) is less than 2^(k+2) so sum(p <= x) ln p < 2^(k+2).
But 2^k <= x so 2^(k+2) <= 4x therefore sum(p <= x) < 4x.
O) By (L) pi(x) <= sqrt(x) + (2 / ln x) sum(p <= x) ln p and so
by (N) pi(x) < sqrt(x) + (2 / ln x) 4x. Therefore there
exists a positive real number B such that pi(x) < B x/ln x for
all x >= 2.
Proof:
We have pi(x) < sqrt(x) + 8 x/ln x for x >= 2.
Let C be such that sqrt(x) < C x/ln x for all x >= 2.
Then pi(x) < B x/ln x for B = 8 + C. I think C = 1
already works which gives 9 for B. This is not a particularly
tight bound.
P) (Chebyshev, 1852) There exists positive real constants A and B
such that for all real x >= 2
x x
A ---- < pi(x) < B ----
ln x ln x
Errors, if any, are mine, not Chebyshev's.
He also proved that if the limit as x -> oo of pi(x) / (x/ln x)
exists, then that limit must be 1. That proof isn't much more
involved than this one. The hard part is to show that the limit
does exist.
Dan
|