Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show $ {}_{n}C_{4}={}_{n-1}C_{3}$ +${}_{n-2}C_{3} +{}_{n-3}C_{3} + \cdots + {}_{3}C_{3} $

where: ${}_{n}C_{i}$ is the number of ways of choosing $i$ elements from $n$

-I've been explicitly requested to provide a non algebraic proof; and to instead use a 'combinatorial argument.'

-'Combinatorial argument' refers to providing a synonymous situation that describes the above equation.

what I attempted:

-choosing $4$ balls from $n$ balls in an urn may be done in ${}_{n}C_{4}$ ways.

This is the same as:

1)st step: from n-1 balls choose 3

2)nd step: from n-2 remaining balls choose 3

.

.

.

n-3)th step: from 3 remaining balls choose 3

The events above are therefore the same as choosing 4 balls from n.


The above "proof" doesn't convince me if it is indeed proof.

Does anybody have insight into how this problem may be visualized using a 'combinatorial argument.'

share|improve this question

2 Answers 2

up vote 6 down vote accepted

The idea you describe does give a proof. Perhaps we can be a little more explicit. We want to choose $4$ numbers from the numbers $1,2,3,\dots,n$. This can be done in $\binom{n}{4}$ ways.

Let us count the number of choices in another way.

Look at the number of choices where the smallest chosen number is $1$. So we need to choose $3$ numbers from $2,3,\dots,n$ to go with the $1$. There are $\binom{n-1}{3}$ ways to do this.

Look at the number of choices where the smallest chosen number is $2$. So we need to choose $3$ numbers from $3,4,\dots,n$ to go with the $2$. There are $\binom{n-2}{3}$ ways to do this.

Look at the number of choices where the smallest chosen number is $3$. So we need to choose $3$ numbers from $4,5,\dots,n$ to go with the $3$. There are $\binom{n-3}{3}$ ways to do this.

Continue. Finally, look at the number of choices where the smallest chosen number is $n-3$. The remaining $3$ numbers can be chosen in $\binom{3}{3}$ ways. We conclude that $$\binom{n}{4}=\binom{n-1}{3}+\binom{n-2}{3}+\binom{n-3}{3}+\cdots+\binom{3}{3}.$$

share|improve this answer

Here is how you can see it. Say you want to choose $4$ people from a group of $n$ persons. You can indeed do this in ${}_nC_4$ ways.

Now take one of the person, say Bob. We will now choose the group with regards to Bob. Groups of $4$ that Bob is part of are in numbers ${}_{n-1}C_3$ and those that do not contain Bob are in numbers ${}_{n-1}C_4$. So you get ${}_{n}C_4={}_{n-1}C_3+{}_{n-1}C_4$

Now apply the same argument to ${}_{n-1}C_4$ to get ${}_{n-1}C_4={}_{n-2}C_3+{}_{n-2}C_4$. Keep doing it until you get to ${}_3C_3$ and you will get your formula.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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