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

Question

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?

Answer 1

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

Answer 2

$\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.

Answer 3

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!

Answer 4

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.