5
$\begingroup$

While attending a math puzzle contest, my friend (a math student) asked me to prove that $$\sum_{k=1}^n \frac{1}{k} \notin \mathbb{Z} \quad \forall n \geq 2$$

Being the first time seeing this problem, I came up with a proof that required the following conjecture:

(1) Given a composite number $n \geq 4$, $\exists p$ prime such that $$p < n < 2p$$

My friend told me that this followed directly from Bertrand's Postulate (and it indeed does).

Now Bertrand's postulate, which says that there exists a prime between $n$ and $2n$, has a pretty involved proof. My question is:

Question: Is there a simpler proof of Bertrand's Postulate if we take $n$ to be prime (which is all I need)? If so could someone either provide a reference or proof/sketch for the same? So far I have come up empty...

Thanks for your time.

PS: Here is how I link (1) with Bertrand's Postulate: Define for composite $n \geq 4$ $$p(n) = \max \{p : p \leq n, \quad p \mbox{ prime} \}$$ Suppose (1) is wrong, then for some $n$, we have $$2p(n) \leq n$$ This also means that $\{p(n)+1, \cdots 2p(n)\}$ are all composite. However by Bertrand's Postulate, between $p(n)$ and $2p(n)$, there is a prime $q$. $\Rightarrow\Leftarrow$

$\endgroup$
2
  • 2
    $\begingroup$ I suppose you are aware that $\sum_{k=1}^n \frac{1}{k} \notin \mathbb{Z} \quad \forall n \geq 2$ has a (well-known) simpler proof, by looking modulo powers of $2$ $\endgroup$ – Ewan Delanoy Apr 9 '14 at 5:53
  • 1
    $\begingroup$ @Ewan: Yes I am. That was the proof my friend expected. However I needed to give some background on how I encountered this problem. $\endgroup$ – Gautam Shenoy Apr 9 '14 at 5:55
3
$\begingroup$

Oh Dear...

I just realized that proving the result for $n$ prime implies proving it for all $n \geq 4$. Here is my reasoning:

Let $p(n)$ be as before i.e. the prime number closest to $n$ and less than $n$. Then IF there was a simpler proof of Bertrand postulate for primes, then there exists a prime number $q$ between $p(n)$ and $2p(n)$. There are $2$ cases: $$p(n)<q<n<2p(n)<2n$$ and $$p(n)<n<q<2p(n)<2n$$

Case 1 would contradict maximality of p(n), leaving us with case 2, which is exactly Bertrand's postulate.

So if there is a simple(r) proof of Bertrand postulate for primes, the above argument extends it to $n \geq 4$. Hence it is "unlikely" for there to be a simple proof for the primes case since Erdos' proof is considered to be the simplest one as of now.

$\endgroup$
2
  • $\begingroup$ @guatam, I tried using your same approach on another conjecture, but failed. Have you got any thoughts? Here is the conjecture: math.stackexchange.com/questions/1422179/… $\endgroup$ – Colm Bhandal Sep 5 '15 at 15:09
  • $\begingroup$ Bertrand implies a prime on p, 2p. Choose p(n) max less than a non-prime n. Then there is a prime on n, 2p(n) which implies a prime on n,2n (Bertrand). So I think the two are equivalent. You don't need case 1, for the reason you give. $\endgroup$ – daniel Sep 5 '15 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.