To prove $n\binom{2n-1}{n-1}$ is divisible by $n(2n-1)$ 
Prove that for natural $n \ge 2$ $$n\binom{2n-1}{n-1}$$ is divisible by $$n(2n-1)$$

We have $$n\binom{2n-1}{n-1}=n \frac{(2n-1)!}{(n-1)! \:n!}=n(2n-1)\frac{(2n-2)!}{(n-1)! \:n!}$$
Now it suffices to prove $\frac{(2n-2)!}{(n-1)! \:n!}$ is an integer
Now
$$\frac{(2n-2)!}{(n-1)! \:n!}= \frac{1 \times 2 \times 3 \cdots \times (n-1) \times (n-2) \times (n-3) \cdots  \times (2n-4) \times (2n-3) \times (2n-2)}{(n-1)! \: n!}$$
hence
$$\frac{(2n-2)!}{(n-1)! \:n!}=\frac{(n-2) \times (n-3) \cdots (2n-2)}{n!}$$
any clue to prove this is always an integer?
 A: 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!
A: Because $$\frac{\binom{2n-1}{n-1}}{2n-1}=\frac{\binom{2n-2}{n-1}}{n}$$ and
$gcd(2n-1,n)=1$.
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\i}{\mathrm{i}} \newcommand{\text}[1]{\mathrm{#1}} \newcommand{\root}[2][]{^{#2}\sqrt[#1]} \newcommand{\derivative}[3]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\abs}[1]{\left\vert\,{#1}\,\right\vert}\newcommand{\x}[0]{\times}\newcommand{\summ}[3]{\sum^{#2}_{#1}#3}\newcommand{\s}[0]{\space}$
$$\frac{(2n-2)!}{(n-1)! \:n!}$$
$$\frac{(2n-2)(2n-3)(2n-4)...(n+1)(n!)}{(n-1)!(n!) }$$
$$\frac{(2n-2)(2n-3)(2n-4)...(n+1)}{(n-1)! }$$
Now prove by induction,
Step 1) It should be true for any $n$ (Will skip this part, it is too easy)
Step 2) Prove that it is true for $n\dashrightarrow n+1$
(Put $n+1$ where $n$ is.)
And expand:
$$\frac{(2n)(2n-1)(2n-2)(2n-3)(2n-4)...(n+6)(n+5)(n+4)(n+3)(n+2)}{(n)(n-1)(n-2)...(3)(2) }$$
Simplify the left
$$\frac{(2)(2n-1)(2)(2n-3)(2)...(n+6)(n+5)(n+4)(n+3)(n+2)}{(1)(1)(1)...(3)(2) }$$
Now think about it for a minute: $n-a$ can be written as $b$, where $\forall a,b \in \text{Natural\s Numbers\s and\s \forall a < n}$
If all "$n-a$"s can be simplified, then "$b$" must be able to be simplified too.
Problem solved. If you think it's not, think again.
A: A combinatorial proof: observe that $n\binom{2n-1}{n-1}$ is the number of $(2n-1)$-letter words that can be made from one copy of the letter A, $n-1$ copies of the letter B, and $n-1$ copies of the letter C.  We partition the set $S$ of such words into $(2n-1)n$ parts of equal size using the following rule: let $w$ be a word and let $x$ be the word obtained from $w$ by replacing A with B.  Since $x$ is a $(2n-1)$-letter word with $n$ Bs, and since $2n-1$ and $n$ are relatively prime, there is a unique cyclic permutation, $p_1$, of $x$ that results in a lexicographically minimal word.  Now let $u$ be the $n$-letter subword of $w$ obtained by applying $p_1$ to $w$ and then omitting all Cs.  Since $u$ is an $n$-letter word with one A, there is a unique cyclic permutation, $p_2$, of $u$ that results in a lexicographically minimal word.  Now partition $S$ according to the permutation pair $(p_1,p_2)$.
As an example, consider $n=3$.
$$
\begin{array}{l|ccc}
p_1\backslash p_2 & 0 & 1 & 2\\
\hline
0 & \{ABBCC,ABCBC\} & \{BBACC,BBCAC\} & \{BABCC,BACBC\}\\
1 & \{BBCCA,BCBCA\} & \{BACCB,BCACB\} & \{ABCCB,ACBCB\}\\
2 & \{BCCAB,CBCAB\} & \{ACCBB,CACBB\} & \{BCCBA,CBCBA\}\\
3 & \{CCABB,BCABC\} & \{CCBBA,ACBBC\} & \{CCBAB,BCBAC\}\\
4 & \{CABBC,CABCB\} & \{CBBAC,CBBCA\} & \{CBABC,CBACB\}
\end{array}
$$
Here $p_1$ and  $p_2$ are represented by integers indicating the required amount of right shift.  We see that $S$ has been partitioned into $5\cdot3=15$ equal parts.
The same argument proves that the number of words of one A, $k-1$ Bs, and $m-k$ Cs is divisible by $mk$ when $m$ and $k$ are relatively prime.
