Prove: $\forall$ $n\in \mathbb N, (2^n)!$ is divisible by $2^{(2^n)-1}$ and is not divisible by $2^{2^n}$

Question

I assume induction must be used, but I'm having trouble thinking on how to use it when dealing with divisibility when there's no clear, useful way of factorizing the numbers.

Answer 1

Let $v_p(m)$ be the largest power of the prime $p$ dividing $m$.

Legendre’s formula states: $v_p(m!)=\sum\limits_{i=1}^{\infty}\lfloor\frac{m}{p^{i}}\rfloor$.

Letting $p=2$ and $m=2^n$ we get:

$v_2(2^n!)=\sum\limits_{i=1}^{\infty}\lfloor\frac{2^n}{2^{i}}\rfloor=2^{n-1}+2^{n-2}+\dots+2+1=2^{n}-1$

Answer 2

We need to count factors 2 in the number $(2^n)!$.

There are 2^{n-1} numbers that are divisible by 2 less then or equal to $2^n$,

There are 2^{n-2} numbers that are divisible by 4 less then or equal to $2^n$,

There are 2^{n-3} numbers that are divisible by 8 less then or equal to $2^n$,

....

There are 2 numbers that are divisible by $2^{n-1}$ less then or equal to $2^n$ and finally

There is exactly 1 number that are divisible by $2^n$ less then or equal to $2^n$ ($2^n$ itself).

When you add all this together $(2^n)!$ is divisible by $2^{1+ 2+ \ldots 2^{n-1}} = 2^{2^n-1}$

Answer 3

No need to have a sledgehammer to crack a nut: a simple induction proof will do. We have to show $\;v_2\bigl((2^n)!\bigr)=2^n-1$.

For $n=0$, it is trivial since it means $\;v_2(1!)=2^0-1=0$.

Now suppose, by induction hypothesis, that $\;v_2\bigl((2^n)!\bigr)=2^n-1$, and let us prove that $\;v_2\bigl((2^{n+1})!\bigr)=2^{n+1}-1$.

We'll split $$(2^{n+1})!=(1\cdot 2\cdot 3\dotsm 2^n)\cdot(2^n+1)(2^n+2)(2^n+3)\dotsm(2^n+2^n-1)\cdot(2^n+2^n).$$ Note that, for any $k<2^n$, $\;v_2(2^n+k)=v_2(k)$, and that $\;v_2(2^n+2^n)=v_2(2\cdot2^n)=v_2(2^n)+1$, whence \begin{align*}v_2\bigl((2^n+1)&(2^n+2)(2^n+3)\dotsm(2^n+2^n-1)\cdot(2^n+2^n)\bigr) \\=v_2&(1\cdot 2\cdot 3\dotsm 2^n)+1=v_2\bigl((2^n)!\bigr)+1. \end{align*} So we have $$v_2\bigl((2^{n+1})!\bigr)=2v_2\bigl((2^n)!\bigr)+1=2(2^n-1)+1=2^{n+1}-1.$$

Answer 4

A Combinatorial Approach:

For each nonnegative integer $n$, show that $a_n:=\frac{\left(2^n\right)!}{2^{2^n-1}}$ is the number of ways to label the leaves of a complete binary tree $T_n$ with $2^n$ leaves by $1$, $2$, $\ldots$, $2^n$. (Two labelings are considered to be the same if there is a graph automorphism $f$ on $T_n$ such that, for $i=1,2,\ldots,2^n$, $f$ sends the leaf with label $i$ in one labeling to the leaf with the same label in the other labeling.) Prove that $a_n$ is odd for all $n\in\mathbb{N}_0$ by showing that $\frac{a_n}{a_{n-1}}$ is an odd integer for $n=1,2,3,\ldots$, whereas $a_0=1$. (This second part can be proven combinatorially as well, because $\frac{a_n}{a_{n-1}}$ for $n\in\mathbb{N}$ is the number of ways to partition $\left\{1,2,\ldots,2^n\right\}$ into $2^{n-1}$ subsets each of which has $2$ elements. It follows immediately that $\frac{a_n}{a_{n-1}}=\left(2^n-1\right)!!=\prod_{i=1}^{2^{n-1}}\,(2i-1)$.)