# 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.