So I was playing around the other day, contemplating an application of the combination of products and sums. I took the sum $$1+2+3+\dotsc+n=\frac n2(n+1)=S_n$$ and divided it by $n!$. I realized that as $n$ approached infinity, the limit of the expression tended towards zero.
I did not find any use in this fact and kept toying around with it and then thought of using the inverse: $n!/S_n$. I noticed that the answer was a whole number $W$ for $n=1$, fraction $(F)$ for $n=2$, and to give you the pattern: $$(1,W),\,(2,F),\,(3,W),\,(4,F),\,(5,W),\,(6,F),\,(7,W).$$ The pattern ended there of $W,\,F,\,W,\,F$. By the time I reached $n=29$ I noticed that $n=28$ was $F$ but 29 was not. Because I was working by hand the fact that $29$ is a factor of $S_n$ for both $n=28,\,29$ was interesting and that's when it hit me — for all $n$ whose value for the expression was $F$, $n+1$ was an odd prime.
I emailed James Grime from the Youtube channel "Numberphile" after my teachers in school didn't wish to help, and to my great elation he proved me correct. However, I did not quite follow his explanation all the way through in proving this conjecture for all natural numbers $n$. Could someone please help and explain his work?
Hi Tomer, your observation is correct.
Your formula: $\displaystyle\frac{n!}{n(n+1)/2}=\frac{2n!}{n(n+1)} = 2\,\frac{(n-1)!}{n+1}.$
If $n+1$ is prime it is greater than any of the factors of $(n-1)!$ so $2\,\dfrac{(n-1)!}{n+1}$ will not be an integer.
If $n+1$ is not prime then can be written as a product of primes. Here's an example; $$n+1=2\times2\times2\times2\times3\times3\times3\times5=360$$
Then we want to know if $2\,\dfrac{359!}{360}$ is an integer.
Since every second number is even, and every third number is divisible by three, and every fifth number is divisible by this will comfortably cancel out.
Something like this will only not cancel out if there is a prime factor of $n+1$ that turns up so often it cannot be cancelled out completely by $(n-1)!$. That means $n+1$ has a prime factor $p$ that appears $k$ times where $k>\dfrac{n-1}p$.
The largest $k$ could be is when $n+1=p^k$. That means $$k=\frac{\log(n+1)}{\log(p)}.$$.
So if it doesn't cancel out we would have $$\frac{\log(n+1)}{\log(p)}>\frac{n-1}p.$$
Rearrange that to get $$\frac{\log(n+1)}{n-1}>\frac{\log(p)}p.$$ This implies $p>n+1$ which is nonsense ($p$ is a prime factor of $n+1$).
So $$k<\dfrac{n-1}p$$ for all prime factors of $n+1$. So all prime factors of $n+1$ are cancelled by $(n-1)!$.
James
I lose him at "Something like this will only not cancel out..." Why is $k>\dfrac{n-1}p$?
Also, how does he arrive at the conclusion of the greatest value of $k$?
If anyone has another explanation for the pattern that would also be welcome!
Here's a somewhat easier take on the proof:
What you're asking is whether $n!$ is divisible by $S_n=\frac12n(n+1)$. For starters, let's simplify things a little bit by removing that pesky $\frac12$ factor: clearly, if $n!$ is divisible by $n(n+1)$ then it's divisible by $\frac12n(n+1)$. But it turns out that the opposite is true, too — if it's divisible by $\frac12n(n+1)$ then it's also divisible by $n(n+1)$ (in other words, $\frac{n!}{S_n}$ will be an even number). We can see this by counting the number of 'factors of $2$' in $n!$: every even number $\leq n$ contributes one, then every multiple of four contributes another one, then every multiple of eight contributes another one, etc. So there are at least $\frac n2$ factors of $2$ in $n!$ — but there can only be about $\log n$ factors in either $n$ or $n+1$ (can you see why?). Since $\frac n2\gt \log n$ for all but the smallest $n$, there will always be an extra factor of two in $n!$ that hasn't been divided out.
So the question comes down to whether $\dfrac{n!}{n(n+1)}$ is a whole number or not; in other words, whether $\dfrac{(n-1)!}{(n+1)}$ is a whole number. Now, if $n+1$ is prime then it's never a factor of $(n-1)$!, so the expression can't be a whole number.
On the other hand, if $n+1$ isn't prime, then we can write $n+1=a\cdot b$ for some two numbers $a, b\gt 1$. But then $a$ and $b$ are both less than or equal to $\frac n2$, so in particular they're less than or equal to $n-1$. But this means that $a$ and $b$ are both individual factors in $(n-1)!$, so it must be evenly divisible by them. For instance, suppose $n=5$ and we break up $n+1=6=2\cdot 3$; then since $4! = 1\cdot 2\cdot 3 \cdot 4$, we can write $\dfrac{(n-1)!}{(n+1)}$ $=\dfrac{4!}{6}$ $=\dfrac{1\cdot\not2\cdot\not3\cdot 4}{\not2\cdot \not3}$ $=1\cdot 4$ - finding $2$ and $3$ in the numerator to cancel out those factors in the denominator.