Greatest common divisior of $2^n$ and $\binom{2n}{n}$

Question

Find the greatest common divisior of $2^n$ and $\binom{2n}{n}$. As I assume we have to use identities

$\sum_{k=0}^n\binom{n}{k} = 2^{n}$ and $\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{2n}{n}$.

But I cannot find the connection between $\gcd((a_1+...+a_n),(a_1^2+...+a_n^2))$? Any hints how do we find such thing?

Answer 1

By Legendre's formula, $v_p(k!)=\displaystyle\sum_{i=1}^{\infty} {[\frac{k}{p^i}]}.$The power of 2 in the binomial is therefore $v_2((2n)!)-2v_2(n!)=n-\displaystyle\sum_{i=1}^{\infty} {[\frac{n}{2^i}]}=A<n.$So the gcd is $2^A$ and I don't think A can be simplified.

Answer 2

If we write

$${2n\choose n}=\frac{(2n)!}{n!\cdot n!}$$

then can you work out how many factors $2$ are in ${2n\choose n}$?

Hint:

Note that $\frac{(2n)!}{n!\cdot n!}=\frac{(n+1)\cdot (n+2)\cdots (2n)}{1\cdot 2\cdots n}$. How many factors $2$ do the numbers $1,2,\cdots,n$ have compared to $(n+1),(n+2),\cdots (2n)$?

Answer 3

Kummer's theorem gives you the following answer. Write $n=\sum_{i=0}^kb_i2^i$ in base two, i.e. $b_i\in\{0,1\}$ for all $i$.

Then do grade school addition of $n+n$. Let the number of carries be $\ell$. Then, according to Kummer, $$ \gcd(2^n,\binom{2n}n)=2^\ell. $$ Kummer's theorem follows in a relatively straightforward manner from Legendre's formula mentioned by Will Jagy.

---

For example, when $n=13=1101_2$, you do the addition $$ \begin{array}{r}1101\\1101\\ \hline11010\end{array}. $$ You see that there were carries into positions $2^1,2^3$ and $2^4$. Three carries total, so we get that $\binom {26}{13}$ is divisible by $8$ but not by $16$.