|
|
|
|
upper bound on
|
(Theorem)
|
|
Theorem Let $\vartheta(n)$ be the Chebyshev function $$ \vartheta(n)=\sum_{\substack{p\le n\\p{\:\mathrm{prime}}}} \log p. $$ Then $\vartheta(n)\le n\log 4$ for all $n\ge 1$
Proof. By induction.
The cases for $n=1$ and $n=2$ follow by inspection.
For even $n>2$ the case follows immediately from the case for $n-1$ since $n$ is not prime.
So let $n=2m+1$ with $m>0$ and consider $(1+1)^{2m+1}$ and its binomial expansion. Since $\displaystyle {{2m+1}\choose m}={{2m+1}\choose{m+1}}$ and each term occurs exactly once, it follows that $\displaystyle {{2m+1}\choose m}\leq 4^m$ Each prime $p$ with $m+1<p\leq 2m+1$ divides ${2m+1}\choose m$ implying that their product also divides $\displaystyle {{2m+1}\choose m}$ Hence $$ \vartheta(2m+1)-\vartheta(m+1)\le\log{{2m+1}\choose m}\le m\log
4. $$ By the induction hypothesis, $\vartheta(m+1)\leq(m+1)\log4$ and so $\vartheta(2m+1)\leq(2m+1)\log4$ 
- 1
- G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1938.
|
"upper bound on " is owned by mps.
|
|
(view preamble | get metadata)
Cross-references: induction hypothesis, product, divides, prime, even, induction, Chebyshev function
There are 3 references to this entry.
This is version 2 of upper bound on , born on 2006-08-13, modified 2006-08-14.
Object id is 8246, canonical name is UpperBoundOnVarthetan.
Accessed 1304 times total.
Classification:
| AMS MSC: | 11A41 (Number theory :: Elementary number theory :: Primes) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|