In how many ways $n$ dishes around a round table can be colored with 3 colors with adjacent dishes with different colors 
Consider a round table with $n$ places. In each place there is a colored dish. In how many ways the dishes in this table can be colored with 3 colors, in such a way that adjacent dishes have different colors?

Solution: If $P(n)$ is the number of possibilities for a table with $n$ places, it is true that $$P(n)=P(n-1)+2P(n-2).$$By inspection it is easy to show that $P(2)=6$ and $P(3)=6$, and we can find the solution for any $P(n)$ by substitution using the recursion, or by the solution for the previous difference equation given by:
$$P(n)=2^n+2(-1)^n$$.
My problem: I don't understand why $$P(n)=P(n-1)+2P(n-2)$$ is true, or why, directly, $$P(n)=2^n+2(-1)^n$$ is true. Yes, I know how last equation is obtained from the previous equation, but cannot find a reasonable argument why it makes sense from a combinatoric argument. Any help?
 A: To find the number of possibilities we label the three colors to be blue green and red. Now we assign positions $a_1,a_2...a_n$ around the circle(cyclic).
Case 1:when $a_2,a_3...a_n$ are such that when arranged in cyclic order no two o adjacent positions have same colour($P(n-1)$ ways).In that case $a_2,a_n$ are of different colours say blue and green and we have to  assign $a_1$ to be red .Hence number of possibilities is $P(n-1)$ .
Case 2: suppose $a_2,a_3...a_{n-1}$  when arranged in cyclic order no two o adjacent positions have same colour-($P(n-2)$ ways).Also inorder to make it disjoint with case 1 we take $a_2,a_n$ to be of same colours say blue,blue.In that case $a_1$ can be assigned any of the two other colours  (here green/red) Hence number of possibility is $2(P(n-2))$
A: Suppose you have your circle full of dishes. Locate yourself in one of the dishes, say the one most at north. Take it out and close the circle. There are two options: Either the dishes still form a circle with the desired property $P(n-1)$ or they are not, meaning, when you form the circle they connect in the same color. There are two options for this because they could not have been the same color as the first dish you took out. Take out one of them. Now they have to be different colors and so $P(n-2)$ in two ways so $2\cdot P(n-2).$
The second equation goes as this. Put one dish, you have $3$ options. Then you have $2$ options on the right, then two options and so on. So you will end up having $3\cdot 2^{n-1}=2^n+2^{n-1}.$ Notice that if you close the circle, perhaps the last dish is equal to the first one so if they are equal eliminate them so you will have $2^n+2^{n-1}-(2^{n-1}+2^{n-2}-(2^{n-2}+2^{n-3}-\cdots )).$  If you keep doing this is clear that most of it cancels out except the last term of the last one ($P(2)=2^2+\color{red}{2^1}=6$) which mimics, combinatorially, the telescopic sum in the difference equation. Notice that the sign alternates when you distribute it.
A: This will be a different approach and probably not the one you are looking for but still may be interesting so I am posting:
This problem can be considered as finding chromatic polynomial $\chi_{C_n}(k)$ of $C_n$ computed at $k=3$ where $C_n$ is an $n$-cycle graph. And we know an algorithm for finding chromatic polynomial of a graph, called Deletion-Contraction Formula. According to this formula, we have
$$\chi_{C_n}(k) = \chi_{C_n\cdot e}(k) + \chi_{C_n \backslash e}(k), \text{for any edge }e \in E(C_n)$$
And here, you can find chromatic polynomial of a cycle graph $C_n$ found by Deletion-Contraction Formula, which yields:
$$\chi_{C_n}(k) = (k-1)^{n} + (k-1)(-1)^{n}$$
So, for $k = 3$, we have
$$P(n) = \chi_{C_n}(3) = 2^n+2(-1)^n$$
A: Here is a different approach.  Look at the circular pattern of differences between successive colors (in a given order, say: red, green, blue) as you go around the table, so the color sequence R,G,R,B,R... gives rise to the sequence $+1,-1,-1,+1,\ldots$ say, since RG has difference $+1$, GR has difference $-1$, and so on.  The condition that the $n$ differences must satisfy is that they add up to $0 \bmod 3$.  (The cumulative sum of the first $k$ of these numbers tells you the difference in color between the $0$-th  plate and the $k$th; if you follow all the way around the circle the $0$th plate is the $n$th plate, and hence of the same color, so the sum of all $n$ differences should be $0\bmod 3$.)  Let $D_n$ count the number of such difference patterns. The number of colorings is $3D_n$: the starting chair can have any of $3$ colors, then the rest are determined by the difference pattern.
A formula for $D_n$ can be obtained by evaluating an $n$-fold convolution product:   $D_n= f^{*n}(0)$, where $f:\mathbb Z_3\to\mathbb R$ is given by $f(0)=0, f(1)=f(2)=1$. (Convolution with respect to the additive group of integers $\bmod 3$.) Writing $f=\mathbb 1-\delta$, where $\mathbb1$ is the constant function $1$, and $\delta(x)$ is $1$ at $x=0$ and $0$ elsewhere, and using the fact that $\mathbb1*\mathbb1=3 \mathbb1$, we see
\begin{align*}
D_n &= \sum_{k=0}^{n-1} \binom n k (-1)^{n-k}\mathbb1^{*k} (0)+(-1)^n\\
&= \sum_{k=0}^{n-1} \binom n k (-1)^{n-k} 3^{k-1} + (-1)^n\\
&=\frac{ (3-1)^n - (-1)^n}3 + (-1)^n
\end{align*}
so the number of colorings is
$$
3D_n = 2^n +2(-1)^n .$$
A: Let the colours be red, green, blue. To have different colours, you can either go forward on th colour cycle (red$\to$ green$\to$blue$\to$red) or backwards. So you can pick any of three colours for the first field and then make $n$ binary choices (forward or backwards). This suggests that the answer is somehow related to $2^n$, though details are left out in this simplified argument.
For the recursion, if you remove the $n$th Place, you either obtain a valid colouring for $n-1$ (namely when the neighbours had different colours, and in this case you can reconstruct the removed colour), or you need to remove a duplicate colour and thereby obtain a valid colouring for $b-2$ places, but cannot reconstruct the original colour of the $n$th place (namely, there are two possibilities).
Convince yourself, that you can obtain every colouring of $n-1$ / $n-3$ places. This we conclude $$P(n)=P(n-1)+2P(n-2).$$
