For a positive integer $s$, denote with $v_2(s)$ the maximum power of $2$ that divides $s$. Prove that for any positive integer $m$ that: $$v_2\left(\prod_{n=1}^{2^m}\binom{2n}{n}\right)=m2^{m-1}+1.$$ (FYROM)
Problem
Source: Balkan BMO Shortlist 2015 N5
Tags: number theory, maximum, power of 2, divides, Product, IMO Shortlist
05.08.2019 19:41
Lemma. $\nu_2\left( \dbinom{2n}{n}\right)$ is equal to the number of $1$'s in the binary represantation of $n$. Proof: This is a direct application of Kummer's Theorem. Now, $$\nu_2\left(\prod_{n=1}^{2^m}\binom{2n}{n}\right)=\sum_{n=1}^{2^m} \nu_2\left(\binom{2n}{n}\right)=1+\sum_{k=1}^{m} k\dbinom{m}{k}=m2^{m-1}+1$$. because there is only one carry when $n=2^m$ and $k\dbinom{m}{k}$ when $n<2m$ and $n$ has $k$ ones in its binary representation. $\blacksquare$
05.08.2019 20:03
$\nu_2 \dbinom{2n}{n} = 2n-S_2(2n)-2(n-S_2(n))=S_2(n)$ - hence $v_2\left(\prod_{n=1}^{2^m}\binom{2n}{n}\right)=S_2(1)+S_2(2)+...+S_2(2^m)$ - but this is just the total number of $1s$ you'll get if you list down the first $2^m-1$ numbers in binary(and $+1$ for the $2^{m^{th}}$)- now, as there are $2^{m}-1$ numbers, and $m$ digits, we get there are in total $2^m \cdot m$ digits- due to symmetry, as we've listed down every number with $m$ digits, number of $0s$=number of $1s$ $=>$ total number of $1s$= $1+ m \cdot 2^m \cdot \frac{1}2=1+m2^{m-1}$. QED.
04.04.2020 21:02
23.08.2020 05:02
Here's another proof of $\nu_2(\binom{2n}{n})=S_2(n)$: We have that $\lfloor\frac{2n}{2^k}\rfloor=\lfloor\frac{n}{2^{k-1}}\rfloor$ in base 2 is the first $\lfloor \log_2(n)\rfloor-k+2$ digits in n's binary representation and similarly $\lfloor\frac{n}{2^k}\rfloor$ is the first $\lfloor \log_2(n)\rfloor-k+1$ digits. Twice the latter subtracted from the former gives the $\lfloor \log_2(n)\rfloor-k+2$th digit counting from the left; summing this over all $k$, we can cover every digit of $n$'s binary representation. (The floors evaluated here are from Legendre's formula)