チェビシェフの評価:θ(n) < (log 4) n

$n$ に関する強い数学的帰納法を用いる。基底段階 $n=1,2$ は自明:$\theta(1)=0$、$\theta(2)=\log 2 < \log 4$。

帰納段階では、$n$ より小さいすべての正の整数について評価が成り立つと仮定する。$n>2$ が偶数なら $n$ は素数でないので、帰納法の仮定を $n-1$ に適用して $\theta(n)=\theta(n-1) < (\log4)(n-1) < (\log4)n$。

$n=2m+1$ が奇数の場合、係数 $\binom{2m+1}{m}=\dfrac{(2m+1)!}{m!\,(m+1)!}$ を考える。これは $(1+1)^{2m+1}$ の二項展開の $2^{2m+1}$ 個の項のうち2回現れる($\binom{2m+1}{m}$ として1回、$\binom{2m+1}{m+1}$ として1回、両者は等しい)ので、$2\binom{2m+1}{m} \le 2^{2m+1}$、すなわち $\binom{2m+1}{m} \le 4^m$。

$m+1 < p \le 2m+1$ を満たすすべての素数 $p$ は分子 $(2m+1)!$ を割り切るが $m!$ も $(m+1)!$ も割り切らない($p>m+1$ のため)ので、$p$ は $\binom{2m+1}{m}$ を割り切る。したがってそのようなすべての素数の積が $\binom{2m+1}{m}$ を割り切り、$\prod_{m+1<p\le 2m+1} p \le \binom{2m+1}{m} \le 4^m$、すなわち $\theta(2m+1)-\theta(m+1) \le (\log 4)\,m$。

$m+1<n$ に帰納法の仮定を適用すると $\theta(m+1) < (\log4)(m+1)$。足し合わせると $\theta(n)=\theta(2m+1) < (\log4)(m+1) + (\log4)m = (\log4)(2m+1) = (\log4)n$ となり、帰納法が完了する。