how prove $n! \mid \prod_{k=0}^{n-1}(2^n-2^k) :\forall n \in \mathbb N$?

Solution 1:

This is the nice, scenic route Qiaochu mentions in the comments. It is not entirely obvious to me that this is not the "intended" answer for this, as it is tagged as a contest problem.

Let ${\bf F}_q$ denote the (unique) finite field with exactly $q=p^s$ elements ($p$ a prime number). The invertible linear maps on the vector space ${\bf F}_q^n$ are in bijection with the ordered $n$-tuples of linearly independent column vectors from ${\bf F}_q^n$. The number of these (so, in effect the size of ${\rm GL}_n({\bf F}_q)$) may be counted combinatorially, directly.

For the first vector, we can choose anything that is nonzero, which makes for $q^n-1$ possible choices. For the second, we can choose anything that is not in the linear span of the first, and the linear span of the first vector is a one-dimensional subspace (so in particular it has $q$ elements), hence there are $q^n-q$ possible choices for the second vector. We may continue in this way for

$$|{\rm GL}_n({\bf F}_q)|=(q^n-1)(q^n-q)(q^n-q^2)\cdots(q^n-q^{n-1})=\prod_{k=0}^{n-1}(q^n-q^k).$$

Another way of expressing this is as $(q-1)^nq^{(n-1)n/2}[n]_q!$ using the $q$-factorial.

The symmetric group $S_n$ is realized directly as a subgroup of ${\rm GL}_n({\bf F}_q)$ via permutation matrices, and so by Lagrange's theorem it follows that for any prime power $q$,

$$n!\mid\prod_{k=0}^{n-1}(q^n-q^k).$$

This case is in particular $q=2$.

A mostly equivalent line of reasoning is seen through group actions in Thomas' comment: the symmetric group $S_n$ acts on the set of $n$-tuples of linearly independent vectors of ${\bf F}_q^n$ through permutating the coordinates; in none of these $n$-tuples are any two coordinates the same, so every stabilizer is trivial, so every orbit has size $|S_n|=n!$ (by orbit-stabilizer), so that the whole space of $n$-tuples under consideration has size a multiple of $n!$ as it is a disjoint union of orbits of size $n!$.

This is pretty much letting the subgroup $S_n$ act on ${\rm GL}_n({\bf F}_q)$ via right-multiplication by inverses.

Solution 2:

A direct proof would use remembering how we proved that the highest power of a prime $p$ that divides $n!$ is:

$$\sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^k}\right\rfloor$$

The same logic can show that the highest power of an odd prime that divides the right side is at least:

$$\sum_{k=1}^\infty\left\lfloor \frac{n}{p^{k}-p^{k-1}}\right\rfloor$$

Essentially, this is because $p^k$ divides $2^m-1$ when $m$ is a multiple of $p^k-p^{k-1}=\phi(p^k)$.

Since $p^k-p^{k-1} < p^k$, each term is as least as big as the associated term from the sum for $n!$

Then you just have to deal with the case $p=2$.