PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] upper bound on $\vartheta(n)$ (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$ $ \qedsymbol$

Bibliography

1
G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1938.




"upper bound on $\vartheta(n)$" is owned by mps.
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

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 $\vartheta(n)$, born on 2006-08-13, modified 2006-08-14.
Object id is 8246, canonical name is UpperBoundOnVarthetan.
Accessed 1304 times total.

Classification:
AMS MSC11A41 (Number theory :: Elementary number theory :: Primes)

Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)