Simplifying Combinatorics: Proving nC(k-1) + nCk = (n+1)Ck for k>0

[courtrigrad]

Hello all

In my calculus book, this problem has been pestering me"

Prove nC(k-1) + nCk = (n+1)Ck, where k > 0 which is read " n choose k-1" + "n choose k"

= n+1C k.

I tried using the formula for the binomial coefficient, but it becomes very messy. I also tried setting k = 1, but then it did not seem like I was actually proving it. Rather I was showing that the statement holds for k > 0. Would I have to use proof my induction? Any replies would be greatly appreciated.

Thanks a lot

 

[Gokul43201]

Use the definition of nCk in terms of factorials. Use the fact that n! = n(n-1)! OR alternatively, (n+1)! = (n+1)n!. Start from the LHS and don't stop till you get the RHS

 

[M98Ranger]

for bringing up this topic!

Hello,

This is a great question and one that many students struggle with when first learning about combinatorics. You are on the right track with using the binomial coefficient formula, but as you mentioned, it can get quite messy.

One approach to proving this statement is by using a combinatorial argument. This means that we will use the concept of combinations to show that both sides of the equation represent the same thing.

Let's start by breaking down the left side of the equation, nC(k-1) + nCk. This can be read as "n choose k-1" + "n choose k".

For the first term, "n choose k-1", we can think of this as the number of ways to choose a group of k-1 objects from a set of n objects.

For the second term, "n choose k", we can think of this as the number of ways to choose a group of k objects from the same set of n objects.

Now, let's look at the right side of the equation, (n+1)Ck. This can be read as "(n+1) choose k". This represents the number of ways to choose a group of k objects from a set of n+1 objects.

So, we can see that both sides of the equation represent the same thing - the number of ways to choose a group of k objects from a set of n+1 objects. Therefore, we can conclude that nC(k-1) + nCk = (n+1)Ck.

To answer your question about using proof by induction, yes, that is another approach that can be used to prove this statement. However, using a combinatorial argument is often simpler and more intuitive for problems involving combinations.

I hope this helps and good luck with your studies!