Example 4 The sides of a convex $n$-gon are sequentially denoted as $a_{1}, a_{2}, \cdots, a_{n}$. Each side is to be painted one of three colors: red, yellow, or blue, such that no two adjacent sides have the same color. How many different coloring methods are there?
Solution: Let there be $s_{n}$ ways of coloring, obviously $s_{3}=6, a_{1}$ has three coloring methods, after coloring $a_{1}$, then color $a_{2}$, according to the problem, there are 2 ways to color, $a_{3}$ also has 2 ways to color, and so on, the total number of ways to color all $n$ sides is $3 \times 2^{n-1}$, but this coloring method can only ensure that $a_{i}$ and $a_{i+1}(i=1,2, \cdots, n-1)$ are different colors, while $a_{1}$ and $a_{n}$ might be the same color. If $a_{n}$ and $a_{1}$ are the same color, then consider $a_{n}$ and $a_{1}$ as the same side, the total number of coloring methods is exactly $s_{n-1}$, thus we get the recurrence relation
$$
s_{n}+s_{n-1}=3 \cdot 2^{n-1} \quad(n \geqslant 3),
$$

Using the method of undetermined coefficients, let $s_{n}-p \cdot 2^{n}=-\left(s_{n-1}-p \cdot 2^{n-1}\right)$,
comparing coefficients with (1) gives $p=1$, so the sequence $\left\{s_{n}-2^{n}\right\}$ is a geometric sequence with the 3rd term
$$
s_{3}-2^{3}=6-8=-2,
$$

and a common ratio of -1, thus $\quad s_{n}=2^{n}+2(-1)^{n-2}(n \geqslant 3)$.
Therefore, the number of coloring methods that meet the conditions is $2^{n}+2 \cdot(-1)^{n-2}$ ways.