Recurrence Relation, Discrete Math problem(Homework) 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!  
 A: Consider your disk as a necklace made of four colors of beads, and a fixed starting point. Cut the necklace at the starting point.
Now you have a sequence of $n$ beads that haven't got neighboring beads of the same color, and furthermore the color of the last bead can't be the same as the first (glueing them together gives your original necklace).
Let the number of such sequences of length $n$ be $s_n$. Consider a sequence of length $n$. Its last bead isn't of the color of either end (two alternatives), and what comes before is a sequence that complies (there are $2 s_{n - 1}$ ways of doing this), or the next to last bead is of a color of either end, before that comes a complying sequence. This gives $4 s_{n - 2}$. In all:
$$
s_{n + 2} = 2 s_{n + 1} + 4 s_n
$$
For boundary conditions we have $s_2 = 4 \cdot 3 = 12$ (second must be different from first), $s_3 = 4 \cdot 3 \cdot 2 = 24$ (second different from first, third different from first and second).
Define $S(z) = \sum_{n \ge 0} s_{n + 2} z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$. Recognize the resulting sums:
$$
\frac{S(z) - s_2 - s_3 z}{z^2}
  = 2 \frac{S(z) - s_2}{z} + 4 S(z)
$$
Solving for $S(z)$ and writing as partial fractions:
\begin{align}
S(z) 
  &= \frac{12}{1 - 2 z - 4 z^2} \\
  &= \frac{6 (1 + \sqrt{5})}{\sqrt{5}} \cdot \frac{1}{1 - (1 + \sqrt{5}) z}
       - \frac{6 (1 - \sqrt{5})}{\sqrt{5}} \cdot \frac{1}{1 - (1 - \sqrt{5}) z}
\end{align}
This is just two geometric series:
$$
s_{n - 2}
  = \frac{6}{\sqrt{5}} 
      \left( 
        (1 + \sqrt{5})^{n + 1} - (1 - \sqrt{5})^{n + 1}
      \right)
$$
