You Can (Not) Divide (2.5)

         This is a a bit of a different post compared to the other ones in the series for a couple of reasons (other than the title reference), so let's start there:

As you may have noticed, it may seem like I missed exercise $2.4$.  The truth is not nearly as exciting as any conspiracy theories you may be imagining though; that exercise just happens to be to complete the second part of a proof given as an example. It's pretty straightforward and follows the exact same structure the first part does, so I don't think it would make too much sense to do it here.

The second one is a confession: I've seen and solved problem $2.5$ before!  It was quite a while ago and I used a slightly different method, but the key happens to be the same so it wasn't much of a challenge this time. That being said, I'll try to describe the path that a reader might take to tackle this question after having read previous examples in the book.

         A natural thing to do when faced with a sum of fractions is to find a way to write it as a single fraction, so let's start with that:

$ \dfrac{2 \times 3 \times \ldots \times n + 3 \times 4 \times \ldots \times n + 2 \times 4 \times \ldots \times n + 2 \times 3 \times \ldots \times (n-1)}{n!}$

We're asked to prove that this is never an integer, but what does that mean? Well, it means that there's something in the denominator that we can never cancel with the numerator. Let that something be a prime $p \leq n$. Why prime? Well, it could be composite number, but that just means there's $2$ or more primes we can't cancel. Do note that $p$ doesn't need to be the same for every $n$, a small detail that will have important consequences.

In any case, proving the original statement is the same as showing that the numerator is never equal to $0$ (mod $p$). This is particularly useful to the reader since the previous example has almost the exact same expression, and Terry shows how to write this numerator in a much nicer way:

\[\begin{equation*}\dfrac{n!}{1} +\dfrac{n!}{2} + \dfrac{n!}{3} + \ldots + \dfrac{n!}{n} \end{equation*} \]

Now this is where it gets interesting. Thinking about the expression above a bit may lead to the following argument:

In each of the terms of the sum, one of the factors in the numerator disappears cancelling the respective denominator. So for each term we're left with something of the shape $a_ip$ where $a_i$ is the multiplication of everything else left bar $p$. This is true for all except for the $p$-th element. In this one, the integer that disappears is $p$ so we're left with $a_p$. Rewriting the previous expression:

$a_1p + a_2p + \ldots + a_p + \ldots + a_np$

In (mod $p$) all the terms multiplied by $p$ are equal to $0$ so we're left with:

$a_p \not\equiv 0 \ [p]$

$QED$... or is it?

...let's think about it a bit more.

If you haven't noticed anything yet, there's two main indications that something is slightly off: 
Pragmatically speaking, we found an easy proof which didn't use the theorem that IMO gold medalist, Fields Medal winner Terence Tao said we would need. The more mathematical one is that our only condition for $p$ was that it be a prime smaller than $n$. This means that no matter which prime we pick, this should always hold. Take $n = 5$ and $p=2$ for example:

$\dfrac{5!}{1} + \dfrac{5!}{2} + \dfrac{5!}{3} + \dfrac{5!}{4} + \dfrac{5!}{5}$

$= 120 + 60 + 40 + 30 +20 \equiv 0 [2]$

Whoops! So what went wrong? According to the previous reasoning, the second term shouldn't be divisible by $2$. Looking under the microscope we see the problem:

$\dfrac{5!}{2} = \dfrac{2 \times 3 \times 4 \times 5}{2} = 3 \times \color{red}{4} \times 5$

There's the culprit! We got rid of the first "$2$", but not of $2 \times 2$. This means there was something wrong with our argument, but what exactly?

Looking back, the reasoning itself was not bad. The issue was not taking into account that multiples of $p$ could also be smaller than $n$ and therefore be factors of $n!$. 
The only way to make sure they aren't is to pick a prime $p$ between $\dfrac{n}{2}$ and $n$. But, is there always such a prime?? If only we could guarantee that... oh wait, we know there is at least one thanks to Bertrand's postulate!

I'm not going to write the full correct proof down since it's almost exactly the same as the one above. We just need to add the condition that $p$ is between $\dfrac{n}{2}$ and $n$, justifying it's existence using the theorem, to guarantee that there will be no uncancelled $p$'s in the $p$-th term of the sum. To be completely rigorous, we would have consider the case where $n$ is odd and therefore $\dfrac{n}{2}$ is not an integer; just apply the theorem to $n+1$ instead.

This time the proof is ours, Shinji!

         There we have it, another number theory proof done! This problem doesn't include a hint per se, but not only is Bertrand's postulate vital to the proof I found, I'm not even sure if it's possible to find a solution without using it! The wording used by Terry doesn't seem to leave much wriggling space. Feel free to show me a proof if you happen to know/find one, or if you know a reason why it would be a necessary condition!

If you're just careful, you may notice the missing piece in the proof fairly early, but I think it's easy to let oneself get carried away with the mods and cancellations. This is one of the reasons why doing a couple of examples with numbers and looking at the consequences of your own statements is very useful when solving problems. That's it for now!