Problem solving in NT ( day 3 Week 1)

 OMG Prime number theorem!!! I actually loved it! So today I solved a quite fancy NT problem with other people's help though!

Problem: Prove that there exists an interval of the $[n^2,(n+1)^2]$ which contains at least $1000$ primes.

Proof 1: By PNT, if $n$ is large enough $$\pi(n) ~ \frac{n}{\log(n)}$$

So $$f(n)=\pi( {n+1}^2)-\pi( n^2) = \frac{(n+1)^2}{\log({n+1}^2)}- \frac{n^2}{\log(n^2)}$$

$$= \frac{(n+1)^2}{2\log({n+1})}- \frac{n^2}{2\log(n)}$$

Then $$f'(n)= \frac{(2n+2)\log(n+1)-(n+1)}{2[\log(n+1)]^2}-\frac{2n\log(n)-n}{2[\log(n)]^2}$$

$$=\frac{n+1}{\log(n+1)}+\frac{n}{2[\log(n)]^2}- (\frac{n}{\log(n)}+\frac{n+1}{2[\log(n+1)]^2})$$

Take  $$h(x)= \frac{(x)}{\log(x)}, g(x)=\frac{x}{2\log^2(x)}$$

we have basically $$(h(n+1)-h(n))>>>( g(n+1)-g(n))$$ since $h$ grows faster than $g$ we have  $$h(n+1)-h(n) > (g(n+1)-g(n)$$ for large enough $n$.

Infact $f'(n)$ is strictly increasing.

Now, by MVT, note that there exist $t_1$ such that $$f(2)-f(1)=f'(t_1), t\in [1,2]$$

Similarly  there exist $t_2$ such that $$f(3)-f(2)=f'(t_2), t\in [2,3]$$

and so on,  there exist $t_{n-1}$ such that $$f(n)-f(n)=f'(t_{n-1}), t\in [n-1,n]$$

So $f(n)-f(1)$ tends to infinity as $f'$ is increasing and positive.. 

So $f(n)$ is increasing and diverges!

Tonight I will revise O notation and make notes! Hopefully I can survive!

Sunaina