Combinatorial (non-algebraic) Proof: $ {}_{n}C_{4}={}_{n-1}C_{3}$ +${}_{n-2}C_{3} +{}_{n-3}C_{3} + \cdots + {}_{3}C_{3} $

Question

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.'

Answer 1

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}.$$

Answer 2

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.