Chặn Chebyshev: θ(n) < (log 4) n

Ta dùng quy nạp mạnh theo $n$. Trường hợp cơ sở $n=1,2$ hiển nhiên: $\theta(1)=0$ và $\theta(2)=\log 2 < \log 4$.

Với bước quy nạp, giả sử chặn đúng với mọi số nguyên dương nhỏ hơn $n$. Nếu $n>2$ chẵn, $n$ không nguyên tố, nên $\theta(n)=\theta(n-1) < (\log4)(n-1) < (\log4)n$ theo giả thiết quy nạp áp dụng cho $n-1$.

Nếu $n=2m+1$ lẻ, xét hệ số $\binom{2m+1}{m}=\dfrac{(2m+1)!}{m!\,(m+1)!}$. Nó xuất hiện hai lần trong $2^{2m+1}$ số hạng của khai triển nhị thức $(1+1)^{2m+1}$ (một lần là $\binom{2m+1}{m}$, một lần là $\binom{2m+1}{m+1}$, và chúng bằng nhau), nên $2\binom{2m+1}{m} \le 2^{2m+1}$, cho $\binom{2m+1}{m} \le 4^m$.

Mọi số nguyên tố $p$ với $m+1 < p \le 2m+1$ chia hết tử số $(2m+1)!$ nhưng không chia hết $m!$ lẫn $(m+1)!$ (vì $p>m+1$), nên $p$ chia hết $\binom{2m+1}{m}$. Do đó tích mọi số nguyên tố như vậy chia hết $\binom{2m+1}{m}$, nên $\prod_{m+1<p\le 2m+1} p \le \binom{2m+1}{m} \le 4^m$, tức $\theta(2m+1)-\theta(m+1) \le (\log 4)\,m$.

Theo giả thiết quy nạp áp dụng cho $m+1<n$, $\theta(m+1) < (\log4)(m+1)$. Cộng lại, $\theta(n)=\theta(2m+1) < (\log4)(m+1) + (\log4)m = (\log4)(2m+1) = (\log4)n$, hoàn tất quy nạp.