In the number theory course, I was asked to prove the following:
$$2^{\pi(n)} \sqrt{n} > n \mathrm{\, for\, all\, } n > 1 \in \mathbb{N}$$, where $\pi(n)$ denotes the number of prime number less than or equal to $n$.
Before this question, there is a "part a" question goes like this:
For any $m \leq n \in N$, $m$ has the form $m = b^2 p_1^{e_1}p_2^{e_2}...p_{k}^{e_k}$, where $b \leq \sqrt{m}$ , $e_i = 0$ or $1$ , $p_i$ is the $i_{th}$ prime and $k = \pi(n)$.
This "part a" question is easy. However, I can't see how this question could guide me to the main question. For the main question, I use strong induction with tools in analysis, goes like this:
Base step: The case $n = 2$ is trivial.
Inductive step: Suppose the statement holds for all $n < N$, when $n = N$,
Case I: $N$ is prime. Then $\pi(N) = \pi(N-1) + 1 $, then $2^{\pi(N)} \sqrt{N} = 2^{\pi(N)} \sqrt{(N-1)+1} \geq 2^{\pi(N)} \sqrt{N-1}(1 + \dfrac{1}{2(N-1)}) (\mathrm{By\, Bernoulli's\, inequality}) = 2^{\pi(N)} \sqrt{N-1} + 2^{\pi(N-1)}\dfrac{1}{\sqrt{N-1}} > N - 1 + 1 = N$
The above argument should be fine. However, for the case which $N$ is composite, I want to argue by the following: Let $N = mn $ for some $1 < m < N$ and $1 < n < N$, then by the inductive hypothesis, $2^{\pi(n)} \sqrt{n} > n $ and $2^{\pi(m)} \sqrt{m} > m $.
An obvious following step is to multiply these two inequalities together to get the desired result. However, is it true in general that $\pi(mn) \geq \pi(m) + \pi(n)$? I get stuck at this point. Need I use the result of "part a" question?
Yes you may use (the former result plus Euler's product formula which implies that 1/p is convergent), or (simply Bertrand's postulate and MI).
The result of your problem gives a proof of infinitude of primes! There are 126 methods (if I remember correctly) to prove that there are infinitely many prime numbers, all of which are accessible on the Internet I suppose.