[Ⅳ] θ(x)=O(x) の証明
チェビシェフのシータ関数:θ(x)=Σ[p≦x] log(p) がオーダ-xであること、すなわち
・ ∃k>0 |θ(x)|≦kx
を3段階で証明します。
(1)2nlog2≧θ(2n)-θ(n) の証明
2項定理より
22n=(1+1)2n=Σ[k=1~2n] 2nCk1k12n-k≧2nCn=2n・(2n-1)・(2n-2)・・(n+2)・(n+1)/n!
2nCnは自然数なので、分母のn!は約分されて1になります。しかしn+1<p≦2nの素数pはn!の中には存在しないので、約分されずに分子に残ります。右辺はn+1<p≦2nの素数pの積Π[n+1≦p≦2n] pより大きくなるので、
・ 22n≧Π[n+1≦p≦2n] p
が成り立ちます。一方
・ θ(2n)-θ(n)=Σ[p≦2n] log(p)-Σ[p≦n] log(p)=Σ[n+1≦p≦2n] log(p)
なので、
・ exp[θ(2n)-θ(n)]=exp[Σ[n+1≦p≦2n] log(p)]=Π[n+1≦p≦2n] p
です。よって
・ 22n≧exp[θ(2n)-θ(n)] → 2n・log2≧θ(2n)-θ(n)
が成り立ちます。
Eg. 16C8=16・15・14・13・12・11・10・9/8・7・6・5・4・3・2・1
=2・3・13・11 >11・13(8+1≦11,13≦16)
(2)2m+1・log2>θ(2m) の証明
上式にn=2k-1を代入すると、2k・log2≧θ(2k)-θ(2k-1)が成り立つ。
k=1: 21・log2≧θ(21)-θ(1)
k=2: 22・log2≧θ(22)-θ(21)
k=3: 23・log2≧θ(23)-θ(22)
・・・ ・・・・
k=m-1:2m-1・log2≧θ(2m-1)-θ(2m-2)
k=m: 2m・log2≧θ(2m)-θ(2m-1)
をすべて加えると、θ(1)=0より
log2・Σ[k=1~m] 2k ≧θ(2m)
を得ます。ここで
Σ[k=1~m] 2k=2m+1-2<2m+1
だから、
2m+1 log2>θ(2m)
が示されました。
(3) θ(x) ≦4log2・x
x≧1なる整数xに対して、∃m∊N、2m≦x≦2m+1
θ(x)は非減少関数なので、(2)より
0≦θ(x) ≦θ(2m+1)<2m+2 log2≦4 log2・2m≦4 log2・x
よって、K=4 log2とおくと
θ(x) ≦Kx、 → θ(x)=O(x)
が示されました。