We know that \(N\) is a multiple of a prime factor¹In fact, all such factors. of each number \(x\) from \(2\) to \(n+1\). For each such \(x\) and prime factor \(p_x\), Proposition 1.2.6 guarantees that \(N-x\) is also a multiple of \(p_x\).

We follow Stopple's presentation in Section 5.2 of [C.3.5] closely in sketching out most of a proof of this below; see also [C.1.11]. It is a little longer than some of our other proofs. It uses some very basic combinatorial ideas and calculus facts, however, so it is a great example of several parts of mathematics coming together.

First, it's not hard to verify this for \(x<1000\).

Now we'll proceed by induction, in an unusual way. We'll assume it is true for \(n\), and prove it is true for \(2n\). This needs a little massaging for odd numbers, but is a legitimate induction method.

With this in mind, we first assume that \(\pi(n)<2\frac{n}{\log(n)}\). Now what?

Below, in Lemma 21.3.6 we look at the product of all the primes (if any) between \(n\) and \(2n\), which we write as \begin{equation*}P=\prod_{n<p<2n} p\, .\end{equation*} In that result some combinatorial thinking leads to the following estimate: \begin{equation*}n^{\pi(2n)-\pi(n)}<P\leq \frac{(2n)!}{n!n!}<2^{2n}\end{equation*} These bounds show that \(P\) is between a certain power of \(n\) and a certain power of \(2\).

Now we will manipulate this to get the final result. Begin by taking \(\log\) of both ends to get \begin{equation*}(\pi(2n)-\pi(n))\log(n)<2n\log(2)\end{equation*} Now divide out and isolate to get \begin{equation*}\pi(2n)<\frac{2n\log(2)}{\log(n)}+\pi(n)<\frac{2n\log(2)}{\log(n)}+2\frac{n}{\log(n)}=(\log(2)+1)\frac{2n}{\log(n)}\, .\end{equation*}

In Exercise 21.5.8 you will show that, as long as \(n> 1000\), we have the inequality \begin{equation*}\frac{\log(2)+1}{\log(n)}<\frac{2}{\log(2)+\log(n)}=\frac{2}{\log(2n)}\end{equation*}

Now we can put it all together to see that \begin{equation*}\pi(2n)<(\log(2)+1)\frac{2n}{\log(n)}<2\frac{2n}{\log(2n)}\, ,\end{equation*} which is exactly what the proposition would predict.

To rescue this for \(2n+1\), we need another calculus comparison. First, from above we have \begin{equation*}\pi(2n+1)\leq \pi(2n)+1<\frac{2n\log(2)}{\log(n)}+\pi(n)+1\end{equation*}\begin{equation*}<\frac{2n\log(2)}{\log(n)}+2\frac{n}{\log(n)}+1\end{equation*} Since \(\frac{2n+1}{\log(2n+1)}>\frac{2n}{\log(2n+1)}\), it will suffice then to show \begin{equation*}(2+2\log(2))\frac{n}{\log(n)}+1<\frac{2n}{\log(2n+1)}\; .\end{equation*} Since \(n>1000\), \begin{equation*}(2+2\log(2))\frac{n}{\log(n)}+1<3.386\frac{n}{\log(n)}+1<3.394\frac{n}{\log(n)}\end{equation*} so it suffices to show \begin{equation*}3.394\frac{n}{\log(n)}<\frac{2n}{\log(2n+1)}\; .\end{equation*} Showing this is Exercise 21.5.9.

Think of all the primes in question. On the one hand, each of these primes \(p\) is greater than \(n\), and there are \(\pi(2n)-\pi(n)\) of them. So \begin{equation*}n^{\pi(2n)-\pi(n)}<P\, .\end{equation*}

On the other hand, each of these primes is greater than \(n\) but they are all in the list of numbers from \(n\) to \(2n\), so their product divides \begin{equation*}\frac{(2n)\cdot (2n-1)\cdot (2n-2)\cdots (n+1)}{n\cdot (n-1)\cdot (n-2)\cdots 1}\end{equation*}

That is to say \(P\) is a factor of a binomial coefficient \begin{equation*}P \mid \frac{(2n)\cdot (2n-1)\cdot (2n-2)\cdots (n+1)}{n\cdot (n-1)\cdot (n-2)\cdots 1}=\frac{(2n)!}{n!n!}\end{equation*} and in particular, \begin{equation*}P\leq \frac{(2n)!}{n!n!}\end{equation*}

Now here is the conceptual key of the proof. We reinterpret this factorial fraction as the number of ways to choose \(n\) things from a collection of \(2n\) things! And the number of ways to choose \(n\) things is certainly less than the number of ways to pick any old collection out of \(2n\) things, which is \(2^{2n}\) (because you either pick it or you don't).

Since we showed both bounds, this concludes the proof.