There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have the same color. Find the Recurrence Relation of $S_n$ (possible ways to paint the disk for $n$ sections).
Here is what I am thinking so far:
Case $1$: $S_1=4$ since for the whole disk, we can pick $4$ possible colors to paint it.
Case $2$: $S_2=4 \times 3=12$ There are $4$ colors to choose for the first section, $3$ remaining for the second.
Case $3$: $S_2=4 \times 3 \times 2=24$ (Since for the first section, we can pick $4$ colors, the second has $3$ possible choices. The third only have $2$ since it can't be the same with both the first one and the second one.
Case $4$: For $4$ sections, similarly, the first section have $4$ choices. The second section have $3$ choices. The third section have $3$ choices. For the last section, there is uncertainty. If the first and third section have the same color. Then it has $3$ choices. Else, it just have $2$ choice. So I don't know how many possible choices would be there.
For now, my strategy is to find cases from $1$ to $5$ or $6$. Then I will figure out the recurrence relation numerically... But I know it's not the right way to go.
This should not be a hard problem and I'd appreciate your help!