The original question was
Let $S=\{1,2,3...n\}$. Find the number of unordered pairs $\{A,B\}$ such that A and B are disjoint. (Either of them or both may be empty)
I came forward with two solution $${3^n+1\over 2}$$and $${1\over2}+\sum_{k=0}^n\binom nk 2^{n-k-1}$$
Both of them are equal. I've check on Desmos and Geogebra. How can I show this analytically?
PS. I know how to get both the answers. Just not sure how to prove them equal
Hint: Calculate $(1+2)^n$ in two different ways.