[Ⅳ] θ(x)＝Ｏ(x)　の証明

チェビシェフのシータ関数：θ(x)＝Σ_[p≦x] log(p) がオーダ－xであること、すなわち

・　∃ｋ＞0　｜θ(x)｜≦ｋx          

を3段階で証明します。

（1）2nlog2≧θ(2n)－θ(n)　の証明

2項定理より

2²ⁿ＝(1＋1)²ⁿ＝Σ_{[k＝1～2n] 2n}C_ｋ1^k1^2n-k≧_2nC_n＝2n・(2n－1)・(2n－2)・・(n+2)・(n+1)／n！

_2nC_nは自然数なので、分母のｎ！は約分されて1になります。しかしn+1＜p≦2nの素数pはn！の中には存在しないので、約分されずに分子に残ります。右辺はn+1＜p≦2nの素数pの積Π_{[n+1≦p≦2n]} pより大きくなるので、

・　2²ⁿ≧Π_{[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

です。よって

・　2²ⁿ≧exp[θ(2n)－θ(n)]　→　2n・log2≧θ(2n)－θ(n)

が成り立ちます。

Eg.  ₁₆C₈=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）2^ｍ+1・log2＞θ(2^m)　の証明

　上式にn＝2^k－1を代入すると、2^k・log2≧θ(2^k)－θ(2^k－1)が成り立つ。

k＝1：　2¹・log2≧θ(2¹)－θ(1)　

k＝2：　2²・log2≧θ(2²)－θ(2¹)

k＝3：　2³・log2≧θ(2³)－θ(2²)

・・・ 　　・・・・

k＝m－1：2^m－1・log2≧θ(2^m－1)－θ(2^m－2)

k＝m：　 2^m・log2≧θ(2^m)－θ(2^m－1)

をすべて加えると、θ(1)＝0より

　　log2・Σ_[k＝1～m]2^k ≧θ(2^m)

を得ます。ここで

　　Σ_[k＝1～m]2^k＝2^m+1－2＜2^m+1

だから、

　　2^m+1 log2＞θ(2^m)

が示されました。

(3) θ(x) ≦4log2・x

x≧1なる整数xに対して、∃m∊N、2^m≦x≦2^m+1

θ(x)は非減少関数なので、（2）より

　　0≦θ(x) ≦θ(2^m+1)＜2^m+2 log2≦4 log2・2^m≦4 log2・x

よって、K＝4 log2とおくと

　　θ(x) ≦Kx、　→　θ(x)＝O(x)

が示されました。