Example 3 A password lock's password setting involves assigning one of the two numbers, 0 or 1, to each vertex of a regular $n$-sided polygon $A_{1} A_{2} \cdots A_{n}$, and coloring each vertex either red or blue, such that for any two adjacent vertices, at least one of the number or color is the same. How many different password settings are there for this type of password lock?
Let $S_{n}$ be the desired result, and let $a_{n}, b_{n}, c_{n}$ represent the number of ways to set the password when $A_{n}=A_{1}$, $A_{n} \neq A_{1}$, and $A_{n} \# A_{1}$, respectively.
Then $S_{n}=a_{n}+b_{n}$.
It is easy to see that $\left(a_{1}, b_{1}, c_{1}\right)=(4,0,0)$,
$\left(a_{2}, b_{2}, c_{2}\right)=(4,8,4)$,
$\left(a_{3}, b_{3}, c_{3}\right)=(12,16,8)$.
When $n \geqslant 4$, we consider three cases.
(1) $A_{n}=A_{1}$, then $A_{n}$ and $A_{1}$ are effectively one point, so $a_{n}=a_{n-1}+b_{n-1}$.
(2) $A_{n} \neq A_{1}$, consider $A_{n-1}$.
(i) $A_{n-1}=A_{1}$, then there are $a_{n-1}$ ways from $A_{1}$ to $A_{n-1}$, and $A_{n}$ has 2 ways, so there are $2 a_{n-1}$ ways.
(ii) $A_{n-1} \neq A_{1}$, then $A_{n-1}=A_{n}$, and considering $A_{n-1}$ and $A_{n}$ as one point, there are $b_{n-1}$ ways.
(iii) $A_{n-1} \# A_{1}$, consider $A_{n-2}$.
If $A_{n-2}=A_{1} \# A_{n-1}$, it is a contradiction.
If $A_{n-2} \neq A_{1}$, then there are $b_{n-2}$ ways from $A_{1}$ to $A_{n-2}$, and $A_{n-1}$ and $A_{n}$ have 1 and 2 ways respectively, so there are $2 b_{n-2}$ ways; $\square$

If $A_{n-2} \# A_{1}$, then $A_{n-2}=A_{n-1}$, and considering $A_{n-2}$ and $A_{n-1}$ as one point, there are $2 c_{n-2}$ ways.
In summary, $b_{n}=2 a_{n-1}+b_{n-1}+2 b_{n-2}+2 c_{n-2}$.
(3) $A_{n} \# A_{1}$, similarly we have
$$
c_{n}=b_{n-1}+c_{n-1} \text {. }
$$

Combining equations (1) and (4), we get
$$
S_{n}=3^{n}+(-1)^{n}+2
$$