17
$\begingroup$

I would like to calculate

$ d=\gcd \left({2n \choose 1}, {2n \choose 3},\cdots, {2n \choose 2n-1}\right) $

We have:

$ \sum_{k=0}^{n-1}{2n \choose 2k+1}=2^{2n-1} $

$ d=2^k, 0\leq k\leq2n-1 $

...

Any idea?

  • 0
    One might be able to use $\mathrm{ord}_p\gcd(a,b,\dots,c)=\min\{\mathrm{ord}_pa,\,\mathrm{ord}_pb,\dots, \mathrm{ord}_p c\} \tag{1}$ & $\mathrm{ord}_p{2n\choose l+2}=\mathrm{ord}_p{2n\choose l}+\mathrm{ord}_p\frac{(2n-l-1)(2n-l)}{(l+1)(l+2)} \tag{2}$ with induction to show it's $2^m\|2n$.2011-12-23

2 Answers 2

10

Let $q = 2^i$ where $2^i | 2n$ and $2^{i+1} \not|2n$. Claim: $d=q$.

First we'll show that each term ${2n \choose 2k+1}$, for $0 \leq k \leq n-1$ has $q$ as a factor. Consider,

$\begin{align*} {2n \choose 2k+1} &= \frac{(2n)(2n-1)(2n-2) \cdots (2n- [2k+1] + 1)}{(2k+1)(2k)(2k-1)\cdots(1)}\\ &= \frac{2n}{2k+1} \cdot {2n-1 \choose 2k}\\ &= \frac{2n{2n-1 \choose 2k}}{2k+1} \end{align*}$

Since $k \leq n-1$, $2k < 2n-1$, and the number ${2n-1 \choose 2k}$ is a nonzero integer. Now since ${2n \choose 2k+1}$ is an integer, we know that $2k+1$ divides the numerator. There are no factors of $2$ in $2k+1$, therefore, $q$ must survive to be a factor of ${2n \choose 2k+1}$.

Second we show that $d \leq q$. We know at least that $q$ and $d$ share the same highest power of 2, since one of the terms is ${2n \choose 1} = 2n$. Now as Andre points out in the comments, this means we're done at this point. Since OP proved that $d$ is a power of 2, we have $d=q$.

  • 1
    I must be feeling particularly dense, but didn't the OP start by proving that the $\gcd$ is a power of $2$?2011-12-25
4

Here’s a short argument for the second part of Shaun’s proof.

Suppose that $p$ is an odd prime dividing $2n$, say $2n = mp^k$, where $p\nmid m$. Then I claim that

$\begin{align*} \binom{2n}{p^k}&=\frac{(2n)!}{p^k!(2n-p^k)!}\\ &=\frac{(mp^k)!}{p^k!((m-1)p^k)!}\\ &=\frac1{p^k!}\prod_{i=0}^{p^k-1}(mp^k-i)\\ &=m\prod_{i=1}^{p^k-1}\frac{(m-1)p^k+i}i \end{align*}$

is not divisible by $p$. Clearly $p\nmid m$. If $1\le i\le p^k-1$, let $p^s$ be the highest power of $p$ dividing $(m-1)p^k+i$. Then $s and $p^s\mid i$, so the factor $\frac{(m-1)p^k+i}i$ contributes no factor of $p$ to $\dbinom{2n}{p^k}$. Thus, $p\nmid d$.

On the other hand, $d\mid 2n$, so any prime factor of $d$ must divide $2n$. It follows that $d$ has no odd prime factors and hence (by the first part of Shaun’s proof) that $d$ is the highest power of $2$ dividing $2n$.

  • 0
    @Ted: Fixed; thanks.2011-12-24