A circular disk is divided into n sectors, each shaped like a piece of pie and all meeting at the centre point of the disk. Each sector is to be painted either red, green or blue in such a way that no two adjacent sectors are painted the same colour. Let P(n) denote the number of distinct ways to paint the disk.
a) Find explicitly P(1), P(2), P(3). b) Find a recurrence relation for P(n) in terms of P(n-1) and P(n-2) for each integer n>3.
I've done part a, (3,6,6). But I'm stuck on how to approach part b. I've had trouble with finding recurrence relations in general, so a approach that I could apply in the future would also help. Thanks in advance!
for part $B$ look at a given coloring; select a "particular slice", there are two possibilites: the first possibility is the slices adjacent to that slice have the same color. In that case when we take away that slice and merge the other two slices into one slice we get a pie with $n-2$ slices, since there are $2$ ways to select the color of the "particular slice" there are $2P(n-2)$ valid colorings where the slice to the sides of the "particular slice" have the same color.
the other possibility is that the slices to the sides of the "particular slice" have different colors. In this case when we remove the "particular slice" we get a valid coloring of $n-1$ slices, and this coloring determines the color of the "particular slice". So there are $P(n-1)$ colorings of this type.
So the recursion is $P(n)=2P(n-2)+(Pn-1)$