# Math Help - Permutation/Combination

1. ## Permutation/Combination

I need help with this question please.
If n is positive whole number, show that (n)(2nCn)= (n+1)(2nCn-1)

As 2nCn - 2nCn-1 is a whole number show that (1/n+1)(2nCn) is a whole number

2. ## Re: Permutation/Combination

Originally Posted by mlg
I need help with this question please.
If n is positive whole number, show that (n)(2nCn)= (n+1)(2nCn-1)
As 2nCn - 2nCn-1 is a whole number show that (1/n+1)(2nCn) is a whole number
$(n)\dbinom{2n}{n}=\dfrac{(n)(2n)!}{(n!)^2}~\&~(n+ 1)\dbinom{2n}{n-1}=\dfrac{(n+1)(2n)!}{(n+1)!(n-1)!}$

3. ## Re: Permutation/Combination

Thanks for the quick response.

4. ## Re: Permutation/Combination

If your teacher wants a more combinatorial proof, then $\binom{2n}{n}$ is the number of $n$-element subsets of a $2n$-element set. Similarly, $\binom{2n}{n-1}$ is the number of $(n-1)$-element subsets of a $2n$-element set.

So, number the elements of the $2n$-element set $1,2,\ldots, 2n$. Consider a pair, $(i,\{a_1,\ldots, a_n\})$ where $1\le i \le n$ and $\{a_1,\ldots, a_n\}$ is an $n$-element subset of the $2n$-element set where $a_1<a_2 <\cdots <a_n$. The product principle tells us there are $n\binom{2n}{n}$ such pairs.

Given any such pair, $(i,\{a_1,\ldots, a_n\})$, remove the $i$-th element from the set, so that $\{a_1,\ldots, a_{i-1},a_{i+1},\ldots, a_n\}$ remains. Consider the remaining elements of the $2n$-element set: $\{b_1,\ldots, b_{n+1}\}$ (there are $n+1$ elements not in the set after one element is removed). Let $k$ be the index of the removed element. This allows us to create a pair, $(k,\{a_1,\ldots, a_{i-1},a_{i+1},\ldots, a_n\})$ where $1\le k \le n+1$ and the set is an $(n-1)$-element subset of the $2n$-element set. Again, the product principle tells us there are $(n+1)\binom{2n}{n-1}$ such pairs.

Now, given any such pair consisting of a number from 1 to $n+1$ and an $(n-1)$-element subset of the $2n$-element set: $(k,\{a_1,\ldots, a_{n-1}\})$, consider the remaining $n+1$ elements of the $2n$-element set: $\{b_1,\ldots, b_{n+1}\}$ where $b_1 < \cdots < b_{n+1}$. Add $b_k$ to the $n-1$-element subset. Reindex the set so that $\{a_1^\prime, \ldots, a_n^\prime\}$ satisfies $a_1^\prime < \cdots < a_n^\prime$. Let $i$ be the index of $b_k$ in this new index. This allows us to create a pair, $(i,\{a_1^\prime,\ldots, a_n^\prime\})$. These are inverse operations, implying a bijective process. If there is a bijection between two sets, they must have the same number of elements, so $n\binom{2n}{n} = (n+1)\binom{2n}{n-1}$.

The proof is a bit longer, but it also a bit stronger combinatorially.

5. ## Re: Permutation/Combination

Hello, mlg!

$\text{If }n\text{ is a natural number, show that: }\:n\left(_{2n}C_n\right)\:=\: (n+1)\left(_{2n}C_{n-1}\right)$

$n\left(_{2n}C_n\right) \;=\;\rlap{/}n\cdot\frac{(2n)!}{\rlap{/}n!\,n!} \;=\;\frac{(2n)!}{(n-1)!\,n!}$

$(n+1)\left(_{2n}C_{n-1\right)} \;=\;(\rlap{/////}n+1)\cdot\frac{(2n)!}{(n-1)!(\rlap{/////}n+1)!} \;=\;\frac{(2n)!}{(n-1)!\,n!}$

6. ## Re: Permutation/Combination

Thanks for your time and effort.
Very much appreciated.