Prove by induction that the number of 2-subsets of an n-set A equals n(n-1)/2.
Let me illustrate in a lazy way.
What we are being asked to do is choose 2 out of n. C(n,2).
As you can see, everything cancels in the numerator and denominator except
Check it, how many 2 subsets can be made from 10. C(10,2)=45
Now, we want to show an induction step.
See what cancels this time?. Everything but
And it is shown.
Sorry Galactus, but I don’t think the question is asking us to assume any combinatorial formula at all. Here’s a more direct way.
First, check that the statement is true for . Obviously the empty set can’t have any subset with 2 elements and so that’s fine. (To be on the safe side, we might also check the case , possibly even , but I’m sure the inductive method below works by just assuming .)
Now assume the statement is true for any set with n elements ( ). Consider a set A with elements and pick any element . (A contains at least 1 element.) Then contains n elements. The number of 2-element subsets of A not containing a is just the number of 2-element subsets of , which by the inductive hypothesis is . The number of 2-element subsets of A which do contain a is n (i.e. a plus any of the other n elements of A). So:
no. of 2-element subsets of A = no. of 2-element subsets of A not containing a + no. of 2-element subsets of A containing a
which you should find is equal to .