Can someone provide the intuitive explanation of the following statement?

Question

Using Legendre's formula we can obtain that $$v_2(n!)=\left\lfloor\frac{n}{2}\right\rfloor+v_2\left(\frac{n}{2}!\right)$$ where $v_2$ is the greatest power of $2$ that divides some $x!$. However I can't wrap my head around this. I was thinking that if you have $n!$ then $2n!$ has $n$ more terms than $n!$ and thus for every other term greater than $n$ you have a multiple of $2$, however in those terms there will also be multiples of powers of two so why is that not accounted for in the formula?

Answer 1

Consider numbers from $1,2,...,n$. Multiples of $2$ have at least one $2$ in them. We have $\lfloor \frac{n}{2}\rfloor$ of $1,2,...,n$, that are a multiples of $2$. Multiples of $4$ have at least two $2$ in them. There are $\lfloor \frac{n}{2^2}\rfloor$ of them in $1,2,...,n$. But, one of the $2$s was counted, when considering multiples of $2$. So we have a total of $\lfloor \frac{n}{2}\rfloor+\lfloor \frac{n}{2^2}\rfloor$ $2$s, until this step. With the same reasoning, we get the following formula for the number of $2$s, in $n!$

$v_2(n!)=\lfloor \frac{n}{2}\rfloor+\lfloor \frac{n}{2^2}\rfloor+...+\lfloor \frac{n}{2^k}\rfloor$

Where $k\leq log_{2}^{n}$.

writing the same formula for $(\frac{n}{2})!$, gives

$v_2((\frac{n}{2})!)=\lfloor \frac{\frac{n}{2}}{2}\rfloor+\lfloor \frac{\frac{n}{2}}{2^2}\rfloor+...+\lfloor \frac{\frac{n}{2}}{2^{k-1}}\rfloor=\lfloor \frac{n}{2^2}\rfloor+\lfloor \frac{n}{2^3}\rfloor+...+\lfloor \frac{n}{2^{k}}\rfloor$

Now, you only need to add $\lfloor \frac{n}{2}\rfloor$ to the second one to get the first one.

Hope it helps.