9
$\begingroup$

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

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

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

$\endgroup$
2
  • 7
    $\begingroup$ An easy proof that $C_n$ is an integer is that $C_n = \binom{2n}{n} - \binom{2n}{n-1}$. $\endgroup$ Jan 26 '18 at 22:36
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 26 '18 at 22:38
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Simply expand and seperate the factorial in the numerator.

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

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – Joffan
    Jan 29 '18 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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