How many ordered pairs (A,B), where A,B are subsets of {1, 2, . . . , n}, are there such that |A B| = 1?
We can prove this via straightforward counting techniques and some elementary algebra. You want to first count all the A sets and then for each of those A sets you want to count all possible B sets such that their intersection comes out to be exactly equal to 1. So first we choose A set from n elements. Then we choose the element we want to be common in the both sets. Then from the remaining elements we just choose the B set. So from this we get the following summation.
We can now observe that the formula for the binomial theorem can be used to simplify the summation with
Hence Proved.
Once you have seen the answer, it's easy to derive it more quickly. There are n possibilities for the one element that is in . For each of the other n–1 elements, there are three possibilities: (i) the element belongs to A, (ii) the element belongs to B, (iii) the element belongs to neither A nor B. Total number of choices is therefore . (I would not have noticed that without seeing hans.kruger11's solution!)