Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Empirically, it seems that $d$ is the largest power of 2 dividing $2n$, although I have no idea how prove this, too. –  sos440 Dec 23 '11 at 20:20
    
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$. –  anon Dec 23 '11 at 20:58

2 Answers 2

up vote 10 down vote accepted

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$.

share|improve this answer
    
Ah, your second part finishes up the proof I was going to write but couldn't figure out. +1. –  anon Dec 23 '11 at 22:49
1  
I must be feeling particularly dense, but didn't the OP start by proving that the $\gcd$ is a power of $2$? –  André Nicolas Dec 25 '11 at 7:23

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<k$ 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$.

share|improve this answer
    
@Shaun: You’re right, but I think that I’ve fixed it now. It’s necessary to use the highest power of $p$ dividing $2n$; in your example that’s $3^2=9$, and $\binom{18}9=48620$, which is not divisible by $3$. –  Brian M. Scott Dec 24 '11 at 1:16
    
@Brian: In the second line of the chain of equalities, the $p$'s should also be $p^k$. –  Ted Dec 24 '11 at 2:24
    
@Ted: Fixed; thanks. –  Brian M. Scott Dec 24 '11 at 3:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.