Evaluate $4^n = \sum_{k=0}^{n} {n \choose k} 3^k$ Prove $4^n = \sum_{k=0}^{n} {n \choose k} 3^k$, using a combinatorial proof of
the set $S = \{(a_1, a_2)| a_1, a_2 \in \{1...n\}\}$.
I'm having trouble figuring out how to prove $4^n$(LHS) using the set given.

Proof: Consider all colourings of set {1,2,...,$n$} with colours red, green, blue, white. LHS is just a number of all of the colourings. To obtain RHS, first colour all numbers white, then choose $k$ of them, which will be recoloured with either red, green or blue each. 
