Not much really, it's pretty elementary. You've seen the induction proof of
.
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