Example 2 Divide a circle into $n$ sectors, and color the sectors using $r$ colors, with each sector being one color, and no two adjacent sectors having the same color. Question: How many coloring methods are there?


【Analysis】For $n$ sectors arranged in a circle, denoted as $\left(A_{1}, A_{2}, \cdots, A_{n}\right)$, where $A_{i}(1 \leqslant i \leqslant n)$ is adjacent to $A_{i+1}$. The coloring requirement is that $A_{i}(1 \leqslant i \leqslant n)$ and $A_{i+1}$ must be different colors. First, we moderately "relax" this requirement and construct a "quasi-coloring": requiring that $A_{i}(1 \leqslant i \leqslant n-1)$ and $A_{i+1}$ are different colors, which may include the case where $A_{n}$ and $A_{1}$ are the same color. Removing this case gives us the exact solution, which is the same as the original problem for $n-1$ sectors.

Let $x_{n}$ be the number of valid coloring methods. Then
$$
x_{1}=r, x_{2}=r(r-1) \text {. }
$$

For $x_{n}(n \geqslant 3)$, sector $A_{1}$ has $r$ coloring methods, sector $A_{2}$, which is different from $A_{1}$, has $r-1$ coloring methods; $\cdots \cdots$ sector $A_{n}$, which is different from $A_{n-1}$, has $r-1$ coloring methods. Therefore, there are $r(r-1)^{n-1}$ coloring methods in total.

However, $A_{n}$ may be the same color as $A_{1}$. In this case, we can consider $A_{n}$ and $A_{1}$ as one sector, which is exactly the problem of coloring $n-1$ sectors, with $x_{n-1}$ methods.
Thus, $x_{n}=r(r-1)^{n-1}-x_{n-1}(n \geqslant 3)$.
(This requires $n-1>1$, otherwise, there would be no $A_{1}$ and $A_{n}$ being the same color sector to bundle (although $x_{1}=r$, there is no recursive formula $\left.x_{1}+x_{2}=r(r-1)\right)$. Hence, $x_{n-1}+x_{n}=r(r-1)^{n-1}$ $(n \geqslant 3)$. $)$

Using "alternating addition and subtraction" can find the general term, but it requires discussing the parity of $n$.
Below is a method to avoid discussing the parity of $n$. Notice that,
$$
\begin{array}{l}
x_{2}+x_{3}=r(r-1)^{2}, \\
x_{3}+x_{4}=r(r-1)^{3}, \\
\cdots \cdots . \\
x_{n-1}+x_{n}=r(r-1)^{n-1} .
\end{array}
$$

Multiplying equation (i) $(1 \leqslant i \leqslant n-2)$ by $(-1)^{i+1}$ gives
$$
\begin{array}{l}
(-1)^{2} x_{2}+(-1)^{2} x_{3}=r(1-r)^{2}, \\
(-1)^{3} x_{3}+(-1)^{3} x_{4}=r(1-r)^{3}, \\
\cdots \cdots \\
(-1)^{n-1} x_{n-1}+(-1)^{n-1} x_{n}=r(1-r)^{n-1} .
\end{array}
$$

Adding all these equations gives
$$
\begin{array}{l}
x_{2}+(-1)^{n-1} x_{n} \\
=r(1-r)^{2} \frac{1-(1-r)^{n-2}}{r} \\
=(1-r)^{2}-(1-r)^{n} \\
=(r-1)^{2}+(-1)^{n+1}(r-1)^{n} . \\
\text { Also, } x_{2}=r(r-1) \text {, so } \\
(-1)^{n-1} x_{n} \\
=(r-1)^{2}+(-1)^{n+1}(r-1)^{n}-r(r-1), \\
x_{n}=(-1)^{n-1}(r-1)^{2}+(r-1)^{n}+ \\
\quad(-1)^{n} r(r-1) \\
=(r-1)^{n}+(-1)^{n}(r-1)(n \geqslant 3) .
\end{array}
$$

Also, when $n=2$, the above formula holds.
And when $n=1$, $x_{1}=r$, hence
$$
x_{n}=\left\{\begin{array}{ll}
(r-1)^{n}+(r-1)(-1)^{n}, & n \geqslant 2 ; \\
r, & n=1 .
\end{array}\right.
$$