Show that $2n\choose n$ is divisible by $2n-1$

I have found many questions asking to prove $2n\choose n$ is divisible $2$, but I also observed by trying the first few "$n$" that $2n\choose n$ is divisible by $2n-1$.

It sure seems true when $2n-1$ is prime, but is it true in general for all $n$?

• Hint: math induction on $n$. Jan 26 '18 at 22:25
• Looking at the binomial coefficient definition according to the binomial theorem shows its definitely true if 2n-1 is prime Jan 26 '18 at 22:26

Catalan's numbers $\{ C_n\}_{n \ge 1}$ are defined by $$C_n=\frac{1}{n+1}\binom{2n}{n}$$ these are known to be integers for all $n \ge 1$.

Now, for $n \ge 2$, $$\binom{2n}{n}=\frac{2n \cdot (2n-1) \cdot ((2n-2)!)}{n \cdot ((n-1)!) \cdot n \cdot ((n-1)!)} = 2 \cdot \frac{1}{n} \binom{2n-2}{n-1} \cdot (2n-1) = 2C_{n-1} \cdot (2n-1)$$ This shows that $(2n-1)$ always divides $\binom{2n}{n}$, and the quotient is $2C_{n-1}$.

• An easy proof that $C_n$ is an integer is that $C_n = \binom{2n}{n} - \binom{2n}{n-1}$. Jan 26 '18 at 22:36
• And I almost put a comment "Catalan Numbers related but not the same" and pulled it because I was sure there would be a link ... great answer. Jan 26 '18 at 22:38

Since $$\binom{2n}{n}=2\frac{2n-1}n\binom{2n-2}{n-1}$$ we get $$2n\binom{2n}{n}=4(2n-1)\binom{2n-2}{n-1}$$ and therefore, $$\bbox[5px,border:2px solid #C0A000]{\binom{2n}{n}=\left[4\binom{2n-2}{n-1}-\binom{2n}{n}\right](2n-1)}$$

The case when $2n-1$ is prime is trivial. This is true, as we know that $\binom{2n}{n}$ is integer, so then we have that

$$\binom{2n}{n} = \frac{(2n)!}{(n!)^2} = \frac{(n+1) \cdots (2n-1)\cdot 2n}{n!}$$

and $2n-1$ doesn't appear in the prime factorization in the denominator.

Now assume that $2n-1$ is composite and $p$ is a prime divisor of it. Obviously we must have $p \le \frac{2n-1}{2} \implies p < n$. Then if $p \mid m \le n$ we get that $m$ contributes in the prime factorization of $(n!)^2$ twice, but similarly $m$ and $2m$ contribute by at least the same amount in $(2n)!$. Obviously $2n-1$ can't be equal to $m$ ($m \le n$) nor to $2m$ ($2n-1$ is odd), so the numerator has at least one more contributor of $p$. So we get that $p^k \mid \binom{2n}{n}$, where $k$ is the highest power of $p$ dividing $2n-1$. This is true for every prime divisor of $2n-1$, so we get

$$2n-1 \mid \binom{2n}{n}$$

Hence the proof.

$$\frac{\binom{2n-1}{n-1}}{2n-1}\in\mathbb N.$$ See here: To prove $n\binom{2n-1}{n-1}$ is divisible by $n(2n-1)$

Thus, $$\frac{\binom{2n}{n}}{2n-1}=2\cdot\frac{\binom{2n-1}{n-1}}{2n-1}\in\mathbb N$$

Note that $\dbinom{2n}{n}$ is an integer. Note also that $1$ divides $\binom 21$ and assume $n>1$ hereafter.

\begin{align} \dbinom{2n}{n} &= \dfrac{2n!}{n!\cdot n!} \\ &= \dfrac{2n\cdot (2n-1)\cdots (n+1)}{n\cdot (n-1)\cdots 1}\\ &= \dfrac{(2n)(2n-1)}{n\cdot n}\dbinom{2(n-1)}{n-1}\\ &= 2\dfrac{2n-1}{n}\dbinom{2(n-1)}{n-1}\\ \end{align}

Now $\gcd(2n-1,n)=1$ so $n$ must divide $2\dbinom{2(n-1)}{n-1}$, that is, $2\dbinom{2(n-1)}{n-1}= kn$ for some integer $k$.

Then $\dbinom{2n}{n} = k(2n-1)$ as required.

Simply expand $\binom{2n}{n}$ and seperate the factorial in the numerator.

$\binom{2n}{n}=\frac{2n!}{n!*(2n-n)!}=&space;\frac{(2n)(2n-1)(2n-2)!}{n!*(2n-n)!}$

Clearly, $2n-1$ is a factor in the numerator. Therefore, $\binom{2n}{n}$ is indeed divisible by $2n-1$.

• This leaves open whether there are sufficient divisors of $2n{-}1$ in the denominator to mean that the result is not divisible by $2n{-}1$. Jan 29 '18 at 16:35