upper bound on
Theorem.
Let be the Chebyshev function
Then for all .
Proof.
By induction.
The cases for and follow by inspection.
For even , the case follows immediately from the case for since is not prime.
So let with and consider and its binomial expansion (http://planetmath.org/BinomialTheorem). Since and each term occurs exactly once, it follows that . Each prime with divides , implying that their product also divides . Hence
By the induction hypothesis, and so .∎
References
- 1 G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1938.