Example 2. The sides of an $n$-sided polygon are sequentially denoted as $a_{1}, a_{2}, \cdots$, 20. Each side is painted one of three colors: red, yellow, or green, such that no two adjacent sides have the same color. How many different coloring methods are there?
Solve: First, color the edge $a_{1}$, there are 3 ways to do so.
Then color the edge $a_{2}$, since $a_{2}$ must be a different color from $a_{1}$, there are 2 ways to color $a_{2}$.
Similarly, for $a_{3}, a_{4}, \cdots, a_{n-1}, a_{n}$, there are 2 ways to color each.
Thus, there are $3 \cdot 2^{n-1}$ ways to color in total.
However, this method only ensures that $a_{i}$ and $a_{i+1}$ are different colors $(i=1,2, \cdots, n-1)$, but it does not ensure that $a_{1}$ and $a_{n}$ are different colors.
Thus, these coloring methods can be divided into two categories:
One category is where $a_{n}$ and $a_{1}$ are different colors, which is the valid coloring method for an $n$-sided polygon, denoted as $S(n)$ ways;

The other category is where $a_{n}$ and $a_{1}$ are the same color, in which case $a_{n}$ and $a_{1}$ can be considered as one edge, and this coloring method is equivalent to the valid coloring method for an $(n-1)$-sided polygon, which is $S(n-1)$ ways.
Thus, we have
$$
S(n)+S(n-1)=3 \cdot 2^{n-1},
$$

which implies $S(n)-2^{n}=-\left(S(n-1)-2^{n-1}\right)$.
Therefore, $\left\{S(n)-2^{n}\right\}$ is a geometric sequence with a common ratio of -1,
then
$$
\begin{array}{l}
S(n)-2^{n}=\left(S(3)-2^{3}\right) \cdot(-1)^{n-3} . \\
\text { It is easy to find that } S(3)=6, \text { then } \\
S(n)-2^{n}=(6-8)(-1)^{n-3}, \\
S(n)=2^{n}+2(-1)^{n} .
\end{array}
$$

Therefore, the number of valid coloring methods is $2^{n}+2(-1)^{n}$.