Sketch: Well.. ugly problem imo. If we denote the amount of colorings with $n$ numbers, then we'll have to prove \[ a_n = 3 \cdot 2^n - 3. \] That can be shown by proving its recursive form \[ a_n = 2a_{n-1}+3. \] And showing that isn't much of a problem, just go over the cases as for how many colors were used to color the first $n$ numbers and show the claimed sequence for $a_{n+1}$. Here, sometimes it is required to go over parity cases.