How many ordered pairs (A,B), where A,B are subsets of {1, 2, . . . , n}, are there such that |A $\displaystyle \cap$ 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.
$\displaystyle \sum_{k=1}^{n}\binom{n}{k}\cdot\binom{k}{1} \cdot 2^{n-k-1} $
$\displaystyle = \sum_{k=1}^{n}\frac{n!}{k!\cdot(n-k)!} \cdot k \cdot2^{n-k-1} $
$\displaystyle = 2^{n-1}\cdot \sum_{k=1}^{n}\frac{n!}{(k-1)!\cdot(n-k)!} \cdot2^{-k} $
$\displaystyle = 2^{n-1}\cdot n\cdot \sum_{k=1}^{n}\frac{(n-1)!}{(k-1)!\cdot(n-k)!} \cdot2^{-k} $
$\displaystyle = 2^{n-1}\cdot n\cdot \sum_{k=1}^{n}\binom{n-1}{k-1} \cdot2^{-k} $
$\displaystyle = 2^{n-1}\cdot n\cdot \sum_{k=0}^{n-1}\binom{n-1}{k} \cdot2^{-k} $
We can now observe that the formula for the binomial theorem can be used to simplify the summation with $\displaystyle a = 1 and b = \frac{1}{2} $
$\displaystyle = 2^{n-1}\cdot n\cdot \left( 1+\frac{1}{2} \right)^{n-1}$
$\displaystyle = 2^{n-1}\cdot n\cdot \left(\frac{3}{2} \right)^{n-1}$
$\displaystyle = n\cdot 3^{n-1}$
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 $\displaystyle A\cap B$. 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 $\displaystyle n\cdot 3^{n-1}$. (I would not have noticed that without seeing hans.kruger11's solution!)