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 **