0
$\begingroup$

I got a question in an assignment but I'm sure it has to be a misprint, any clarification on this would be much appreciated ( though I want to work the actual problem out myself)

It's about Bertrands postulate, particularly we've been asked to consider the lemma which states that for $n>2$ and $\tfrac{2n}{3}<p\leq n$, $p$ does not divide $\pmatrix{2n\\n}$, and then explain why this means that all prime factors of $\pmatrix{2n\\n}$ satisfy $p\leq \tfrac{2n}{3}$.

but then take for example $n=3$ then $\pmatrix{2n\\n}$= $\pmatrix{6\\3}=\tfrac{6.5.4.3.2.1}{3.2.1.3.2.1.}=\tfrac{6.5.4}{3.2}=5.2^2$ and so 5 appears in the prime decomposition. But then this contradicts what we were trying to show because $\tfrac{2n}{3}=\tfrac{6}{3}=2$and 5 is certainly not less than 2. Surely the thing we should be trying to show is that $p\geq\tfrac{2n}{3}$ , no ?

$\endgroup$
1
$\begingroup$

First, it is correct that $\binom{2n}{n}$ has no prime factor $p$ such that $\frac{2n}3 \lt p \le n$. It follows that all prime factors $p$ are either $\le \frac{2n}3$ or greater than $n$. As you've seen with $n = 3$, both cases can occur.

Since the intent is to prove Bertrand's postulate, i.e., that there is some prime between $n$ and $2n$, I suspect the plan was to assume the contrary and eventually arrive at a contradiction. Under this assumption, all prime factors of $\binom{2n}{n}$ must be either $\le \frac{2n}3$ or greater than $2n$. If that is what's going on, your next step is simply to eliminate the possibility that $p \gt 2n$. That isn't hard. The difficult step is to show that the contribution of the primes $\lt \frac{2n}3$ is not actually large enough to produce $\binom{2n}{n}$, yielding the desired contradiction.

$\endgroup$
  • $\begingroup$ Sorry I should have been more clear, we don't actually have to prove bertrands postulate, just explain why the part of the lemma I stated means that $p\leq\tfrac{2n}{3}$. But I assume your answer is still what I would need to use to explain this $\endgroup$ – excalibirr Mar 24 '19 at 23:44

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.