How can we prove this combinatorial identity
$$\frac{{}^nC_r}{r+1}=\frac{{}^{n+1}C_{r+1}}{n+1}$$
How can we prove above combinatorial identity preferably by some intuitive logic or double counting approach?
Asked
Active
Viewed 66 times
1 Answers
2
From a set with $n+1$ elements, count the pairs of one element and a subset of $r$ elements from the remaining.
First way: choose one element (first part of the pair), then choose $r$ among $n$ for the second part, that is $(n+1){n\choose r}$ possibilities.
Second way: choose $r+1$ elements, and pick one among them to get the first part of the pair and the remaining is the second part: $(r+1){n+1\choose r+1}$ possibilities.
Jean-Claude Arbaut
- 23,277
-
1Just realised this is same problem as here, here, here and here but in disguising different form!!! (Correct me if I am wrong.) To me this comment is most satisfying double counting proof. – RajS Oct 11 '19 at 20:06