Prove: $\forall$ $n\in \mathbb N, (2^n)!$ is divisible by $2^{(2^n)-1}$ and is not divisible by $2^{2^n}$ 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.
 A: 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}$
A: 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$
A: 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)$.)
A: 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.$$
