While examining the central binomial coefficients, I noticed that $(m+1)$ always seemed to divide $\binom{2m}{m}$. I would like to confirm that a short proof I have found, using Hall's theorem, is correct.
If the proof (or, at least, the result) is correct, could someone provide a combinatorial explanation for why this is true? Why would $(m+1)$ divide the number of $m$-subsets of a set of size $2m$?
Lemma: let $m,n \in \mathbb{N}$. Then, the set $\{2,...,m\}$ contains (at least) as many multiples of $n$ as $\{m+2, ..., 2m\}$.
Proof of lemma: WLOG $1 < n < m$. Let $k \in \mathbb{N}$ be the number of multiples of $n$ in $\{2,...,m\}$ i.e. $kn < m < (k+1)n$. If $(k+1)n = m+1$, then $$\{(k+1)n,...,(2k+1)n\} \subseteq \{(m+2),...2m\}$$ since $kn + (k+1)n < 2m+1$.
Otherwise, $\{(k+1)n,...,2kn\} \subseteq \{(m+2),...2m\}$. $\square$
Proposition: $\forall m \in \mathbb{N}, (m+1) | \binom{2m}{m}$.
Proof of proposition:
For $n \in \mathbb{N}$, let $v_p(n)$ denote the largest power of $p$ dividing $n$. Let $p$ be a (fixed) prime dividing $m$.
Construct a bipartite graph $G$ with $V = X \cup Y$, where $X = \{2, ..., m\}$, $Y = \{(m+2), ..., 2m\}$ and $x \sim y$ if and only if $v_p(x) \le v_p(y)$ ($x\in X, y \in Y$).
We show that $G$ satisifies Hall's condition i.e. $|N(A)| \ge |A|, \; \forall A \subseteq X$.
Let $A \subseteq X$, and let: $$v = \min_{x \in A} v_p(x)$$
Then, note that $$N(A) = \Big\{ y \in \{(m+2), ..., 2m\} \; : \; p^v | y \Big\}$$ while
$$A \subseteq \Big\{ x \in \{2, ..., m\} \; : \; p^v | x \Big\}$$
By the lemma applied to $n = p^v$, $|N(A)| \ge |A|$. Hence, by Hall's theorem, there exists a matching. By pairing the numbers in this way, we deduce that:
$$v_p\Big( (m+2) \cdots (2m) \Big) - v_p \Big( (2) \cdots (m) \Big) \ge 0$$
Hence, $$p^k \Big| (m+1) \implies p^k \Bigg| \binom{2m}{m} = (m+1)\frac{(m+2) \cdots (2m)}{(2) \cdots (m)} $$
But $p$ was arbitrary so we deduce that $(m+1) \Big| \binom{2m}{m}$. $\square$
Thanks to Michael Lugo who has identified the sequence $C_m = \frac{1}{m+1} \binom{2m}{m}$ as the Catalan numbers. There is a much easier proof that $C_m \in \mathbb{N}$; note that $C_m = \binom{2m}{m} - \binom{2m}{m+1}$. I am still interested to know if the proof above is correct.
As Michael Lugo says, the quotient is a Catalan number. You can write down a direct combinatorial proof that the quotient is an integer (without any further binomial coefficient manipulations) using a result called Raney's lemma. Here you can see the result stated (without being named because I forgot the name for awhile) and used to prove the more general fact that $(k-1)m + 1$ divides ${km \choose m}$ (the quotient is a generalization of the Catalan numbers).