Prove $n{2n\choose n}=(n+1){2n\choose n-1}$ and $(n+1)|{2n\choose n}$

Question

a) Show that $n \cdot {2n\choose n}=(n+1){2n\choose n-1}$ for all $n \in \mathbb{N}$.

b) Show that $(n+1)\mid{2n\choose n}$ for all $n \in \mathbb{N}$.

---

Prove for a) $$n\cdot {2n\choose n} =n\cdot {(2n)!\over n!\cdot n!} = {(2n)!\over n!\cdot (n-1)!}$$ and

$$(n+1)\cdot {2n\choose n-1} =(n+1)\cdot {(2n)!\over (n-1)!\cdot (n+1)!} = {(2n)!\over (n-1)!\cdot n!}$$

We can use it now for b):

Since: $$n\cdot {2n\choose n}=(n+1)\cdot {2n\choose n-1}\implies n+1 \mid n\cdot {2n\choose n}$$

But since $\gcd(n,n+1)=1$ we must have $n+1 \mid {2n\choose n}$.

Alternative proof, more combinatorial?

Answer 1

The quotients, $C_n=\frac 1{n+1}\binom {2n}n$ are the Catalan Numbers.

It's not hard to show that $$C_n=\binom {2n}n - \binom {2n}{n+1}$$ which shows integrality efficiently (if a bit unintuitively).

Somewhat more intuitive is the recursive definition: $$C_0=1 \quad C_{n+1}=\sum_{i=0}^{n}C_iC_{n-i}$$

Which also demonstrates integrality. That relation has well known combinatorial interpretations, many of which are discussed in the link mentioned above.

Answer 2

For part a, imagine you have $2n$ people, and want to form a committee of $n$ people. Within the committee, you want there to be one committee leader and $n-1$ regular members.

We can calculate the number of such committees by first selecting the $n$ out of $2n$ people who will be in the committee, and then choosing one of those $n$ people to be the leader. Doing this gives us $n \binom{2n}{n}$, which is the left hand side of the equation.

However, it would be equally valid to first chose the $n-1$ regular members, and then chose the leader from the remaining $n+1$ people. Doing this gives us $(n+1) \binom{2n}{n-1}$, which is the right hand side of the equation.

Since the quantities on the left hand side and the right hand side are answers to the same combinatorial question, they must be equivalent. Thus $n \binom{2n}{n} = (n+1) \binom{2n}{n-1}$.

Answer 3

A combinatorial interpretation of $\binom{2n}n$ is equal to the number ways to walk from $(0,0)$ to $(n,n)$ in the 2D plane, where each step is either one unit up or one unit right. To prove that $n+1$ divides $\binom{2n}n$, it suffices to partition these walks into $n+1$ equal groups.

Each walk will spend some amount of time above the diagonal $y=x$; the length of the path above this line is an even number between $0$ and $2n$. It turns out that for each $k=0,1,2\dots, n$, letting $w_k$ equal number of paths from $(0,0)$ to $(n,n)$ whose length above $y=x$ is $2k$, then $w_0=w_1=\dots=w_n$. The argument proving this is paraphrased from Wikipedia:

If we are given a monotonic path whose length above the diagonal is $2k>0$, then we may apply the following algorithm to construct a new path whose length above the diagonal $2(k-1)$:

• Starting from the bottom left, follow the path until it first travels above the diagonal.
• Continue to follow the path until it touches the diagonal again. Denote by $X$ the first such edge that is reached.
• Swap the portion of the path occurring before X with the portion occurring after $X$.

The following example should make this clearer. In the image below, the black dot indicates the point where the path first crosses the diagonal. The black edge is X, and we swap the red portion with the green portion to make a new path, shown in the second diagram.

It is also not difficult to see that this process is reversible: given any path $P$ whose length above the diagonal is less than $2n$, there is exactly one path which yields $P$ when the algorithm is applied to it. Indeed, the (black) edge $X$, which originally was the first horizontal step ending on the diagonal, has become the last horizontal step starting on the diagonal.

This proves that $w_k=w_{k-1}$ for all $k=1,\dots,n$.