1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please use the set given to prove the statement. For example S1 = {(1,1)} $\endgroup$ – user636032 Jan 19 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy