Let . It is quite commonly known that the number of subsets one can form from are , but how many pairs of these subsets is true?
So we're interested in finding all pairs such that
Let a set with elements. Then we have sets such that . Namely these are all sets, disjunct with , we can unite with such that .
Thus the total amount of such pairs are: . With the Binomium of Newton.
Not much really, it's pretty elementary. You've seen the induction proof of .How much math must I learn to understand this? Am I hopeless?
However this can fairly easily shown by applying the binomium of Newton too!
Observe that .
Namely: it's how many different ways we can choose 0 elements, + how many different ways we can choose 1 element...etc.
However note that . Applying the binomium of newton: with .
And this gives: .
That idea is used here again here.
Taking an element with elements. How many sets exist such that ? Well, we have elements in . So we have elements left to choose from. Observe that the amount of such 's equals the amount of subsets we can create from elements!
Hence there exists of such B's in .
Since we have elements in of length , it follows we have pairs , where is a set of length and .
Now we only need to sum over all different lengths a set can have. Thus we obtain:
Total amount of pairs = .
And if we analyse this number close we can recognise the binomium of Newton again with .
Hence we obtain: Total amount of pairs