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

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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)} $$

Answer 5

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.

Answer 6

Simply expand and seperate the factorial in the numerator.

Clearly, is a factor in the numerator. Therefore, is indeed divisible by .