0
$\begingroup$

So I'm completely new to this, and I have a very basic understanding of how this works. Here is my best attempt at trying to prove this.

${2n \choose n}$

=$\frac{(2n)!}{(n)!(2n-n)!}$

=$\frac{(2n)!}{2(n)!}$

and then

${2n-1 \choose n}$

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

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

I have no idea if this is the method to prove this problem, or even if I have done it correctly up to this point. I hit a block in trying to get the ${2n \choose n}$ equivalent to the ${2n-1 \choose n}$.

I am really at a beginner level here, so if you could explain your steps it would be great!

$\endgroup$
  • 1
    $\begingroup$ Hint: $(2n)!=2n\times (2n-1)!$ $\endgroup$ – J. W. Tanner Mar 15 at 20:10
  • 1
    $\begingroup$ Notice that $$\frac{(2n - 1)!}{(n)! (n - 1)!} = \frac{(2n)!}{(2n) \cdot (n)! (n - 1)!}$$ $\endgroup$ – Viktor Glombik Mar 15 at 20:10
  • $\begingroup$ @J.W.Tanner So I'm really new to this, can you explain how that's equivalent? I'm still learning how to work with factorials, and I'm at a real beginner's level. $\endgroup$ – Brownie Mar 15 at 20:20
  • 1
    $\begingroup$ I put an explanation in my answer $\endgroup$ – J. W. Tanner Mar 15 at 20:34
4
$\begingroup$

First of all you made a mistake when you wrote that $(n)!(n)!=2(n)!$. It should be $(n!)^2$. So $\binom{2n}{n}=\frac{(2n)!}{(n!)^2}$.

Next, you got that $\binom{2n-1}{n}=\frac{(2n-1)!}{(n)!(n-1)!}$. Now just multiply and divide the expression by $2n$. You will get $\frac{(2n)!}{2(n!)^2}$. Hence $2\binom{2n-1}{n}=\frac{(2n)!}{(n!)^2}=\binom{2n}{n}$.

$\endgroup$
  • $\begingroup$ This is great thanks for the explanation! I know this is a really basic question, but I'm kinda iffy on working with factorials. Could you explain how the multiplying and diving by 2n works? $\endgroup$ – Brownie Mar 15 at 20:19
  • 1
    $\begingroup$ Well, if you multiply and divide by the same number you don't change the expression. Now let's see what we get from this. In the numerator we have $(2n-1)!\times (2n)=(2n)!$. In the denominator it is $(n)!(n-1)!\times (2n)=2(n)!(n-1)!n=2(n)!(n)!$. $\endgroup$ – Mark Mar 15 at 20:20
  • $\begingroup$ oh, I see. So I didn't know / understand that (n-1)! * n just equals n!. Thanks for breaking it down! $\endgroup$ – Brownie Mar 15 at 20:25
  • 1
    $\begingroup$ It follows from the definitions. $(n-1)!\times n=(1\times 2\times 3\times...\times (n-1))\times n=1\times 2\times...\times n=n!$. $\endgroup$ – Mark Mar 15 at 20:30
2
$\begingroup$

$$\text{We know from Pascal's triangle that }\binom m k=\binom{m−1}{k−1}+\binom{m−1}{k}.$$ $$\therefore\binom{2n}n=\binom{2n−1}{n−1}+\binom{2n−1}n=2\binom{2n−1}n$$

$$\text{since }\binom{2n-1}{n-1}=\binom{2n-1}n\text{ since } (2n-1)-(n-1)=n.$$

$\endgroup$
  • $\begingroup$ Inspired by @Bernard $\endgroup$ – J. W. Tanner Mar 15 at 21:32
2
$\begingroup$

With very few calculations:

We can use the recurrence relation $$\binom nk=\frac nk\binom{n-1}{k-1}, $$ which is the basis of the proof of the formula with factorials. In particular, $$\binom{2n}n= 2\binom{2n-1}{n-1}=2\binom{2n-1}n,\quad\text {since}\quad n=(2n-1)- (n-1).$$

$\endgroup$
  • $\begingroup$ Quite a fine proof too! $\endgroup$ – Bernard Mar 15 at 20:59
  • $\begingroup$ Ok, I put it as another answer. $\endgroup$ – J. W. Tanner Mar 15 at 21:09
1
$\begingroup$

Noting $2n-n=n, $ we have $${2n \choose n}=\frac{\color{red}{(2n)!}}{\color{green}{(n)!}(n)!}.$$

Also, noting $(2n-1)-n=n-1, $ we have $${2n-1 \choose n}=\frac{(2n-1)!}{(n)!(n-1)!}.$$

Finally, note that $\color{red}{(2n)!}=2n\times(2n-1)!$ and $\color{green}{n!}=n\times(n-1)!$ and $\frac {2n}n=2$ and we're done.


The last note is because $m! = m\times(m-1)\times(m-2)\times...\times2\times1$ and

$(m-1)!=(m-1)\times (m-2)\times...\times2\times1$,

so $m!=m\times(m-1)!$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.