True or false: $C(199,49) = C(200,50) - C(199,50)$

Question

I am currently very confused with this problem as I believe $C(200,50) - C(199,50)$ should equal $C(1,0)$ which makes no sense... a friend in my class believes this problem equals $C(199,49)$ but I do not see how...

Any help or input on this question would mean a lot! I personally think the answer is false but I have never really understood how to multiply, add, or subtract numbers like $200$ choose $50$.

Thank you in advance for any assistance!

Here $C(n, k)= { n \choose k}$

Answer 1

Just do it. $C(199, 49) = \frac {199!}{150!49!}$

And $C(200,50) - C(199, 50) = \frac {200!}{150!50!}-\frac {199!}{149!50!}=$

$\frac {200}{50}\cdot \frac {199!}{150!49!} - \frac 1{\frac 1{150}\cdot 50}\cdot\frac {199!}{150!49!}=$

$4C(199,49) - 3C(199,49)= C(199,49)$

We can generalize this to prove $C(n,k) -C(n-1,k)= \frac {n!}{(n-k)!k!}- \frac {(n-1)!}{(n-k-1)!k!}= (\frac n{n-k}-1)\frac {(n-1)!}{(n-k-1)k!}=$

$\frac {k}{n-k}\frac {(n-1)!}{(n-k-1)k!}= \frac {(n-1)!}{(n-k)!(k-1)!}=C(n-1,k-1)$ (which is, as Yves Daoust points out, Pascal's formula)

Meanwhile $C(1,0) = 1$ as $C(x,0) = 1$, and in particular $C(1,0) = \frac {1!}{1!0!} = \frac 1{1\cdot 1} = 1$.

And clearly For any $n \ge k > 0$ we have $C(n,k)=\frac {n!}{(n-k)!k!} = \frac {(n-k+1)(n-k+2).....(n-1)n}{1\cdot 2\cdot ....(k-1)(k)} = (n-k+1)\cdot \frac{n-k+2}2\cdot .... \cdot \frac {n-1}{k-1}\cdot \frac nk > 1\cdot 1\cdot.... \cdot 1\cdot 1 > 1$. Which is just common sense. If you have a choice to pick some items from a larger number of items you obviously have more than one way of doing that!

I believe C(200,50)−C(199,50) should equal C(1,0) which makes no sense

If it makes no sense then why do you believe it?

Do you think $C(n,k) - C(m, j)$ should equal $C(n-m, k-j)$?

There's no reason to think that. Very few operations actually distribute over addition/subtraction (those that do are called linear operations and they are the exception, not the norm). Unless there is a logistical reason why removing $m$ out of $n$ should result in a linear reduction of choices (which it shouldn't as choices are combinations and combinations grow nearly exponentially) there is no reason we should assume this.

Answer 2

This is Pascal's formula. $$\frac{199!}{150!49!}=\frac{200!}{150!50!}-\frac{199!}{149!50!}$$

$$\frac{50\cdot199!}{150!50!}=\frac{200\cdot199!}{150!50!}-\frac{150\cdot199!}{150!50!}$$

Answer 3

Imagine your company has $200$ programmers, and you, Marie, are one of them. They are selecting a group of $50$ programmers to work on a project. The number of ways they can do this is $C(200, 50)$, correct?

Now, for any given group of $50$ programmers, there are two options:

1. You, Marie, are part of the group. If you are part of the group, then there are $49$ other people in the group, chosen from the $199$ programmers in the company who are not you. So there are $C(199, 49)$ ways to select a group of $50$ people that includes you.

2. You, Marie, are not part of the group. That means all $50$ people in the group came from the $199$ programmers who are not you. So there are $C(199, 50)$ ways to select a group of $50$ people that does not include you.

Since every group of $50$ that can be formed either includes you or does not include you, it follows that

$$C(200, 50) = C(199, 49) + C(199, 50).$$

More generally, $C(n, k) = C(n-1, k-1) + C(n, k-1)$ by a similar argument, the method of distinguished element.