, 2010

We first show that
$$N_r \le \frac{r}{2} \binom{2r}{r}$$
by proving that
$$K(n,r) = \frac{r}{2(n+r)} \binom{2n}{n} \binom{2r}{r}$$
is an integer for all $n \ge 0$ and $r \ge 1$. Notice that
$$K(0, r) = \binom{2r-1}{r} \quad \text{and} \quad K(n, 1) = \frac{1}{n+1} \binom{2n}{n},$$
the latter being a Catalan number, so $K(0, r)$ and $K(n, 1)$ are integers for all $n$ and $r$.
Next, the recurrence relation (which will be proved at the end of the solution)
$$K(n, r + 1) - K(n + 1, r) = 2K(n, 1)K(0, r)$$
shows by induction on $r$ that $K(n, r)$ is indeed an integer for all $n$ and $r$.
Suppose now that, for some $r$, $N_r < M_r = \frac{r}{2} \binom{2r}{r}$. The integer $N_r$ is the least common multiple, over all $n \ge 0$, of the denominators of the numbers $\frac{1}{n+r} \binom{2n}{n}$ when written in lowest terms. By the argument above, $M_r$ is a multiple of all these denominators. Hence $N_r$ divides $M_r$. By the definition of $N_r$, any prime $p$ that divides $M_r/N_r$ also divides $K(n, r)$ for each $n \ge 0$. Since $K(n, s+1) = K(n+1, s) + 2K(n, 1)K(0, s)$, induction on $m$ shows that $p$ divides $K(n, m)$ for all $n \ge 0$ and $m \ge r$.
Now choose $k$ such that $p^k \ge r$. Since $p$ divides $\binom{p^k}{j}$, $j = 1, 2, \dots, p^k - 1$, the identity $\binom{2n}{n} = \sum_{j=1}^n \binom{n}{j}^2$ yields $\binom{2p^k}{p^k} \equiv 2 \pmod{p}$. Therefore $p$ does not divide $\frac{1}{2}\binom{2p^k}{p^k} = K(0, p^k)$. This contradicts the preceding paragraph, so $N_r = \frac{r}{2}\binom{2r}{r}$ for all $r$.

To prove the recurrence relation, notice that
$$\binom{2m+2}{m+1} = 2\binom{2m+1}{m} = 2\frac{2m+1}{m+1}\binom{2m}{m},$$
to get
$$$$
$$\begin{align*} K(n, r + 1) - K(n + 1, r) &= \\ &\frac{r+1}{2(n+r+1)} \binom{2n}{n} \binom{2r+2}{r+1} - \frac{r}{2(n+r+1)} \binom{2n+2}{n+1} \binom{2r}{r} = \\ &\frac{1}{n+r+1} \binom{2n}{n} \binom{2r}{r} \left(2r+1 - r\frac{2n+1}{n+1}\right) = \\ &\frac{1}{n+1} \binom{2n}{n} \binom{2r}{r} = 2K(n, 1)K(0, r). \end{align*}$$