Finding LCD of factorial to show that $C(2n,n+1)+C(2n,n)=\frac12 C(2n+2,n+1)$

Question

So there's an almost exact question like this here:

Use a factorial argument to show that $C(2n,n+1)+C(2n,n)=\frac{1}{2}C(2n+2,n+1)$

However, I'm getting stuck in just figuring out the lcds for the factorials.

I end up with this after the CNR:

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

When I try to find the common denominator, I do:

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

Putting it together I get:

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

Which is wrong because according to the other answer, it should be:

$$\frac{(2n+1)!}{n!(n+1)!}$$

Not sure how they got there. I guess that's my question, how did they get that?

I've been googling for hours on how to find common denominators of factorials but can't seem to find anything. I mean, what happened to the $(n-1)!$ ?

Thanks.

Answer 1

You have it right!

Notice that

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

Do you see any simplifications?

Answer 2

I think your solution is correct. Here is the visualization. Take $2n+1$ marbles. You want to pick $n+1$ among them. However you notice one very specific tiny red marble among them. It captures your attention and your decision to pick that marble or not to pick it comes before picking any other marbles.

If you choose to pick the tiny red marble, you're left with $2n$ stones and you still have $n$ to choose. If you leave the tiny red marble out, you're left with the other $2n$ marbles and still have to choose $n+1$.

Putting it together, \begin{equation} C(2n+1,n+1) = C(2n,n) + C(2n,n+1). \end{equation}

Note that in you computation, the least common multiple between $n!n!$ and $(n+1)!(n-1)!$ is $n!(n+1)!$. Indeed, \begin{align} n!\cdot n! &= (n-1)!\cdot n! \cdot n\\ (n-1) \cdot (n+1)! &= (n-1)! \cdot n! \cdot (n+1) \end{align} Hence the least common multiple is \begin{equation} (n-1)! \cdot n! \cdot n \cdot (n+1) = n! \cdot (n+1) \end{equation}

Answer 3

Prove by the combinatoric way:

You can actually simplify this equation to be $C(2n+2,n+1)=2C(2n,n+1)+C(2n,n)$

Now, on the left-hand side, we assume we have $2n+2$ elements, and we want to pick $n+1$ elements. That would give us $C(2n+2,n+1)$

On the right-hand side, this is one way we can pick our elements: We are going to separate our set of $2n+2$ elements (Assuming they are arranged from smallest to biggest) into 2 subsets; The first subset contains the first $n$ elements, and the second set contains the last $2$ elements.

There are 3 ways we can pick our elements:

Case 1: We pick $n$ elements from the set of $2n$ elements, and $1$ element from the set of $2$ elements. Hence, we have $C(2n,2).C(2,1)=2C(2n,n)$

Case 2: We pick $n+1$ elements from the set of $2n$ elements, and $0$ elements from the set of $2$ elements. Hence, we have $C(2n,n+1)$

Case 3: We pick $n-1$ elements from the set of $2n$ elements, and $2$ elements from the set of $2$ elements. We have $C(2n,n-1).C(2,2)=C(2n,n-1)$. However, we need to take note that $C(2n,n-1)=C(2n,n+1)$ because $2n-(n+1)=n-1$

Therefore, our our right-hand side, the number of ways to choose $n+1$ elements from 2 different sets is

$2C(2n,n)+C(2n,n+1)+C(2n,n-1)=2C(2n,n)+C(2n,n+1)+C(2n,n+1)=2C(2n,n)+2C(2n,n+1)$, which is what is to be shown!

I hope that this combinatoric argument would help you because there are some questions where algebraic argument is very difficult to manipulate!

Answer 4

Another route is through the recurrence relations.

Note that $C(2n,n+1) = C(2n,n-1)$

Then

$\begin{align} 2\cdot \left( C(2n,n+1)+C(2n,n) \right) &= C(2n,n-1)+2C(2n,n) + C(2n,n+1)\\[1ex] &= C(2n+1,n)+C(2n+1,n+1) \\[1ex] &= C(2n+2,n+1) \\ \end{align}$