Example 2 A bug crawls along a triangular iron ring, at each vertex the bug has an equal chance of crawling to one of the other two vertices. Then the probability that the bug is back at the starting point after $n$ moves is $\qquad$ [2]
【Analysis】Suppose the bug starts from vertex $A$ of $\triangle A B C$.
Since there are two possible directions, clockwise or counterclockwise, at each vertex, there are $2^{n}$ possible ways of movement after $n$ steps.

Let the number of ways the bug can end up at points $A, B, C$ after $n$ moves be denoted as $A_{n}, B_{n}, C_{n}$, respectively.

Assume that a clockwise move from any vertex is denoted as “1” and a counterclockwise move as “-1”. Each walk of $n$ steps from point $A$ can correspond to an ordered array
$$
\left(x_{1}, x_{2}, \cdots, x_{n}\right)\left(x_{i} \in\{1,-1\}, i=1,2, \cdots, n\right)
$$

Obviously, there are $2^{n}$ distinct ordered arrays, i.e.,
$$
A_{n}+B_{n}+C_{n}=2^{n} \text {. }
$$

Assume that in a certain walk, there are $k$ counterclockwise moves, and let
$$
p(k)=\sum_{i=1}^{n} x_{i}=n-2 k(k=0,1, \cdots, n) \text {. }
$$

Since $p(k) \equiv 0,1,2(\bmod 3)$ corresponds to the bug ending at points $A, C, B$ respectively, and the same $p(k)$ value corresponds to $\mathrm{C}_{n}^{k}$ different walks. The $n+1$ distinct $k$ values can be divided into three categories: $\left\{k_{i}^{(0)}\right\}, \left\{k_{i}^{(1)}\right\}, \left\{k_{i}^{(2)}\right\}$, satisfying
$$
\begin{array}{l}
p\left(k_{i}^{(0)}\right) \equiv 0(\bmod 3)(i=1,2, \cdots, s), \\
p\left(k_{i}^{(1)}\right) \equiv 1(\bmod 3)(i=1,2, \cdots, t), \\
p\left(k_{i}^{(2)}\right) \equiv 2(\bmod 3)(i=1,2, \cdots, r) . \\
\text { Clearly, } s + t + r = n + 1 . \\
\text { Since } A_{n}=\sum_{i=1}^{s} \mathrm{C}_{n}^{k_{n}^{(1)}}(i=1,2, \cdots, s), \\
C_{n}=\sum_{i=1}^{r} \mathrm{C}_{n}^{k_{n}^{(1)}}(i=1,2, \cdots, t), \\
B_{n}=\sum_{i=1}^{r} \mathrm{C}_{n}^{k_{n}^{(3)}}(i=1,2, \cdots, r),
\end{array}
$$

How can we find $A_{n}, B_{n}, C_{n}$? We need to find a special number that can easily yield $A_{n}, B_{n}, C_{n}$.
$$
\begin{array}{l}
\text { Note that, } \omega=\cos \frac{2 \pi}{3}+\mathrm{i} \sin \frac{2 \pi}{3} \text { (a cube root of 1). } \\
\text { Then } \omega^{p\left(k_{i}^{(0)}\right)}=\omega^{0}=1, \omega^{p\left(k_{k_{1}^{(1)}}\right)}=\omega^{1}=\omega, \\
\omega^{p\left(x_{i}^{(2)}\right)}=\omega^{2}=\bar{\omega} \text {. } \\
\text { Hence } \sum_{i=0}^{n} \mathrm{C}_{n}^{k} \omega^{n-2 k}=\frac{1}{\omega^{n}} \sum_{i=0}^{n} \mathrm{C}_{n}^{k} \omega^{2 n-2 k} \\
=\frac{1}{\omega^{n}} \sum_{i=0}^{n} \mathrm{C}_{n}^{k}\left(\omega^{2}\right)^{n-k}=\frac{1}{\omega^{n}}\left(1+\omega^{2}\right)^{n} \\
=\frac{1}{\omega^{n}}(-\omega)^{n}=(-1)^{n} \text {. } \\
\text { Also } \sum_{i=0}^{n} \mathrm{C}_{n}^{k} \omega^{n-2 k} \\
=\sum_{i=1}^{1} \mathrm{C}_{n}^{k^{(0)}} \omega^{p\left(k_{i}^{(0)}\right)}+\sum_{i=1}^{1} \mathrm{C}_{n}^{k_{k}^{(i)}} \omega^{p\left(k_{i}^{(j)}\right)}+\sum_{i=1}^{1} \mathrm{C}_{n}^{k^{(i)}} \omega^{p\left(k_{i}^{(2)}\right)} \\
=A_{n}+C_{n} \omega+B_{n} \bar{\omega} \\
=A_{n}-\frac{1}{2}\left(B_{n}+C_{n}\right)+\frac{\sqrt{3}}{2}\left(C_{n}-B_{n}\right) \mathrm{i} \text {, } \\
\end{array}
$$

Combining with equation (2) we get
$$
A_{n}-\frac{1}{2}\left(B_{n}+C_{n}\right)=(-1)^{n}, C_{n}-B_{n}=0 .
$$

Combining with equation (1) we solve to get $A_{n}=\frac{2^{n}+(-1)^{n} \times 2}{3}$.
Thus, the probability that the bug returns to the starting point after $n$ moves is
$$
P=\frac{2^{n}+(-1)^{n} \times 2}{3 \times 2^{n}} \text {. }
$$

From the above two examples, it can be seen that the periodicity of $\omega^{n}$ can provide a unique approach to solving problems.