6
$\begingroup$

I want to show that $n+1$ is a divisor of $\displaystyle\binom{2n} {n}$, for all $n\in\mathbb{N}.$

I have tried to show it by induction and Pascal's rule but it did not worked out.

I would appreciate some help.

  • 0
    @spohreis regarding my comment above, I might be wrong. The numerator has a factor $2n(2n-2)(2n-4)\cdots$ but the product doesn't end with $2$. I have to write it down.2012-08-31

4 Answers 4

19

From the Wikipedia page for Catalan numbers: http://en.wikipedia.org/wiki/Catalan_number

Note that $\binom {2n}{n+1} = \frac{(2n)!}{(n-1)!(n+1)!} = \frac{n}{n+1} \frac{(2n)!}{n!n!} = \frac{n}{n+1}\binom{2n}{n}$

So $\frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}$ is an integer.

7

$\frac{n}{n+1}\binom{2n} {n} = \binom{2n} {n+1} \textrm{ is an integer.}$

6

Let $x=\frac{1}{n+1}{2n\choose n}\implies x=\frac{(n+1)-n}{n+1}{2n\choose n}$ $ \implies x={2n\choose n}-{2n\choose n+1}$.

Since $n\choose k$ is always an integer $\implies x$ is an integer $\implies (n+1)$ divides ${2n\choose n}$

4

Hint $\ $ Put $\rm\:k = 2n\:$ in the following

Theorem $\displaystyle \rm\ \ (n\!+\!1,k\!+\!1) = 1\:\Rightarrow\: n\!+\!1\:\bigg|\:{k\choose n}$

Proof $\displaystyle\rm\ \ \ (n\!+\!1){k\choose n\!+\!1}\, =\, \frac{(n\!+\!1)\,k!}{(n\!+\!1)! \,(k\!-\!n\!-\!1)!}\, =\, \frac{(k\!-\!n)\,k!}{n!\, (k\!-\!n)!} \,=\, (k\!-\!n){k\choose n}$

so the result follows from Euclid's Lemma, since $\rm\:(n\!+\!1,k\!-\!n) = (n\!+\!1,k\!+\!1) = 1.\ \ $ QED