Why is $ a_n= \frac{(2n)!-2(n!)^2}{(n!)^2n} $ a natural number when $n$ is a prime number?

Question

Why is $ a_n= \dfrac{(2n)!-2(n!)^2}{(n!)^2n} $ a natural number when $n$ is a prime number?

I have tried $ a_n= \dfrac{(\prod_{i=n+1}^{2n}i)-2(n!)}{(n!)n} $. But now i stuck.

Answer 1

That is a consequence of Wolstenholme's theorem $$ \binom{2p-1}{p-1}\equiv 1\pmod{p^3},\qquad \binom{2p}{p}\equiv 2\pmod{p} $$ holding for any prime $p>3$.

Answer 2

$$\frac{(2n)!-2(n!)^2}{(n!)^2 n} = \frac{1}{n} \left( \frac{(2n)!}{(n!)^2} - 2 \right) = \frac{1}{n} \left( \binom{2 n}{n} - 2 \right).$$

So one has to prove that if $n$ is prime, then $$ \binom{2 n}{n} \equiv 2 \pmod{n}. $$ This is a very special case of Lucas's Theorem. In this particular instance, just compute in $\mathbb{Z}/ n\mathbb{Z} [x]$ $$ \sum_{i=0}^{2n} \binom{2n}{i} x^{i} = (1 + x)^{2n} = (1 + x^{n})^{2} = 1 + 2 x^{n} + x^{2 n} $$ and compare the coefficients of $x^{n}$.

Answer 3

This simplifies to $\big(\binom{2n}n-2\big)/n$.

Now $\binom{2n}{n}$ is the number of ways of choosing $n$ nuumbers from $1,...,2n$. If we choose $r$ from $1,...,n$ we have to choose $n-r$ from $n+1,...,2n$, and so this equals $\sum_{r=0}^n\binom{n}{r}\binom{n}{n-r}$.

So $\binom{2n}n-2=\sum_{r=1}^{n-1}\binom{n}{r}\binom{n}{n-r}$ (the two terms we've missed out are both $1$), and since $n$ is prime it is easy to check that all terms on the RHS are divisible by $n$.

Answer 4

Count the number of ways to arrange $n$ red and $n$ green balls into a sequence of $2n$ balls; there are $2n\choose n$ such arrangements. Say that two such arrangements are equivalent, if they can be transformed into another by a cyclic permutaion of the first $n$ balls. If $n$ is prime, we have two cases:

• First all red, then all green balls or vice versa. These arrangements are only equivalent to themselves.
• At least one green and one red ball in the first half. Then all $n$ cyclic rearrangements are different (the first repetition must occur at a divisor of $n$)

Thus the $2n\choose n$ arrangements are partitioned into $2$ arrangements of the first kind and some integer $k$ number of equivalence classes containing (if $n$ is prime) $n$ elements each. Hence $${2n\choose n}=2+kn, $$ or solved for $k$, $$k=\frac{{2n\choose n}-2}n=\frac{\frac{(2n)!}{n!n!}-2}{n}=\frac{(2n)!-2n!^2}{n!^2n}=a_n $$

Answer 5

It is clear that $n!^2$ divides each term in the numerator (the first term because $\binom{2n}{n}$ is an integer). That takes care of all prime factors of the denominator that are smaller than $n$. So we just need to prove $$ n^3 \mid (2n)!-2(n!)^2 $$ We can divide out two of the $n$s easily enough, so what remains to prove is $$ \tag{*}n \mid 2(2n-1)!/n - 2(n-1)!^2 $$ However, $$(2n-1)!/n \equiv (n-1)!^2 \pmod n$$ so $\text{(*)}$ is inded true.