To prove $n\binom{2n-1}{n-1}$ is divisible by $n(2n-1)$

Because $$\frac{\binom{2n-1}{n-1}}{2n-1}=\frac{\binom{2n-2}{n-1}}{n}$$ and $gcd(2n-1,n)=1$.

1)

you need to know that $$k\binom{n}{k}=n\binom{n-1}{k-1}$$ This could be proven combinatoricaly.

Question in how many ways is is possible to choose a committeeof k student of n with one leader coming from the k chosen.

Left Side: $\binom{n}{k}$ of ways choosing a set of k, and k possibilities of choosing a leader.

Right Side: choose a leader out of n, the choose the k-1 students$\binom{n-1}{k-1}$

This actually a (combinatorial) proof. By The book: "The Proofs that counts."

Since we have this now lets apply to the problem and we get

2)$$n\binom{2n-1}{n-1}=n \frac{n-1}{n-1}\binom{2n-1}{n-1}=n \frac{n-1}{n-1}(2n-1)\binom{2n-2}{n-2}$$

3)

Since you have the Identity 2) you win! :) Since this is now obviously is divisible by n(2n-1)!

ps. dont write you win in the proof!