Example 4 There are $n$ squares arranged in a row, to be painted with red, yellow, and blue. Each square is painted one color, with the requirement that no two adjacent squares are the same color, and the first and last squares are also different colors. How many ways are there to paint them?
(1991, Jiangsu Mathematics Competition)
Solution: Let there be $a_{n}$ ways of coloring, it is easy to see that $a_{1}=3, a_{2}=$ $6, a_{3}=6$, and when $n \geqslant 4$, after numbering the $n$ cells in sequence, cell 1 and cell $(n-1)$ are not adjacent.

Case 1: The color of cell $(n-1)$ is different from that of cell 1. In this case, cell $n$ has only one color to choose from, and the first $(n-1)$ cells satisfy the condition that the first and last cells are of different colors, so there are $a_{n-1}$ ways of coloring.

Case 2: The color of cell $(n-1)$ is the same as that of cell 1. In this case, the color of cell $(n-2)$ must be different from that of cell 1, otherwise, cell $(n-1)$ and cell $(n-2)$ would be the same color. Thus, the first $(n-2)$ cells have $a_{n-2}$ ways of coloring. Since cell $n$ must be a different color from cell 1, there are two ways to color it, so there are $2 a_{n-2}$ ways of coloring in total.
In summary, we get the recursive equation
$$
a_{n}=a_{n-1}+2 a_{n-2} \cdot(n \geqslant 4)
$$

Solving this, we get $a_{n}=2^{n}+2(-1)^{n} .(n \geqslant 2, n \in \mathbf{N})$
For $n$ positions in a circular arrangement, the solution can be derived similarly. This idea is also applicable to solving probability problems.