Hi, I'm trying to combinatorially prove the following identity:
On the right side, is the number of ways we can choose a -element subset from a -element set, while on the left side there is the sum of ways we can select an -element subset from a -element, -element,..., -element set...
How can we prove that the numbers on both sides of the equation are actually identical?
I'd be really grateful for any help.
You could try using proof by induction:
You need this formula,
1: let r=1 and show that the two sides are equal.
2: Assume that it's true for r = k.
This tells us,
3: Now prove that it's true for r = k+1
This is equal to,
Now making use of the formula from the start
simplify the LHS
using and simplifying further
You can show the two sides are equal for k+1 so equal for all k ( or r)