Let $n\ge0$. What is the power of $2$ in the prime factorization of $(2^n)!\,$? Prove that the value is correct.
So far I've conjectured the value to be $2^n - 1$. This is true for $n=0,1,2,3,4$. Then I decided to use induction to prove the statement.
Base case: $(2\cdot0)!=1\cdot2^0=2^0-1$
IH: Assume for some $(2^n)!$, the power of $2$ in the prime factorization is $2^n-1$.
IC: Then it must be true for $(2^{n+1})!=(2\cdot2^n)!$
Am I using the wrong method?
Can anyone provide a proof?
On
Hint:
Just count the 2s.
$(2^5)!=32!=32\times31\times\cdots\times2\times1$
Half of these are divisible by 2.
One fourth are divisible by 4 (so have one more factor of 2 than those divisible only by 4).
One eighth are divisible by 8 (so have one more factor of 2 than those divisible only by 2 and 4).
In general, the exponent of a prime $p$ in the decomposition of $m!$
is $v_m(p)=\lfloor\frac{m}{p}\rfloor +\lfloor\frac{m}{p^2}\rfloor+\lfloor\frac{m}{p^3}\rfloor+\cdots$
For the case $m=2^n$ and $p=2$ we have $$v_{2^n}(2)=\lfloor\frac{2^n}{2}\rfloor+\lfloor\frac{2^n}{2^2}\rfloor+\cdots=2^{n-1}+2^{n-2}+\cdots +1=2^n-1$$
Your conjecture is correct.