Example 8 Color each vertex of an $n(n \geqslant 3)$-sided pyramid with one of $m(m \geqslant 4)$ available colors, such that the endpoints of the same edge have different colors. How many different coloring methods are there?
Given that vertex $S$ has $m$ coloring methods, and $A_{1}, A_{2}, \cdots, A_{n}$ cannot be the same color as $S$, the problem is reduced to coloring the vertices of the polygon $A_{1} A_{2} \cdots A_{n}$ with $m-1$ colors, ensuring that adjacent vertices have different colors. Let there be $a_{n}$ ways to do this, then $a_{3}=(m-1)(m-2)(m-3)$.
For $n>3$, consider the recurrence relation of $\left\{a_{n}\right\}$:
If we start coloring from $A_{1}$, then $A_{1}$ has $(m-1)$ coloring methods, and $A_{2}, \cdots, A_{n-1}$ each have $(m-2)$ coloring methods. Finally, when coloring $A_{n}$, if we only require $A_{n}$ to be different from $A_{n-1}$ (not requiring $A_{n}$ to be different from $A_{1}$), there are still $(m-2)$ coloring methods. Thus, there are a total of $(m-1)(m-2)^{n-1}$ coloring methods.
The $(m-1)(m-2)^{n-1}$ coloring methods can be divided into two categories:
One category is where $A_{n}$ is different from $A_{1}$, which meets the problem's requirements, with $a_{n}$ coloring methods;
The other category is where $A_{n}$ is the same as $A_{1}$, which does not meet the requirements. In this case, we can merge $A_{n}$ and $A_{1}$ into one point, resulting in $a_{n-1}$ coloring methods that meet the problem's requirements.
Thus,
$$
\begin{array}{l}
a_{n}+a_{n-1}=(m-1)(m-2)^{n-1}(n>3), \\
a_{n}-(m-2)^{n}=-\left[a_{n-1}-(m-2)^{n-1}\right] .
\end{array}
$$

Therefore,
$$
\begin{aligned}
a_{n}-(m-2)^{n} & =-\left[a_{n-1}-(m-2)^{n-1}\right]=(-1)^{2}\left[a_{n-2}-(m-2)^{n-2}\right] \\
& =\cdots=(-1)^{n-3}\left[a_{3}-(m-2)^{3}\right] \\
& =(-1)^{n-3}\left[(m-1)(m-2)(m-3)-(m-2)^{3}\right] \\
& =(-1)^{n-2}(m-2)=(-1)^{n}(m-2) .
\end{aligned}
$$

Thus,
$$
a_{n}=(m-2)\left[(m-2)^{n-1}+(-1)^{n}\right] \text {. }
$$

Therefore, the total number of coloring methods for the entire pyramid is $N=m(m-2)\left[(m-2)^{n-1}+(-1)^{n}\right]$.
!Note: Recurrence is a common method. In this problem, taking $n=4, m=5$, i.e., the 1995 league test question: “Color each vertex of a quadrilateral pyramid with one color, ensuring that the endpoints of the same edge are different colors. If only 5 colors are available, the total number of different coloring methods is $\qquad$ .” Using the conclusion of this problem, the answer is $N=5 \times 3 \times\left(3^{3}+1\right)=420$ methods.